大佬救救我
by Lazystone @ 2019-03-30 17:00:55
```cpp
#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read()
{
int data=0;int w=1; char ch=0;
ch=getchar();
while(ch!='-' && (ch<'0' || ch>'9')) ch=getchar();
if(ch=='-') w=-1,ch=getchar();
while(ch>='0' && ch<='9') data=(data<<3)+(data<<1)+ch-'0',ch=getchar();
return data*w;
}
int a,b;
int p,q;
int c[20],cnt;
int ans;
int f[20][20][100][100];
int g[20][20][20][20];
inline int dfs(int len,int pos,int num,int limit,int lead,int sum){
if(!len){
return sum*2>=pos;
}
if(lead&&!limit&&f[len][pos][num][sum]!=-1){
return f[len][pos][num][sum];
}
int up=limit?c[len]:9;
int ret=0;
for(int i=0;i<=up;i++)
ret+=dfs(len-1,pos-(!lead&&!i),num,limit&&i==up,lead||i,sum+(i==num&&(lead||i)));
if(lead&&!limit)
f[len][pos][num][sum]=ret;
return ret;
}
inline int Dfs(int len,int pos,int s1,int s2,int num1,int num2,int limit,int lead){
if(!len)
return num1==num2&&num1+num2==pos;
if(!limit&&lead&&g[len][pos][num1][num2]!=-1)
return g[len][pos][num1][num2];
int up=limit?c[len]:9;
int ret=0;
if(!lead)
ret+=Dfs(len-1,pos,s1,s2,num1,num2,0,0);
if(s1<=up&&(lead||s1))
ret+=Dfs(len-1,pos,s1,s2,num1+1,num2,limit&&s1==up,1);
if(s2<=up&&(lead||s2))
ret+=Dfs(len-1,pos,s1,s2,num1,num2+1,limit&&s2==up,1);
if(!limit&&lead)
g[len][pos][num1][num2]=ret;
return ret;
}
inline int solve(int x){
cnt=0;
while(x){
c[++cnt]=x%10;
x/=10;
}
int ans1=0,ans2=0;
for(int i=0;i<=9;i++){
memset(f,-1,sizeof(f));
ans1+=dfs(cnt,cnt,i,1,0,0);
}
for(int i=1;i<=9;i++){
for(int j=0;j<=i-1;j++){
memset(g,-1,sizeof(g));
ans2+=Dfs(cnt,cnt,i,j,0,0,1,0);
}
}
return ans1-ans2;
}
signed main(){
a=read();b=read();
printf("%lld\n",solve(b)-solve(a-1));
return 0;
}
```
凉凉~~~
by Lazystone @ 2019-03-30 17:12:14