Contest Duration: - (local time) (100 minutes) Back to Home
Official

## D - I Hate Non-integer Number Editorial by en_translator

When $$x_1,\ldots,x_i$$ are chosen, the average is $$\frac {x_1+\ldots+x_i}{i}$$. This is integer if and only if the numerator, i.e. the sum of the chosen terms, is a multiple of $$i$$.

Here, consider the following $$\mathrm {dp}$$ for each $$i=1,\ldots,N$$. (DP stands for Dynamic Programming.)

• $$\mathrm{dp}_{j,k,l}$$: the number of ways, modulo $$998244353$$, to choose $$k$$ terms from the first $$j$$ terms of $$A$$ such that the remainder by $$i$$ of the sum of the chosen terms equals $$l$$

Then the answer is the sum of $$\mathrm{dp}_{N,i,0}$$.
For the transitions of $$\mathrm{dp}$$, please refer to the sample code. (The $$23$$-rd corresponds to choosing $$a_j$$, and the $$24$$-th corresponds not choosing.)

### Sample code (C++)

#include <bits/stdc++.h>
#include <atcoder/modint>
using namespace std;
using namespace atcoder;
using mint = modint998244353;

int main() {

int N;
cin>>N;

vector<int> a(N);
for(int i=0;i<N;i++)cin>>a[i];

mint ans = 0;

for(int i=1;i<=N;i++){
vector dp(N+1,vector(i+1,vector<mint>(i,0)));
dp[0][0][0] = 1;
for(int j=0;j<N;j++){
for(int k=0;k<=i;k++){
for(int l=0;l<i;l++){
dp[j+1][k][l] += dp[j][k][l];
if(k!=i)dp[j+1][k+1][(l+a[j])%i] += dp[j][k][l];
}
}
}
ans += dp[N][i][0];
}

cout<<ans.val()<<endl;

return 0;
}


posted:
last update: