hdu 5106 hdu 5435ビットdp
3115 ワード
hdu 5106
本当に疲れたので、コードを説明しません.
hdu 5435
本当に疲れたので、コードを説明しません.
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
long long int dp[1002][1002],dpl[1002][1002];//dpl[i][j] i j 1 ,dp[i][j] i , j 1 。
int bit[1003],n,c[1001];
char r[1003];
#define mod 1000000007
long long int solve()
{
long long int answer=0,s=0;
int ss=0;
memset(dp,0,sizeof(dp));
memset(bit,0,sizeof(bit));
memset(dpl,0,sizeof(dpl));
int len,k;
len=strlen(r);
int i,j;
for(i=1;i<=len;i++)
{
bit[i]=r[i-1]-'0';
}
for(i=1;i<=len;i++)
{
for(j=0;j<bit[i];j++)
{
dp[i][s+j]+=(ss*2)%mod;
dpl[i][s+j]++;
}
s+=bit[i];
ss=ss*2+bit[i];
ss%=mod;
for(j=0;j<=n;j++)
{
dp[i+1][j]+=dp[i][j]*2%mod;
dpl[i+1][j]+=dpl[i][j];
dpl[i+1][j]%=mod;
dpl[i+1][j+1]+=dpl[i][j];
dpl[i+1][j+1]%=mod;
if(dp[i][j]==0&&j!=0)
continue;
dp[i+1][j+1]+=(dp[i][j]*2+dpl[i][j])%mod;
dp[i+1][j+1]%=mod; // , , dpl 。
//printf("dp[%d][%d]=%d
",i,j,dp[i][j]);
}
}
return dp[len][n];
}
int main () {
//freopen("d:\\in.txt","r",stdin);
while(~scanf("%d%s",&n,r))
{
int ans=solve();
printf("%d
",ans);
}
return 0;
}
hdu 5435
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
long long int dp[100005][16],bit[100005];
char a[100005],b[100005];
#define mod 1000000007
long long int solve(char *str,int c)
{
long long int ans=0,s=0;
int len;
len=strlen(str);
memset(dp,0,sizeof(dp));
memset(bit,0,sizeof(bit));
for(int i=1;i<=len;i++)
{
bit[i]=str[i-1]-'0';
//printf("%d
",bit[i]);
}
int j,k,f;
for(j=1;j<=len;j++)
{
for(k=0;k<bit[j];k++)
{
dp[j][s^k]++;
}
s^=bit[j];
for(int i=0;i<=9;i++)
for(f=0;f<=15;f++)
{
dp[j+1][i^f]+=dp[j][f];
dp[j+1][i^f]%=mod;
//printf("dp[%d][%d]=%d
",j,f,dp[j][f]);
}
}
if(c!=0)
dp[len][s]++;
dp[len][0]--;
for(j=0;j<=15;j++)
{
ans+=dp[len][j]*j;
//printf("dp[%d][%d]=%d
",len,j,dp[len][j]);
ans%=mod;
}
return ans;
}
int main () {
int cas;
//freopen("d:\\in.txt","r",stdin);
//freopen("d:\\inn.txt","w",stdout);
scanf("%d",&cas);
int y=1;
while(y<=cas)
{
scanf("%s%s",a,b);
long long int ss=solve(b,1)-solve(a,0);
printf("Case #%d: %d
",y,(ss+mod)%mod);
//printf("%lld
",solve(b,1));
y++;
}
return 0;
}