题解

dfs 是很显然的，考虑优化。

显然的，优化 dfs，第一种是记忆化，第二种是 dp，记忆化没写过，直接考虑 dp。

令 $dp_i$ 表示取模后为 $i$ 的方案数量，容易得到 $dp_i=dp_{i-a_j}$。

注意负数，随时取模。（赛时没取模喜提罚时）

Code:

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll MAXN=1e6+16,MOD=998244353;
ll n;
ll dp[21],a[MAXN],t[21];
int main(){
    cin>>n;
    for(ll i=1;i<=n;i++){
        cin>>a[i];
        a[i]%=21;
    }
    dp[0]=1;
    for(ll i=1;i<=n;i++){
        for(ll j=0;j<21;j++) t[j]=dp[((j-a[i])%21+21)%21];
        for(ll j=0;j<21;j++){
            dp[j]+=t[j];
            if(dp[j]>=MOD) dp[j]-=MOD;
        }
    }
    cout<<dp[0];
    return 0;
}