本文共 1441 字，大约阅读时间需要 4 分钟。
数位DP。dp[i][j][state] 表示最高位为i，数字为j，i位之后k-1个为state的方案数。例如1 2 3 4四个数字，state用1234表示。
#pragma comment(linker, "/STACK:1024000000,1024000000")#include #include #include #include #include #include #include #include #include #include using namespace std;typedef long long LL;const double pi=acos(-1.0),eps=1e-8;void File(){ freopen("D:\\in.txt","r",stdin); freopen("D:\\out.txt","w",stdout);}inline int read(){ char c = getchar(); while(!isdigit(c)) c = getchar(); int x = 0; while(isdigit(c)) { x = x * 10 + c - '0'; c = getchar(); } return x;}LL L,R,dp[21][12][10010];int k;int f[21],q[10],sz;bool check(int limit,int x){ int tmp=x,tmpsz=0; if(tmp==0) tmpsz=1; while(tmp) tmpsz++, tmp=tmp/10; if(tmpsz>limit) return 0; if(tmpsz =1;i--) g[i]=g[i-1]; for(int i=1;i<=len-1;i++) for(int j=1;j<=9;j++) for(int s=0;s<=9999;s++) res=res+dp[i][j][s]; for(int i=len;i>=1;i--) { int D; if(i==len) D=1; else D=0; for(int j=D;j =0;pos--) for(int pre=i+1;pre<=min(len,i+pos-sz+k-1);pre++) if(f[pos]==g[pre]) fail=1; if(fail) continue; res=res+dp[i][j][s]; } } for(int s=i+1;s<=min(len,i+k-1);s++) if(g[s]==g[i]) return res; } return res;}int main(){ q[0]=1; for(int i=1;i<=5;i++) q[i]=10*q[i-1]; while(~scanf("%lld%lld%d",&L,&R,&k)) { init(); printf("%lld\n",get(R+1)-get(L)); } return 0;}
转载于:https://www.cnblogs.com/zufezzt/p/5734681.html