【Foreign】数数 [打表][DP]

数数

Time Limit: 10 Sec  Memory Limit: 128 MB

Description

　　

Input

　　仅一行两个整数L,R

Output

　　仅一行一个整数表示答案。

Sample Input

　　9 28

Sample Output

　　2

HINT

　　L,R <= 10^9，代码长度限制10k。

Source

　　我们首先想到了如何判断一个数字是否可行，考虑到了一个DP，令 f[i][j] 表示前 i 位，其中一个集合和为 j 的方案，那么 f[i+1][j] 可以转移到 f[i][j+a[i]] 或 f[i+1][j]，这样做就可以把 j 倒着跑，省去 i 这一维，又由于跑不满，判断很快，可以过100w左右的点。

　　然后我们就考虑用这个判断来打表，每隔100w输出一个表，无脑记录前缀和，这样做发现代码>10k，于是我们一波计算，决定每隔110w打一个表，成功解决该题。

　　（代码长度限制是最不资磁的！但是打表是坠妙的！）

Code

 #include<iostream>

 #include<algorithm>

 #include<cstdio>

 #include<cstring>

 #include<cstdlib>

 #include<cmath>

 using namespace std;

 #define F(a,l,b) for(a=l;a<=b;a++)

 int O=,PD,L,R,y,i,j,u,S,N,T,a[];

 bool f[];

 int A[]={,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,};

 int C(int x){for(N=T=;x;)T+=a[++N]=x%,x/=;if(T&)return ;memset(f,,sizeof(f));f[]=;T>>=;F(i,,N-)for(int j=T-a[i];j>=;j--){if(f[j]) f[j+a[i]]=;if(f[T]) return ;}return ;}

 int D(int x){y=x/O;S=A[y];F(u,y*O+,x)S+=C(u);return S;}

 int main(){;scanf("%d%d",&L,&R);printf("%d",D(R)-D(L-));}