das d+ dfs cnblogs fine -1 scu r+ amp
Time Limit: 1000/500 MS (Java/Others) Memory Limit: 65535/32768 K (Java/Others)
- #include < algorithm > #include < iostream > #include < cstring > #include < cstdlib > #include < cstdio > #include < cmath > #define lo long long#define mod 1000000007 using namespace std;
- int a[23];
- lo mi[41]; //mi[i]:10的i次幂
- inline lo read() {
- register long long ans = 0,
- f = 1;
- char ch = getchar();
- while (!isdigit(ch)) {
- if (ch == ‘ - ‘) f = -1;
- ch = getchar();
- }
- while (isdigit(ch)) {
- ans = ans * 10 + ch - ‘0‘;
- ch = getchar();
- }
- return ans * f;
- }
- struct num {
- lo su,
- sq,
- nu; //和,平方和,个数
- num(lo u = 0, lo q = 0, lo n = 0) : su(u),
- sq(q),
- nu(n) {}
- }
- dp[23][11][11];
- num dfs(int wi, int o, lo e, bool lim) //哪一位,每一位%7,数%7,限制?
- {
- num ans,
- zc;
- if (wi < 1) {
- ans.nu = o && e;
- return ans;
- }
- if (!lim && dp[wi][o][e].su > -1) return dp[wi][o][e];
- int l = lim ? a[wi] : 9;
- for (lo i = 0; i <= l; i++) if (i != 7) //////
- {
- zc = dfs(wi - 1, (o + i) % 7, (lo)(e * 10 + i) % 7, lim && i == a[wi]); //e+i*mi[wi-1]?
- ans.sq = (((ans.sq + i * i * mi[2 * wi - 2] % mod * zc.nu % mod) % mod + zc.sq) % mod + (lo) 2 * zc.su * i % mod * mi[wi - 1] % mod) % mod;
- ans.su = ((ans.su + zc.su) % mod + zc.nu * i % mod * mi[wi - 1] % mod) % mod;
- ans.nu = (ans.nu + zc.nu) % mod;
- }
- if (!lim) dp[wi][o][e] = ans;
- return ans;
- }
- lo sol(lo x) {
- int w = 0;
- while (x) {
- a[++w] = x % 10;
- x /= 10;
- }
- num ans = dfs(w, 0, (lo) 0, 1);
- return ans.sq;
- }
- int main() {
- int t;
- lo l,
- r;
- t = read();
- mi[0] = 1;
- for (int i = 1; i <= 38; i++) mi[i] = mi[i - 1] * 10 % mod;
- memset(dp, -1, sizeof(dp));
- while (t--) {
- l = read();
- r = read();
- lo rr = sol(r);
- lo ll = sol(l - 1);
- printf("%lld\n", (rr + mod - ll) % mod);
- }
- return 0;
- }
hdu-4507 吉哥系列故事——恨7不成妻
来源: http://www.bubuko.com/infodetail-2332608.html