Gym-100923A-Por Costel and Azerah(DP)

链接:

题意:

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!

思路:

dp, 把子序列当成子串算了半天..

代码:

#include <iostream>
#include <memory.h>
#include <string>
#include <istream>
#include <sstream>
#include <vector>
#include <stack>
#include <algorithm>
#include <map>
#include <queue>
#include <math.h>
#include <cstdio>
#include <set>
#include <iterator>
#include <cstring>
using namespace std;

typedef long long LL;
const int MAXN = 1e6+10;
const int MOD = 1e9+7;

LL dp[MAXN][2], a[MAXN];
int n;

int main()
{
    freopen("azerah.in","r",stdin);
    freopen("azerah.out","w",stdout);
    int t;
    cin >> t;
    while (t--)
    {
        memset(dp, 0, sizeof(dp));
        cin >> n;
        for (int i = 1;i <= n;i++)
            cin >> a[i];
        if (a[1]%2)
            dp[1][1] = 1;
        else
            dp[1][0] = 1;
        for (int i = 2;i <= n;i++)
        {
            if (a[i]%2)
            {
                dp[i][0] = (dp[i-1][0]+dp[i-1][1])%MOD;
                dp[i][1] = (dp[i-1][0]+dp[i-1][1]+1)%MOD;
            }
            else
            {
                dp[i][0] = (dp[i-1][0]*2LL+1)%MOD;
                dp[i][1] = (dp[i-1][1]*2LL)%MOD;
            }
        }
        cout << dp[n][0] << endl;
    }

    return 0;
}