UVA 12063 Zeros and Ones （数位dp）

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 ( 1T100). Then T test cases will follow, each in one line. The input for each test case consists of two integers, N ( 1N64) and K ( 0K100).

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

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

题目大意：

　　就是说，给你一个长度为n的二进制序列，然后让你求出能够整除k的序列的个数，标准的数位dp

解题思路：

　　开始定义了一个状态：dp[i][j][k] 表示有i个0和j个1组成的二进制序列被K MOD后余数为k的序列的个数

　　　　　　初始状态：dp[0][1][1%K]=1;

　　　　　　状态转移方程：如果我们加入的是一个1的话，dp[i][j+1][(k*2+1)%K]+=dp[i][j][k];

　　　　　　　　　　　　　　如果我们加入的是一个0的话,dp[i+1][j][(k*2)%K] += dp[i][j][k];

代码：

 1 # include<cstdio>
 2 # include<iostream>
 3 # include<cstring>
 4 
 5 using namespace std;
 6 
 7 typedef long long LL;
 8 
 9 # define MAX 150
10 
11 LL dp[MAX][MAX][MAX];//dp[i][j][k]表示的是由i个0，j个1组成的数字，除以K余数为k的数的个数
12 
13 
14 
15 int main(void)
16 {
17     int icase = 1;
18     int t;cin>>t;
19     while ( t-- )
20     {
21         memset(dp,0,sizeof(dp));
22         LL n,k;
23         cin>>n>>k;
24         printf("Case %d: ",icase++);
25         LL num1 = n/2;
26         LL num2 = num1;
27         if ( n%2==1||k==0 )
28         {
29             cout<<0<<endl;
30             continue;
31         }
32         dp[0][1][1%k] = 1;
33         for ( LL i = 0;i <= num1;i++ )
34         {
35             for ( LL j = 0;j <= num2;j++ )
36             {
37                 for ( LL l = 0;l <= k-1;l++ )
38                 {
39                     dp[i+1][j][(l*2)%k]+=dp[i][j][l];
40                     dp[i][j+1][(l*2+1)%k]+=dp[i][j][l];
41                 }
42             }
43         }
44         cout<<dp[num1][num2][0]<<endl;
45     }
46 
47     return 0;
48 }