hdu 5389 Zero Escape（dp）

题意：

有n个玩家，每个玩家有一个id，id可能相同，然后有两扇门，每扇门有一个数字，当某几个人的数根等于门上的数字的时候，这些人就可以进入这扇门，问n个人对于2扇门，有几种不同的进门方式。
每个人都必须要进一扇门。
数根是将一正整数的各个位数相加(即横向相加)，若加完后的值大于10的话，则继续将各位数进行横向相加直到其值小于十为止，或是，将一数字重复做数字和，直到其值小于十为止，则所得的值为该数的数根。例如54817的数根为7，因为5+4+8+1+7=25，25大于10则再加一次，2+5=7，7小于十，则7为54817的数根。

思路：

很容易想到，如果能找到满足题意的解，一定满足A和B的和等于n个人的标号的和，所以我们只需要判断n个人的标号组成A的情况有多少（或者只判断B，同理），同时还要注意，可以把n个人都分给a，或者都分给b，这样也是满足的。
所以$dp[i][j]$表示第$i$个人的标号组成$j$的情况有多少种
dp公式为：$dp[i][j] = (dp[i-1][j] + dp[i-1][(j - C[i] + 9) % 9]$

$my$ $code$

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN = (int)1e6 + 10;
const int MOD = 258280327;
int dp[MAXN][10];
int A, B, C[MAXN];
int n;
int main() {
    int T;
    scanf("%d", &T);
    while(T--) {
        scanf("%d%d%d", &n, &A, &B);
        int sum = 0, ans = 0;
        for(int i = 1; i <= n; i++) {
            scanf("%d", &C[i]);
            sum += C[i];
        }

        if((A + B) % 9 != sum % 9) {
            if(sum % 9 == A % 9) ans++;
            if(sum % 9 == B % 9) ans++;
            printf("%d\n", ans);
            continue;
        }

        dp[0][0] = 1;
        for(int i = 1; i <= n; i++) {
            for(int j = 0; j < 9; j++) {
                dp[i][j] = (dp[i-1][j] + dp[i-1][(j - C[i] + 9) % 9]) % MOD;
            }
        }
        printf("%d\n", dp[n][A % 9]);
    }
    return 0;
}