UVA 12063(dp记忆化)

UVA 12063(dp记忆化)UVA-12063ZerosandOnesTimeLimit:3000MSMemoryLimit:Unknown64bitIOFormat:%lld&%lluSubmitStatusDescriptionBinary

UVA – 12063

Zeros and Ones
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$ \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 

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 36 46 2
101010111000111000
 110100110100
 101100101100
  110010
  101010
  100110

Source

Root :: Prominent Problemsetters ::  Monirul Hasan

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

(0)
编程小号编程小号

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注