HDU 4734 F(x) 2013 ACM/ICPC 成都网络赛

传送门：http://acm.hdu.edu.cn/showproblem.php?pid=4734

数位DP。

用dp[i][j][k] 表示第i位用j时f(x)=k的时候的个数，然后需要预处理下小于k的和，然后就很容易想了

dp[i+1][j][k+(1<<i)]=dp[i][j1][k];(0<=j1<=j1)

AC代码：

#include <iostream>#include <cstdio>#include <cstring>#include <string>#include <cstdlib>#include <cmath>#include <vector>#include <list>#include <deque>#include <queue>#include <iterator>#include <stack>#include <map>#include <set>#include <algorithm>#include <cctype>using namespace std;typedef __int64 xiaohao;typedef long long LL;const int N=7000;const int INF=0x3f3f3f3f;const double PI=acos(-1.0);const double eps=1e-7;int dp[12][12][N];int tsum[12][12][N];int w[20];void init(){    memset(dp,0,sizeof(dp));    dp[0][0][0]=1;    int n=10;    for(int i=0;i<12;i++)    {        for(int j=0;j<n;j++)        {            for(int k=0;k<N-1;k++)            {                for(int k1=0;k1<n;k1++)                {                    int t1=k+k1*(1<<i);                    dp[i+1][k1][t1]+=dp[i][j][k];                }            }        }    }    memset(tsum,0,sizeof(tsum));    for(int i=1;i<12;i++)    {        for(int j=0;j<n;j++)        {            for(int k=0;k<N-1;k++)            {                tsum[i][j][k]=tsum[i][j][k-1]+dp[i][j][k];            }        }    }}int f(int x,int fa){    if(x==0) return 0;    int len=0;    int flag=0;    while(x)    {        w[++len]=x%10;        x/=10;    }    int tsum1=0;    for(int i=len;i>=1;i--)    {        for(int k=0;k<w[i];k++)        {            tsum1+=tsum[i][k][fa-flag];        }        flag+=(w[i])*(1<<(i-1));        if(fa<flag)            break;    }    return tsum1;}int main(){    init();    int cas;    while(~scanf("%d",&cas))    {        for(int q=1;q<=cas;q++)        {            int a,b;scanf("%d%d",&a,&b);            int len=0;            int fa=0;            while(a)            {                int t1=a%10;                fa+=(1<<(len))*t1;                len++;                a/=10;            }            int ans=f(b+1,fa);            printf("Case #%d: %d\n",q,ans);        }    }    return 0;}