江门网站上排名,如何做一款服装网站,百度做网站怎么联系,室内设计招标网站Atcoder刷不动的每日一题... 首先注意到一个事实#xff1a;随着 \(l, r\) 的增大#xff0c;\(f(r) - f(l)\) 会越来越小。考虑暴力处理出小数据的情况#xff0c;我们可以发现对于左端点 \(f(l) 7\) 的情况下#xff0c;右端点的最大限度为 \(\frac{10^8}{8} 10^7… Atcoder刷不动的每日一题... 首先注意到一个事实随着 \(l, r\) 的增大\(f(r) - f(l)\) 会越来越小。考虑暴力处理出小数据的情况我们可以发现对于左端点 \(f(l) 7\) 的情况下右端点的最大限度为 \(\frac{10^8}{8} 10^7\) 。这个范围并不大可以直接用 two-pointer 处理出来。 那么这部分的数据和后面的数据有什么不同呢 当 \(f(l) 7\) 的时候\(f(r) - f(l) 1\)。那么设 \(l f(l)\)我们有 \( x * l y * (l 1) S \) 令 \( t x y \) 原式等于 \( t * l y S \) 我们令 \(x y y\) 即 \( x ! 0 \)那么最后一个式子实际上表达的是 \( y S \ mod \ t \)。也就是说对于任何的一个确定的 \(t\)当 \(l\) 的范围 \( 7\)我们都可以找到唯一对应的 \(x, y\) 与之对应。那么我们就可以扫一遍所有的 \(t\)以求得答案。注意当 \( y 0 \) 时对答案的贡献为这个数字范围内所有长为 \(t\) 的区间。 #include bits/stdc.h
using namespace std;
#define maxn 23000000
#define int long long
#define mod 1000000007
int digit[maxn], ans, S;int read()
{int x 0, k 1;char c; c getchar();while(c 0 || c 9) { if(c -) k -1; c getchar(); }while(c 0 c 9) x x * 10 c - 0, c getchar();return x * k;
}int Qpow(int times)
{int x 10, base 1;for(; times; times 1, x x * x % mod)if(times 1) base base * x % mod;return base;
}void Up(int x, int y) { x (x y) % mod; }
signed main()
{S read(); int lim S / 8, now 0;for(int i 1; i maxn; i ) digit[i] digit[i / 10] 1;for(int i 1, now 0, tem 0; i 1e7; i ){while(tem S) { tem digit[now]; now ; }if(tem S) { ans 1; if(ans mod) ans - mod; } tem - digit[i];}for(int i 1; i lim; i ){if(!(S % i)) {int l S / i, sum Qpow(l - 1) * 9 % mod;Up(ans, (sum - i 1 mod) % mod);}else { int l (S - S % i) / i;ans 1; if(ans mod) ans - mod; }}printf(%lld\n, ans);return 0;
} 转载于:https://www.cnblogs.com/twilight-sx/p/9739078.html
