[ABC262D] I Hate Non-integer Number
Demons_Killer
·
·
题解
思路：
考虑动态规划。
由思路可得不选状态转移方程为 $f_{i,j,k}=f_{i+1,j,k}$，选的状态转移方程为 $f_{i,j,k}=f_{i+1,j+1,(k+a_{j})\mod k}$。
# CODE：
```cpp
#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define rep(i,l,r) for(register ll i=(l);i<=(r);i++)
#define PLL pair<ll,ll>
#define PLD pair<ld,ld>
#define FI first
#define SC second
#define MP make_pair
using namespace std;
const ll INF=9223372036854775807;
const ld ERR=1e-12;
const ll N=109,MOD=998244353;
ll n,a[N],f[N][N][N],ans;
int main(){
cin>>n;
rep(i,1,n)cin>>a[i];
rep(i,1,n){
memset(f,0,sizeof(f));
f[1][0][0]=1;
rep(j,1,n)rep(k,0,i)rep(l,0,i-1){
f[j+1][k][l]+=f[j][k][l];
f[j+1][k][l]%=MOD;
if(k!=i)f[j+1][k+1][(l+a[j])%i]+=f[j][k][l],f[j+1][k+1][(l+a[j])%i]%=MOD;
}
ans=(ans+f[n+1][i][0])%MOD;
}
cout<<ans<<endl;
return 0;
}
```