想吃冰卻又敏感保護不足?5檔高息股比定存強10倍吉隆坡最便宜行程一覽表黃曉明、林志玲攜手代言...
2012-04-13 21:46:44 人氣(615) | 回應(0) | 推薦(0) | 收藏(0) 上一篇 | 下一篇

[UVA][DP] 12063 - Zeros and Ones

0
收藏
0
推薦

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;
}

12063Zeros and OnesDP
台長:Morris
人氣(615) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: UVA |
此分類下一篇:[UVA] 11559 - Event Planning
此分類上一篇:[UVA][Math] 11428 - Cubes

我要回應
是 (若未登入"個人新聞台帳號"則看不到回覆唷!)
* 請輸入識別碼:
請輸入以下數字 (ex:123)

(有*為必填)
詳全文