azerah.in / azerah.out
Por Costel the Pig has received a royal invitation to the palace of the Egg-Emperor of Programming, Azerah. Azerah had heard of the renowned pig and wanted to see him with his own eyes. Por Costel, having arrived at the palace, tells the Egg-Emperor that he looks "tasty". Azerah feels insulted (even though Por Costel meant it as a compliment) and, infuratied all the way to his yolk, threatens to kill our round friend if he doesn‘t get the answer to a counting problem that he‘s been struggling with for a while
Given an array of numbers, how many non-empty subsequences of this array have the sum of their numbers even ? Calculate this value mod (Azerah won‘t tell the difference anyway)
Help Por Costel get out of this mischief!
Input
The file azerah.in will contain on its first line an integer , the number of test cases. Each test has the following format: the first line contains an integer
(the size of the array) and the second line will contain
integers
(
), separated by single spaces.
It is guaranteed that the sum of over all test cases is at most
Output
The file azerah.out should contain lines. The
-th line should contain a single integer, the answer to the
-th test case.
Example
2
3
3 10 1
2
4 2
3
3
给你一个序列，问你有多少个子序列的元素和为偶数。
水dp。分别记f(i)为前i位元素和为偶数的子序列数，g(i)为前i位元素和为奇数的子序列数。瞎几把转移一下就行了。
#include<cstdio>
#include<cstring>
using namespace std;
typedef long long ll;
#define MOD 1000000007ll
int T,a[1000010],n;
ll f[1000010],g[1000010];
int main()
{
// freopen("a.in","r",stdin);
freopen("azerah.in","r",stdin);
freopen("azerah.out","w",stdout);
scanf("%d",&T);
for(;T;--T)
{
memset(f,0,sizeof(f));
memset(g,0,sizeof(g));
scanf("%d",&n);
for(int i=1;i<=n;++i)
scanf("%d",&a[i]);
if(a[1]%2)
g[1]=1;
else
f[1]=1;
for(int i=2;i<=n;++i)
if(a[i]%2)
{
f[i]=(g[i-1]+f[i-1])%MOD;
g[i]=((f[i-1]+g[i-1])%MOD+1ll)%MOD;
}
else
{
f[i]=((f[i-1]*2ll)%MOD+1ll)%MOD;
g[i]=(g[i-1]*2ll)%MOD;
}
printf("%d\n",f[n]);
}
return 0;
}
【动态规划】Gym - 100923A - Por Costel and Azerah
原文：http://www.cnblogs.com/autsky-jadek/p/6321740.html