Atcoder681 Typical DP Contest E.数 数位dp

写什么递归….非递归多好写

令$f[i][j]$表示前$i$位的和在模$d$意义下为$j$的方案数，然后转移即可

复杂度$O(10000 * 100 * 10)$

注意非递归建议高位摆第$n$位…

#include <cstdio>
#include <cstring>
using namespace std;#define ri register int
#define rep(io, st, ed) for(ri io = st; io <= ed; io ++)
#define drep(io, ed, st) for(ri io = ed; io >= st; io --)const int sid = ;
const int pid = ;
const int mod = 1e9 + ;char s[sid];
int d, n, f[sid][pid];inline void inc(int &a, int b) { a += b; if(a >= mod) a -= mod; }
inline int inv(int a) { return (d - (a % d)) % d; }void Solve() {
    f[][] = ;
    rep(i, , n)
        rep(j, , ) rep(k, , d - )
            inc(f[i][(k + j) % d], f[i - ][k]);    int ret = ;
    rep(i, , n - ) rep(j, , )
        inc(ret, f[i - ][inv(j)]);
    rep(i, , s[n] - )
        inc(ret, f[n - ][inv(i)]);    int sum = s[n] % d;
    drep(i, n - , ) {
        rep(j, , s[i] - )
            inc(ret, f[i - ][inv(sum + j)]);
        sum = (sum + s[i]) % d;
    }
    if(!sum) ret ++;
    printf("%d\n", ret);
}int main() {
    scanf("%d", &d);
    scanf("%s", s + );
    n = strlen(s + ); reverse(s + , s + n + );
    rep(i, , n) s[i] = s[i] - '';
    Solve();
    return ;
}