Number (dp-性质数状态表示）

Number

【题目描述】

明明在做力学作业的时候发现一类数非常有趣，他们和杠杆有比较相似的结构。这类数有这样的性质：

把某一位当成支点的话，那么左边的数字到这个点的力矩和等于右边的数字到这个点的力矩和，力矩可以理解为距离乘以数字。

举个例子，4139就是满足条件的数字，把3当成支点，我们有这样的等式4 * 2 + 1 *1 = 9 * 1。

小明想知道在一个区间[x,y]中，有多少个这样的数。

【输入数据】

两个数，表示x,y。 0 <= x,y<= 1018。

【输出数据】

一个输出，表示区间[x,y]中满足条件的数的个数。

【样例输入】

7604 24324

【样例输出】

897

【数据范围】

0 <= x,y<= 1018

#include<cstdio>#include<iostream>#include<cstring>#include<cstdlib>#include<functional>#include<algorithm>using namespace std;#define MAXS 810 + 10 +4000#define MAXx 1000000000000000000#define MAXI 30long long f[MAXI][MAXS][2],depth,a[MAXI],ans,pos;  //0 <= 只能取<=第i位的数，否则超过X越界    1 高位已经取了更小的 位数 后面随便取 long long dfs(int i,int s,int c){if (s<0||s>MAXS) return 0;if ((i==0)&&((s)||(c))) return 0;if (i==0) {//cout<<i<<' '<<s<<' '<<c<<' '<<f[i][s][c]<<endl;return 1;}//cout<<i<<' '<<s<<' '<<c<<' '<<f[i][s][c]<<endl;if (f[i][s][c]>=0) return f[i][s][c];else f[i][s][c]=0;if (!c){//cout<<"push "<<a[i]<<endl;f[i][s][c]+=dfs(i-1,s-(pos-i)*a[i],0);}else{for (int k=0;k<a[i];k++) //{ cout<<"push "<<k<<endl;f[i][s][c]+=dfs(i-1,s-(pos-i)*k,0); // cout<<"pop "<<k<<endl;}for (int k=0;k<=9;k++)//{  cout<<"push "<<k<<endl; f[i][s][c]+=dfs(i-1,s-(pos-i)*k,1); //cout<<"pop "<<k<<endl;}}return f[i][s][c];}long long calc(long long x){if (!x) return 0;  //<0的杠杆数为0 long long ans=0;memset(f,0,sizeof(f));depth=0;while (x) {depth++;a[depth]=x%10;x=x/10;}for (int i=1;i<=depth/2;i++){swap(a[i],a[depth-i+1]);}ans=0;f[depth+1][0][0]=1;   // =29333f[depth+1][0][1]=1;  // <29333 for (pos=1;pos<=depth;pos++) {memset(f,128,sizeof(f));//cout<<f[19][0][0]<<endl;ans+=/*dfs(depth,0,0)+*/dfs(depth,0,1);ans--;//不考虑 0 它无论支点为几都出现 }return ans+1;   //最后 加上 0 /*f[i][s][c]=f[i-1][s-(k-i)*j][0]*/}int main(){freopen("number.in","r",stdin);freopen("number.out","w",stdout);long long x,y;scanf("%lld%lld",&x,&y);printf("%lld",calc(y+1)-calc(x));//while (1);}