abc262-D（dp）

D - I Hate Non-integer Number Editorial

 / 

---

Time Limit: 2.5 sec / Memory Limit: 1024 MB

Score : 400400 points

Problem Statement

You are given a sequence of positive integers A=(a_1,\ldots,a_N)A=(a1​,…,aN​) of length NN.
There are (2^N-1)(2N−1) ways to choose one or more terms of AA. How many of them have an integer-valued average? Find the count modulo 998244353998244353.

Constraints

• 1 \leq N \leq 1001≤N≤100
• 1 \leq a_i \leq 10^91≤ai​≤109
• All values in input are integers.

---

Input

Input is given from Standard Input in the following format:

NN
a_1a1​ \ldots… a_NaN​

Output

Print the answer.

---

Sample Input 1 Copy

Copy

3
2 6 2

Sample Output 1 Copy

Copy

6

For each way to choose terms of AA, the average is obtained as follows:

• If just a_1a1​ is chosen, the average is \frac{a_1}{1}=\frac{2}{1} = 21a1​​=12​=2, which is an integer.

• If just a_2a2​ is chosen, the average is \frac{a_2}{1}=\frac{6}{1} = 61a2​​=16​=6, which is an integer.

• If just a_3a3​ is chosen, the average is \frac{a_3}{1}=\frac{2}{1} = 21a3​​=12​=2, which is an integer.

• If a_1a1​ and a_2a2​ are chosen, the average is \frac{a_1+a_2}{2}=\frac{2+6}{2} = 42a1​+a2​​=22+6​=4, which is an integer.

• If a_1a1​ and a_3a3​ are chosen, the average is \frac{a_1+a_3}{2}=\frac{2+2}{2} = 22a1​+a3​​=22+2​=2, which is an integer.

• If a_2a2​ and a_3a3​ are chosen, the average is \frac{a_2+a_3}{2}=\frac{6+2}{2} = 42a2​+a3​​=26+2​=4, which is an integer.

• If a_1a1​, a_2a2​, and a_3a3​ are chosen, the average is \frac{a_1+a_2+a_3}{3}=\frac{2+6+2}{3} = \frac{10}{3}3a1​+a2​+a3​​=32+6+2​=310​, which is not an integer.

Therefore, 66 ways satisfy the condition.

---

Sample Input 2 Copy

Copy

5
5 5 5 5 5

Sample Output 2 Copy

Copy

31

Regardless of the choice of one or more terms of AA, the average equals 55.

#include<bits/stdc++.h>
using namespace std;
const int MAXN =1e2 + 10;
const int MOD = 998244353;
long long a[MAXN],n,ans,dp[MAXN][MAXN][MAXN];
int main()
{
    cin >> n;
    for(int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
    for(int s = 1; s <= n; s++)
    {
        memset(dp,0,sizeof dp);
        dp[0][0][0] = 1;
        for(int i = 0; i < n; i++)
        {
            for(int j = 0; j <= s && j <= i; j++)
            {
                for(int k = 0; k < s; k++)
                {
                    dp[i + 1][j][k] += dp[i][j][k];
                    dp[i + 1][j][k] %= MOD;
                    if(j != s)dp[i + 1][j + 1][(k + a[i + 1]) % s] += dp[i][j][k];
                    dp[i + 1][j + 1][(k + a[i + 1]) % s] %= MOD;
                }
            }
        }
        ans += dp[n][s][0];
        ans %= MOD;
    }
    cout << ans;
}