UVA – 12063
| Time Limit: 3000MS | Memory Limit: Unknown | 64bit IO Format: %lld & %llu |
Submit Status
Description
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
T100). 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
56 36 46 226 364 2
Sample Output
Case 1: 1Case 2: 3Case 3: 6Case 4: 1662453Case 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 |
Source
Root :: ACM-ICPC Dhaka Site Regional Contests :: 2004 – Dhaka
Root :: AOAPC II: Beginning Algorithm Contests (Second Edition) (Rujia Liu) :: Chapter 10. Maths :: Exercises
Root :: Competitive Programming 2: This increases the lower bound of Programming Contests. Again (Steven & Felix Halim) :: More Advanced Topics :: More Advanced Dynamic Programming :: DP + bitmask
Submit Status
求长度为n的串(不含前导0)，0的个数和1的个数相等且是k的倍数的个数。
#include<bits/stdc++.h>
#define foreach(it,v) for(__typeof((v).begin()) it = (v).begin(); it != (v).end(); ++it)
using namespace std;
typedef long long ll;
ll dp[40][40][100];
int n,k,tot;
ll d(int ones,int zeros,int mod)
{
ll & res = dp[ones][zeros][mod];
if(res!=-1)return res;
if(ones==tot&&zeros==tot) return res = (mod==0);
if(ones==tot)return res = d(ones,zeros+1,(mod<<1)%k);
if(zeros==tot)return res = d(ones+1,zeros,(mod<<1|1)%k);
return res = d(ones+1,zeros,(mod<<1|1)%k) + d(ones,zeros+1,(mod<<1)%k);
}
int main()
{
int T;
scanf("%d",&T);
for(int cas = 1; cas <= T; ++cas) {
memset(dp,-1,sizeof dp);
scanf("%d%d",&n,&k);
ll res = 0;
tot = n>>1;
if((n&1)==0&&k)res = d(1,0,1);
printf("Case %d: %lld\n", cas,res);
}
return 0;
}今天的文章UVA 12063（dp记忆化）分享到此就结束了，感谢您的阅读。
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
如需转载请保留出处：http://bianchenghao.cn/62229.html
