hdu 5106 hdu 5435ビットdp

3115 ワード

hdu 5106
本当に疲れたので、コードを説明しません.
#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; }