2012-04-13 21:46:44Morris

[UVA][DP] 12063 - Zeros and Ones

Binary numbers and their pattern of bits are always very interesting to computer programmers. In this problem you need to count the number of positive binary numbers that have the following properties:

  • The numbers are exactly N bits wide and they have no leading zeros.
  • The frequency of zeros and ones are equal.
  • The numbers are multiples of K.

Input 

The input file contains several test cases. The first line of the input gives you the number of test cases, T ( 1$ le$T$ le$100). Then T test cases will follow, each in one line. The input for each test case consists of two integers, N ( 1$ le$N$ le$64) and K ( 0$ le$K$ le$100).

Output 

For each set of input print the test case number first. Then print the number of binary numbers that have the property that we mentioned.

Sample Input 

5
6 3
6 4
6 2
26 3
64 2

Sample Output 

Case 1: 1
Case 2: 3
Case 3: 6
Case 4: 1662453
Case 5: 465428353255261088


Illustration: Here's a table showing the possible numbers for some of the sample test cases:

6 3 6 4 6 2
101010 111000 111000

110100 110100

101100 101100


110010


101010


100110


動態方程, DP[zeros][ones][mod]
DP[i+1][j][(l<<1)%k] += DP[i][j][l];
DP[i][j+1][((l<<1)+1)%k] += DP[i][j][l];

#include <stdio.h>
#include <string.h>
long long DP[34][34][100];
int main() {
    int t, n, k;
    int i, j, l, Case = 0;
    scanf("%d", &t);
    while(t--) {
        scanf("%d %d", &n, &k);
        printf("Case %d: ", ++Case);
        if(n&1 || k == 0) {
            puts("0");
            continue;
        }
        memset(DP, 0, sizeof(DP));
        /*[zeros][ones][mod];*/
        DP[0][1][1%k] = 1;
        n /= 2;
        for(i = 0; i <= n; i++) {
            for(j = 0; j <= n; j++) {
                for(l = 0; l < k; l++) {
                    DP[i+1][j][(l<<1)%k] += DP[i][j][l];
                    DP[i][j+1][((l<<1)+1)%k] += DP[i][j][l];
                }
            }
        }
        printf("%lld\n", DP[n][n][0]);
    }
    return 0;
}