hdu4734 F(x)

链接

　　这题当时在网络赛时很费劲的推出来的，以递推的形式写出来的，一些边界点特别不好控制，靠看数据改出来的。现在改出dfs形式，也是很简单的。

因为f(x)的数不会很大，直接保留前面枚举的数得出的结果即可。

 #include <iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<stdlib.h>

 #include<vector>

 #include<cmath>

 #include<queue>

 #include<set>

 using namespace std;

 #define N 15000

 #define LL long long

 //#define INF 1e18+1e12

 const double eps = 1e-;

 const double pi = acos(-1.0);

 const double inf = ~0u>>;

 const LL INF = (1ll<<);

 int dp[][N],p[];

 int d[];

 int dfs(int i,int s,bool e)

 {

     if(s<) return ;

     if(i==-) return ;

     if(!e&&dp[i][s]!=-) return dp[i][s];

     int mk = e?d[i]:;

     int ans = ;

     for(int j = ;j <= mk ; j++)

         ans+=dfs(i-,s-j*p[i],e&&j==mk);

     return e?ans:dp[i][s] = ans;

 }

 int cal(int a,int b)

 {

     int  i,g=;

     while(a)

     {

         d[g++] = a%;

         a/=;

     }

     int s = ;

     for(i =  ; i < g ; i++)

     {

         s+=d[i]*p[i];

     }

     memset(d,,sizeof(d));

     g = ;

     while(b)

     {

         d[g++] = b%;

         b/=;

     }

     return dfs(g-,s,);

 }

 int main()

 {

     int i,t,a,b;

     int kk = ;

     p[] = ;

     for(i =  ; i <= ; i++)

     p[i] = p[i-]*;

     memset(dp,-,sizeof(dp));

     scanf("%d",&t);

     while(t--)

     {

         scanf("%d%d",&a,&b);

         printf("Case #%d: %d\n",++kk,cal(a,b));

     }

     return ;

 }