题解 CF908G 【New Year and Original Order】
s_r_f
2020-04-30 19:56:58
[我的数位DP总结blog](https://www.luogu.com.cn/blog/s-r-f/oi-bi-ji-shuo-wei-dp-ge-ji-dui-shuo-wei-dp-di-yi-dian-li-xie)
这题也有两种思路$,$不过交错和那道题两种思路不管优劣都能过$,$但是在这个题目里较劣复杂度的做法就过不去了$.$
一种思路是对于$O(700*10)$个查询直接整体$DP$求答案$,$
记$dp[i][j]$表示目前已经安排到了数字$i,$已经放了$j$个数位的方案数和答案$($ 可以用一个$struct$来存 $)$
$.$每次$DP$的复杂度都是$O(700^2*10)$的$,$总复杂度$O(700^3*10^2)$过不去$,$并且不能在只$dp$一次的情况下处理多组询问$.$
另一种思路是$,$我们考虑贡献$.$
记$sum(n) = \sum\limits_{i=0}^{n-1}10^i$
那么对于一个数字答案显然为 $\sum\limits_{i=0}^{9}$ $sum($ 满足 $k\leq i$ 的数字的个数 $).$
所以对这个 $($ 满足 $k\leq i$ 的数字的个数 $)$ $dp,$就可以降低复杂度$.$
记$dp(n,m,k)$表示目前还有$n$位还没确定$,$目前已经确定下来的前缀中有$m$位数字$\geq$ $k$ $,$直接$dp$即可$.$
处理一组询问的复杂度是$O(10*700),$可以只通过一次$dp$来处理多组询问$.$
这种做法的复杂度是 $O(700^2*10),$ 可以通过本题$.$
两种做法的代码$:($ 第一种$TLE,$第二种$AC$ $)$
$upd:$这篇题解里面的**查询**和**询问**不是同一个意思$.$
一组**询问**里面会包含$O($ 进制 $\times$ 最大位数 $)$ 次**查询**$.$ 结合数位$dp$的本质不难想清楚这是为什么$.$
```cpp
/*
方法一O(700^3*10^2)
#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 705,P = 1e9 + 7;
int fac[10005],nfac[10005],inv[10005],pw[10005],prepw[10005];
inline int getval(int l,int r){ if (l>r) return 0; if (l <= 0) return prepw[r]; return (prepw[r] - prepw[l-1] + P) % P; }
inline int C(int n,int m){ return (n<0||m<0||n<m) ? 0 : (LL)fac[n] * nfac[m] % P * nfac[n-m] % P; }
inline void init(){
int i;
fac[0] = nfac[0] = inv[0] = fac[1] = nfac[1] = inv[1] = 1;
for (i = 2; i < 10005; ++i) fac[i] = (LL)fac[i-1] * i % P,inv[i] = (LL)(P-P/i) * inv[P%i] % P,nfac[i] = (LL)nfac[i-1] * inv[i] % P;
pw[0] = prepw[0] = 1;
for (i = 1; i < 10005; ++i) pw[i] = 10ll * pw[i-1] % P,prepw[i] = (prepw[i-1] + pw[i]) % P;
}
int cnt[10],suf[11];
struct data{
int f0,f1;
inline void mul(int v){ f0 = (LL)f0*v%P,f1 = (LL)f1*v%P; }
inline void add(int v){ f1 = (f1 + (LL)f0 * v) % P; }
inline void init(){ f0 = f1 = 0; }
inline void upd(data x){ f0 = (f0+x.f0) % P,f1 = (f1+x.f1) % P; }
};
data dp[N],f[N];
int n;
inline void work(int v){
register int i,j,r; int l; data vv;
for (i = 0; i <= n; ++i) f[i] = dp[i],dp[i].init();
if (!v){
for (i = 0; i <= n; ++i){
if (!f[i].f0) continue;
l = suf[v+1] + i,r = suf[v] + n - 1;
vv = f[i],vv.mul(nfac[n-i]),dp[n].upd(vv);
}
return;
}
for (i = 0; i <= n; ++i){
if (!f[i].f0) continue;
l = suf[v+1] + i,r = suf[v] + i - 1;
for (j = 0; j <= n-i; ++j,++r)
vv = f[i],vv.add((LL)getval(l,r) * v % P),vv.mul(nfac[j]),dp[i+j].upd(vv);
}
}
inline void upd(int &x,int y){ x = (x+y>=P)?(x+y-P):(x+y); }
inline int DP(int nn){
int i; data ans;
for (ans.init(),n = nn,suf[9] = cnt[9],i = 8; i >= 0; --i) suf[i] = suf[i+1] + cnt[i]; suf[10] = 0;
for (i = 0; i <= n; ++i) dp[i].init(); dp[0].f0 = fac[n];
for (i = 9; i >= 0; --i) work(i);
return dp[n].f1;
}
inline int calc(string X){
int i,j,x,ans = 0; bool flag = 0;
for (i = X.size()-1; i >= 0; --i) if ((x=X[i]-'0')||flag){
for (j = 0; j < x; ++j) ++cnt[j],ans = (ans+DP(i)) % P,--cnt[j];
flag = 1,++cnt[x];
}
return ans;
}
string addone(string X){
cerr<<X.size()<<'\n';
int i,n = X.size(),pos = 0; bool flag = 1;
for (i = 0; i < n; ++i) if (X[i] != '9'){ flag = 0; break; }
if (flag){ X.resize(n+1); X[n] = '1'; for (i = n-1; i >= 0; --i) X[i] = '0'; return X; }
while (X[pos] == '9') X[pos] = '0',++pos; X[pos]++; return X;
}
int main(){ init(); string N; cin >> N; reverse(N.begin(),N.end()); N = addone(N); cout << calc(N) << '\n'; }
*/
#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 705,P = 1e9 + 7;
inline void upd(int &x,int y){ x = (x+y>=P)?(x+y-P):(x+y); }
int pw[701];
inline void init(){
int i;
for (pw[0] = 0,pw[1] = 1,i = 2; i <= 700; ++i) pw[i] = 10ll * pw[i-1] % P;
for (i = 1; i <= 700; ++i) upd(pw[i],pw[i-1]);
}
int dp[10][701][701]; bool vis[10][701][701];
inline int DP(int k,int n,int m){
if (!n) return pw[m]; if (vis[k][n][m]) return dp[k][n][m]; vis[k][n][m] = 1;
return dp[k][n][m] = ((LL)DP(k,n-1,m+1)*(10-k)+(LL)DP(k,n-1,m)*k) % P;
}
int cnt[10];
inline int calc(string X){
int i,j,k,now,x,ans = 0; bool flag = 0;
for (i = X.size()-1; i >= 0; --i) if ((x=X[i]-'0')||flag){
for (j = 0; j < x; ++j){
for (++cnt[j],now = 0,k = 9; k ; --k) now += cnt[k],upd(ans,DP(k,i,now));
--cnt[j];
}
flag = 1,++cnt[x];
}
return ans;
}
string addone(string X){
int i,n = X.size(),pos = 0; bool flag = 1;
for (i = 0; i < n; ++i) if (X[i] != '9'){ flag = 0; break; }
if (flag){ X.resize(n+1); X[n] = '1'; for (i = n-1; i >= 0; --i) X[i] = '0'; return X; }
while (X[pos] == '9') X[pos] = '0',++pos; X[pos]++; return X;
}
int main(){
init(); string N; cin >> N; reverse(N.begin(),N.end()); N = addone(N);
cout << calc(N) << '\n';
}
```