UVA 12063 Zeros and Ones

题意：问有多少个N(N<=64)位二进制数满足这样的要求：

(1)没有前导0

(2)0的数目和1的数目相等

(3)可以被K(K<=100)整除

用dp(i,j,t)表示前i位数中有j个1时被K除余t的数一共有多少个。

得到方程：dp(i+1,j,t)+=dp(i,j,t);dp(i+1,j+1,(t+(1<<i))%k)+=dp(i,j,t);

然后直接递推就行了，边界条件是dp(0,0,0)=1。要注意(t+(1<<i))%k的前面会暴int，还要注意N可以为奇数，k可能为0。鄙人就这里被卡了。。

 1 #include <cstdio>
 2 #include <cstring>
 3 typedef long long LL;
 4 LL dp[70][70][101];
 5 LL pow_mod(LL a,LL p,LL n){
 6     if(p == 0)  return 1;
 7     LL ans = pow_mod(a,p/2,n);
 8     ans = ans * ans % n;
 9     if(p%2 == 1)    ans = ans * a % n;
10     return ans;
11 }
12 
13 int main(){
14     int nkase;
15     scanf("%d",&nkase);
16     for(int kase = 1;kase <= nkase;kase++){
17         int n,k;
18         scanf("%d%d",&n,&k);
19         if((n&1) || k == 0){
20             printf("Case %d: 0
",kase);
21             continue;
22         }
23         for(int i = 0;i <= n;i++)
24         for(int j = 0;j <= n;j++)
25         for(int t = 0;t < k;t++)    dp[i][j][t] = 0LL;
26         dp[0][0][0] = 1LL;
27         for(int i = 0;i <= n-1;i++)
28         for(int j = 0;j <= i;j++)
29         for(int t = 0;t < k;t++)    if(dp[i][j][t]){
30             if(i+1 != n)    dp[i+1][j][t] += dp[i][j][t];
31             LL tmp = pow_mod(2,i,k);
32             LL mod = (tmp+t) % k;
33             dp[i+1][j+1][(int)mod] += dp[i][j][t];
34         }
35         printf("Case %d: %lld
",kase,dp[n][n/2][0]);
36     }
37     return 0;
38 }

View Code