HDU 5389 Zero Escape (DP)

제목 링크
한 수의 숫자 루트는mod9 이후의 값과 관계가 있으며, 가방과 유사하면 인원 분배 계산을 완성할 수 있다.

#include <bits/stdc++.h>
using namespace std;
#define prt(k) cerr<<#k" = "<<k<<endl
typedef long long ll;
const int inf = 0x3f3f3f3f;

const int mod = 258280327;
int n, A, B;
int dp[2][11];
inline void add(int &a, int b)
{
    a += b;
    if (a >= mod) a -= mod;
}
int main()
{
    int re, ca = 1;
    scanf("%d", &re);
    while (re--) {
        scanf("%d%d%d", &n, &A, &B);
        memset(dp, 0, sizeof dp);
        A %= 9; B %= 9;
        int sum = 0;
        int now = 0;
        dp[now][0] = 1;
        for (int i=0;i<n;i++) {
            int x; scanf("%d", &x); 
            sum = (sum + x) % 9;
            for (int i=0;i<9;i++)
            {
                add(dp[now ^ 1][(i + x) % 9], dp[now][i]);
                add(dp[now ^ 1][i], dp[now][i]);
            }
            memset(dp[now], 0, sizeof dp[now]);
            now ^= 1;
        }
        int ans = 0;
        if (sum == (A + B) % 9) ans = dp[now][A];
        if (sum == A && B > 0)
            add(ans, 1);
        if (sum == B && A > 0)
            add(ans, 1);
        printf("%d
", ans);
    }
    return 0;
}