CF908G New Year and Original Order 数位dp
CF908G New Year and Original Order 数位dp
题目大意
给 \(n<=10^{700}\)，问 \(1\) 到 \(n\) 中每个数在各数位排序后得到的数的和。答案模 \(1e9+7\)。
分析
可以分开去考虑每一位的贡献。
设 \(f[i][j]\) 为 \(i\) 这种数字在排序后在原数中是第 \(j\) 大的方案数。
那么答案就是 \(\sum_{i=1}^9 \sum_{j=1}^{len} 10^{j-1} f[i][j]\)。
发现恰好第 \(j\) 大这个限制不是很好处理，于是考虑把一个数的贡献分开。
比如 \(3459\) 就可以分成 \(1111,1111,1111,111,11,1,1,1,1\)。
发现如果一个数中大于等于 \(k\) 的数位有 \(cnt\) 个，那么贡献就是 \(\underbrace{11\cdots1}_{cnt}\)。
所以我们只需要求出在原数中大于等于 \(k\) 的数位有 \(x\) 个的方案数即可。
代码
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<iostream>
#define rg register
template<typename T>void read(rg T& x){
x=0;rg int fh=1;
rg char ch=getchar();
while(ch<'0' || ch>'9'){
if(ch=='-') fh=-1;
ch=getchar();
}
while(ch>='0' && ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
x*=fh;
}
const int maxn=705,mod=1e9+7;
inline int addmod(rg int now1,rg int now2){
return now1+=now2,now1>=mod?now1-mod:now1;
}
inline int delmod(rg int now1,rg int now2){
return now1-=now2,now1<0?now1+mod:now1;
}
inline int mulmod(rg long long now1,rg int now2){
return now1*=now2,now1>=mod?now1%mod:now1;
}
int f[maxn][maxn],num[maxn],maxcnt,ans;
char s[maxn];
int dfs(rg int ws,rg int cnt,rg int val,rg int lim){
if(cnt<0) return 0;
if(!ws) return cnt==0;
if(!lim && f[ws][cnt]!=-1) return f[ws][cnt];
rg int nans=0,up=lim?num[ws]:9;
for(rg int i=0;i<=up;i++){
nans=addmod(nans,dfs(ws-1,cnt-(i>=val),val,lim && (i==up)));
}
if(!lim) f[ws][cnt]=nans;
return nans;
}
int main(){
scanf("%s",s+1);
maxcnt=strlen(s+1);
for(rg int i=1;i<=maxcnt;i++) num[i]=s[maxcnt-i+1]-'0';
for(rg int i=1;i<=9;i++){
memset(f,-1,sizeof(f));
for(rg int j=1,now=1;j<=maxcnt;j++,now=addmod(mulmod(now,10),1)){
ans=addmod(ans,mulmod(now,dfs(maxcnt,j,i,1)));
}
}
printf("%d\n",ans);
return 0;
}
版权声明：本文为liuchanglc原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。