题解：AT_abc262_d [ABC262D] I Hate Non-integer Number

· · 题解

题目简述

给你一个序列，请你取出任意连续元素，组成一个新的序列的平均数为整数的方法数有多少种？

思路

我们知道序列求平均数的方法为 \dfrac{a_1+a_2+\dots+a_i}{i} 其中我们要想让这个算式是整数，就得让 i 能整除 a_1+a_2+\dots+a_i。

这不就是一道动态规划的题目吗？

于是我们设 f_{j,k,l} 为序列 A 中前 j 项选 k 项，他们的和除以 i 的余数为 l。很显然答案是 f_{N,i,0}，初始值 f_{0,0,0}=1。

接着我们设计动态转移方程，当不选这个数，方程为：

f_{j+1,k,d}=f_{j+1,k,d}+f_{j,k,d}

当我们选这个数：

f_{j+1,k+1,(d+a_j\bmod i)}=f_ {j+1,k+1,(d+a_j\bmod i)}+f_{j,k,d}

最后记得模 998244353。

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
int a[105];
int dp[105][105][105];
const int mod=998244353;
signed main() {

    int N;
    cin>>N;
    for(int i=0;i<N;i++)cin>>a[i];
    int ans = 0;
    for(int i=1;i<=N;i++){
        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]%mod;
                    if(k!=i)dp[j+1][k+1][(l+a[j])%i] += dp[j][k][l]%mod;
                }
            }
        }
        ans += dp[N][i][0]%mod;
    }

    cout<<ans%mod<<endl;

    return 0;
}