— DP — 1 min read
Teacher Mai is addicted to game 2048. But finally he finds it's too hard to get 2048. So he wants to change the rule:
You are given some numbers. Every time you can choose two numbers of the same value from them and merge these two numbers into their sum. And these two numbers disappear meanwhile.
If we can get 2048 from a set of numbers with this operation, Teacher Mai think this multiset is good.
You have n numbers, A1,...,An. Teacher Mai ask you how many subsequences of A are good.
The number can be very large, just output the number modulo 998244353.
There are multiple test cases, terminated by a line "0".
For each test case, the first line contains an integer n (1<=n<=10^5), the next line contains n integers ai (0<=ai<=2048).
For each test case, output one line "Case #k: ans", where k is the case number counting from 1, ans is the number module 998244353.
In the first case, we should choose all the numbers. In the second case, all the subsequences which contain more than one number are good.
2014 Multi-University Training Contest 8
hujie | We have carefully selected several similar problems for you: 4955 4954 4953 4952 4951
貌似这几天第一次做的DP题啊。想象一下二进制就能明白——当子序列的2次幂数字之和大于等于2048时这个序列就是good序列了。正面dp要dp出2048~100000肯定要超时，而反面dp只需要dp出0~2047就够了。复杂度大大降低O（11＊2048*2048）。 标程写的很厉害！尤其是逆元的处理！