HDU - 6796（数位dp）

[题目链接](https://vjudge.net/problem/HDU-6796) ------------ ------------ ```cpp #include <bits/stdc++.h> using namespace std; typedef long long ll; ll c[20][20],l,r,dp[20]; int x,a[20]; vector<int> state(10,0); map<vector<int>,ll> ans[20][2]; ll C(int n,int m) { if(m<n-m)m=n-m; if(c[n][m]!=-1)return c[n][m]; ll res=1; for(int i=m+1;i<=n;i++)res*=i; for(int i=2;i<=n-m;i++)res/=i; return c[n][m]=res; } ll dfs(int len,int lim,int f) { if(lim==0&&ans[len][f].find(state)!=ans[len][f].end())return ans[len][f][state]; if(!len) { for(int i=0;i<10;i++)if(i!=x&&state[i]>=state[x])return ans[len][f][state]=0; return ans[len][f][state]=1; } ll res=0; if(!lim&&f) { for(int i=0;i<=len;i++) { for(int j=0;j<=len-i;j++)dp[j]=0; dp[len-i]=C(len,i); for(int j=0;j<10;j++)if(j!=x) { if(state[j]>=state[x]+i) { dp[0]=0; break; } for(int k=0;k<=len-i;k++) for(int t=1;t<=min(k,state[x]+i-1-state[j]);t++) dp[k-t]+=C(k,t)*dp[k]; } res+=dp[0]; } return ans[len][f][state]=res; } int w=lim?a[len]:9; for(int i=0;i<=w;i++) { if(i||f) { if(i==x||state[i]+1<state[x]+len-1) { state[i]++; res+=dfs(len-1,lim&&i==w,1); state[i]--; } } else res+=dfs(len-1,lim&&i==w,0); } return lim?res:ans[len][f][state]=res; } ll solve(ll tmp) { int tot=0; while(tmp)a[++tot]=tmp%10,tmp/=10; return dfs(tot,1,0); } int main() { memset(c,-1,sizeof(c)); int T;scanf("%d",&T); while(T--) { for(int i=0;i<20;i++)for(int j=0;j<2;j++)ans[i][j].clear(); scanf("%lld%lld%d",&l,&r,&x); printf("%lld\n",solve(r)-solve(l-1)); } return 0; } ```