数位DP,求[L,R]区间内所有"数字内包含的不同数码不超过k个的数字"之和.在状态上加一维状态压缩表示含有的数码集合.一开始读错题以为是求数字的个数.读对题之后调了一会儿.
#include<cstdio> typedef long long ll; const int mod=998244353; int cnt1[1024]; int f[20][1024],g[20][1024]; int F[20][1024],G[20][1024]; int p10[20]; void init(){ p10[0]=1; for(int i=1;i<20;++i)p10[i]=p10[i-1]*10ll%mod; cnt1[0]=0; for(int i=1;i<1024;++i)cnt1[i]=cnt1[i>>1]+(i&1); for(int i=0;i<10;++i)f[1][1<<i]=1,g[1][1<<i]=1,F[1][1<<i]=i,G[1][1<<i]=i; g[0][0]=1; for(int i=2;i<=18;++i){ for(int k=0;k<1024;++k){ for(int j=0;j<10;++j){ g[i][k|(1<<j)]=(g[i][k|(1<<j)]+g[i-1][k])%mod; G[i][k|(1<<j)]=(G[i][k|(1<<j)]+G[i-1][k])%mod; G[i][k|(1<<j)]=(G[i][k|(1<<j)]+g[i-1][k]*1ll*j%mod*p10[i-1]%mod)%mod; } for(int j=1;j<10;++j){ f[i][k|(1<<j)]=(f[i][k|(1<<j)]+g[i-1][k])%mod; F[i][k|(1<<j)]=(F[i][k|(1<<j)]+G[i-1][k])%mod; F[i][k|(1<<j)]=(F[i][k|(1<<j)]+g[i-1][k]*1ll*j%mod*p10[i-1]%mod)%mod; } } } } int calc(ll lim,int c){//strictly less than lim if(lim==(ll)(1e18)){ int ans=0; for(int i=1;i<=18;++i){ for(int k=0;k<1024;++k){ if(cnt1[k]<=c)ans=(ans+F[i][k])%mod; } } return ans; } int L[20],n=0; while(lim){ L[++n]=lim;lim/=10; } int S=0; int ans=0; for(int i=1;i<=n-1;++i){ for(int k=0;k<1024;++k){ if(cnt1[k]<=c)ans=(ans+F[i][k])%mod; } } int presum=0; for(int i=n;i>=1;--i){ int lo=(i==n)?1:0; for(int j=L[i]-1;j>=lo;--j){ int tmp=(1<<j)|S; for(int k=0;k<1024;++k){ if(cnt1[tmp|k]<=c){ ans=(ans+g[i-1][k]*1ll*(presum*10ll+j)%mod*p10[i-1]%mod+G[i-1][k])%mod; } } } S|=(1<<L[i]); presum=(presum*10ll+L[i])%mod; } return ans; } int main(){ init(); ll L,R; int k; scanf("%lld%lld%d",&L,&R,&k); printf("%d\n",(calc(R+1,k)-calc(L,k)+mod)%mod); return 0; }转载于:https://www.cnblogs.com/liu-runda/p/9897261.html
