http://codeforces.com/contest/1073
AB
はい。
C
にぶたん。
D
煩雑になるだろうなぁと思ったら、実は愚直な解法がO(NlogT)になっているという。良問。
何回も同じ値についてmodを取るとかなりの勢いで値が減っていくことがあんまり意識できてなかった。
E
めんどくさいけどまあまあうまく実装できたと思う。
とりまf(at, bit):=bitの集合に属する数をすでに使っているとする。あとのat+1桁を埋める際に最終的にKの条件を満たす数の個数
という関数でDPしといて他の値も求めていくみたいな感じでやりました。
int K; ll L, R; ll dp[20][(1 << 10)][2]; ll ep[20][(1 << 10)][2]; ll po10[20]; ll f(int at, int bit, int used) { if(at == -1) { if(__builtin_popcount(bit) <= K && used == 1) { return 1; } else return 0; } if(ep[at][bit][used] != -1) return ep[at][bit][used]; ll res = 0; if(used) { for(int i = 0; i <= 9; i++) { ADD(res, f(at - 1, bit | (1 << i), used)); } } else { for(int i = 1; i <= 9; i++) { ADD(res, f(at - 1, bit | (1 << i), 1)); } ADD(res, f(at - 1, bit, 0)); } return ep[at][bit][used] = res; } ll loop(int at, int bit, int used) { if(at == -1) return 0; if(dp[at][bit][used] != -1) return dp[at][bit][used]; ll res = 0; if(used) { for(int i = 0; i <= 9; i++) { ADD(res, f(at - 1, bit | (1 << i), used) * po10[at] % mod * i % mod); ADD(res, loop(at - 1, bit | (1 << i), used)); } } else { for(int i = 1; i <= 9; i++) { ADD(res, f(at - 1, bit | (1 << i), 1) * po10[at] % mod * i % mod); ADD(res, loop(at - 1, bit | (1 << i), 1)); } ADD(res, loop(at - 1, bit, 0)); } return dp[at][bit][used] = res; } ll G(ll N) { //N miman if(N == 0) return 0; vector<int> vec; while(N > 0) { vec.pb(N % 10); N /= 10; } reverse(all(vec)); ll res = 0; int bit = 0; ll tmp = 0; rep(i, 0, sz(vec)) { if(i == 0) { ADD(res, loop(sz(vec) - i - 2, 0, 0)); for(int j = 1; j < vec[i]; j++) { ADD(res, loop(sz(vec) - i - 2, bit | (1 << j), 1)); ADD(res, f(sz(vec) - i - 2, bit | (1 << j), 1) * po10[sz(vec) - 1 - i] % mod * j % mod); } } else { for(int j = 0; j < vec[i]; j++) { ADD(res, loop(sz(vec) - i - 2, bit | (1 << j), 1)); ADD(res, f(sz(vec) - i - 2, bit | (1 << j), 1) * ((tmp + po10[sz(vec) - 1 - i] * j % mod) % mod) % mod); } } bit |= (1 << vec[i]); ADD(tmp, po10[sz(vec) - 1 - i] * vec[i] % mod); } return res; } void solve() { cin >> L >> R >> K; memset(ep, -1, sizeof(ep)); memset(dp, -1, sizeof(dp)); po10[0] = 1; for(int i = 0; i <= 19; i++) { po10[i + 1] = po10[i] * 10 % mod; } cout << (G(R + 1) - G(L) + mod) % mod << "\n"; }