首页 > 代码库 > HDU 4507 吉哥系列故事——恨7不成妻 数位DP

HDU 4507 吉哥系列故事——恨7不成妻 数位DP

2024-07-15 13:12:23   220人阅读

这个不是求的数量，而是求平方和，所以记忆化的时候不能像以前那样无脑的来。

先来看简单的情况，如果是求和，应该怎么搞。

假如我现在搜索到第3位,一共有5位，情况应该是这样的XXiXX,注意后面的X和前面的X都是不确定的，转移的时候应该是i * 10^(5-3) * (能满足的条件的数的数量) + sigma(（每个分支下面满足条件的数量）* (分支和）)这样的形式，然后再返回到上一层。这样子就可以记忆化了。但是除了要统计数量，还要统计和。

那么这里要统计平方和的话，如果还是上面这种情况，根据(a + b)^2 = a^2 + 2*a*b + b^2可以得出(i * 10^(5 - 3))^2 * (能满足的条件的数的数量) + 2 * sigma(（每个分支下面满足条件的数量）*(分支和)) + sigma(分支平方和）。所以出了要维护分支和，还要维护分支平方和和数量。

真鬼畜

#include <cstdio>#include <cstring>#include <cmath>#include <algorithm>#include <climits>#include <string>#include <iostream>#include <map>#include <cstdlib>#include <list>#include <set>#include <queue>#include <stack>using namespace std;typedef long long LL;const int maxn = 20;const LL MOD = 1e9 + 7;int lim[maxn],len = 0;LL p10[maxn] = {1};struct EE {    LL sqsum,sum,cnt;    bool vis;    EE(LL sqsum = 0,LL sum = 0,LL cnt = 0):sqsum(sqsum),sum(sum),cnt(cnt),vis(0) {}};EE f[maxn][10][10];void getlim(LL num) {    len = 0;    memset(lim,0,sizeof(lim));    while(num) {        lim[len++] = num % 10;        num /= 10;    }}EE dfs(int now,int bitsum,int rest,int bound,LL num) {    if(now == 0) {        if(bitsum % 7 == 0 || rest % 7 == 0) return EE(0,0,0);        return EE(0,0,1);    }    EE &note = f[now][bitsum][rest];    if(note.vis && !bound) return note;    int m = bound ? lim[now - 1] : 9;    EE ret(0,0,0);    for(int i = 0;i <= m;i++) {        if(i == 7) continue;        int nbitsum = (bitsum + i) % 7;        int nrest = (rest * 10 + i) % 7;        int nbound = (i == m && bound);        EE nret = dfs(now - 1,nbitsum,nrest,nbound,num * 10 + i);        LL ff = p10[now - 1] * i % MOD;        ret.cnt = (nret.cnt + ret.cnt) % MOD;        ret.sum = ((nret.cnt * ff % MOD + nret.sum) % MOD + ret.sum) % MOD;        ret.sqsum = ((nret.cnt * ff % MOD * ff % MOD + nret.sqsum) % MOD + 2 * ff % MOD * nret.sum % MOD + ret.sqsum) % MOD ;    }    if(!bound) note = ret,note.vis = true;    return ret;}LL work(LL num) {    for(int i = 0;i < maxn;i++) {        for(int j = 0;j < 10;j++) {            for(int k = 0;k < 10;k++) {                f[i][j][k] = EE();            }        }    }    getlim(num);    EE ret = dfs(len,0,0,1,0);    return ret.sqsum;}int main() {    for(int i = 1;i < maxn;i++) p10[i] = p10[i - 1] * 10;    int T; cin >> T;    LL n,m;    while(T--) {        cin >> n >> m;        cout << (work(m) - work(n - 1) + MOD) % MOD << endl;    }    return 0;}

　　


联系
我们