HDU 5389 Zero Escape

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define ms(arr,a) memset(arr,a,sizeof arr)
/*
50
9 9 9
1 2 3 4 5 6 7 8 9
*/
const int maxn=1e5+5;
const long long mod=258280327;
int arr[maxn];
long long dp[maxn][9];//至少选一个
int mod9(int x)
{
    if(x<0)return x%9+9;
    else return x%9;
}
int main()
{
    int T;scanf("%d",&T);
    while(T--)
    {
        int n,A,B;
        int sum=0;
        scanf("%d%d%d",&n,&A,&B);
        A%=9,B%=9;
        rep(i,1,n)
        {
            scanf("%d",arr+i);
            arr[i]%=9;
            sum+=arr[i];
            sum%=9;
        }
        if(sum!=(A+B)%9)
        {
            if(sum==A||sum==B)printf("1
");
            else printf("0
");
            continue;
        }
        ms(dp,0);
        dp[1][arr[1]]=1;
        rep(i,2,n)
        {
            rep(j,0,8)
            {
                dp[i][j]=(dp[i-1][j]+dp[i-1][mod9(j-arr[i])]+(j==arr[i]))%mod;
            }
        }
        long long ans;
        if(A==0)ans=(dp[n][A]+1)%mod;
        else ans=dp[n][A];
        printf("%lld
",ans);
    }
}