HDU 5435

数位DP题，然而不会做。设dp[i][j]表示前i位异或和为j的时候的个数。先dp出所有的可能组合使得异或和为j的个数，然后按位进行枚举。对于dp[i][j]，其实不止是前i位，对于后i位的情况同样适用，当在枚举s[i]位时k，如果k<s[i]时，只需直接计算后dp[i][j]的情况就好。。

可见，我其实对于状压、数位DP已经很生疏了，因为这个暑假。。。

#include <iostream>

#include <cstdio>

#include <algorithm>

#include <cstring>

using namespace std;

#define LL long long

const int MAX=100005;

const int mod=1000000007;

int cnt[MAX][17];

char s[MAX],t[MAX];

void init(){

	memset(cnt,0,sizeof(cnt));

	cnt[0][0]=1;

	for(int i=0;i<10;i++) cnt[1][i]=1;

	for(int i=1;i<MAX-1;i++){

		for(int j=0;j<16;j++){

			for(int k=0;k<=9;k++){

				cnt[i+1][j^k]+=cnt[i][j];

				cnt[i+1][j^k]=cnt[i+1][j^k]>=mod?cnt[i+1][j^k]-mod:cnt[i+1][j^k];

			}

		}

	}

}

LL cal(char s[]){

	int cur=0; LL res=0;

	int len=strlen(s);

	for(int i=0;i<len;i++){

		int k=s[i]-'0';

		for(int j=0;j<k;j++){

			for(int h=0;h<16;h++){

				res+=(LL)cnt[len-i-1][h]*(j^h^cur);

			}

			res%=mod;

		}

		cur^=k;

	}

	return res;

}

int main(){

	init();

	int T,kase=0;

	scanf("%d",&T);

	while(T--){

		scanf("%s%s",s,t);

		LL ans=cal(t)-cal(s);

		int tmp=0,l=strlen(t);

		for(int i=0;i<l;i++) tmp^=(t[i]-'0');

		ans+=tmp; ans=(ans%mod+mod)%mod;

		printf("Case #%d: %lld\n",++kase,ans);

	}

	return 0;

}

巴特西

HDU 5435

最新文章

热门文章