hdu5435 数位dp（大数的处理）

http://acm.hdu.edu.cn/showproblem.php?pid=5435

  
  

   
   4
0
1
2
2
1
10
9999
99999
  
  

  
  

   
   Case #1: 1
Case #2: 2
Case #3: 46
Case #4: 649032
  
  
  
  


  
  

/**
hdu5435 数位dp（大数的处理）
题目大意：一个数字的值为它各个位上数字异或的结果，给定两个数，问二者闭区间内有所有数字值得和为多少？
解题思路：我用的是记忆话搜索的写法，好像递归耗时比较多吧，比赛时过了，后来给判掉了，最后老是TLE。
           网上学的方法： dp[i][j][k]表示前i位数（k==0||k==1）异或值为j的数有多少个，k为0则表示到结尾了，1表示没有到结尾
           最后注意分别取模会TLE，具体看代码怎么实现的吧
*/
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <iostream>
using namespace std;
typedef long long LL;
const int maxn=100005;
const LL mod=1e9+7;

char s1[maxn],s2[maxn];
int bit[maxn];
LL dp[maxn][16][2];

LL solve(char *a)
{
    int n=strlen(a);
    for(int i=1; i<=n; i++)bit[i]=a[i-1]-'0';
    memset(dp,sizeof(dp));
    dp[0][0][0]=1;
    for(int i=0; i<n; i++)
    {
        int num=bit[i+1];
        for(int j=0; j<16; j++)
        {
            dp[i][j][0]%=mod;
            dp[i][j][1]%=mod;
            if(dp[i][j][0]>0)
            {
                dp[i+1][j^num][0]+=dp[i][j][0];
                for(int k=0; k<num; k++)
                {
                    dp[i+1][j^k][1]+=dp[i][j][0];
                }
            }
            if(dp[i][j][1]>0)
            {
                for(int k=0; k<=9; k++)
                {
                    dp[i+1][j^k][1]+=dp[i][j][1];
                }
            }
        }
    }
    LL ans=0;
    for(int i=1; i<=15; i++)
    {
        ans+=(dp[n][i][0]+dp[n][i][1])*(LL)i;
        ans%=mod;
    }
    ans%=mod;
    return ans;
}

int main()
{
    int T,tt=0;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%s%s",s1,s2);
        int n=strlen(s1);
        LL ans=s1[0]-'0';
        for(int i=1; i<n; i++)
            ans^=(s1[i]-'0');
        printf("Case #%d: %I64dn",++tt,(solve(s2)-solve(s1)+ans+mod)%mod);
    }
    return 0;
}