ABC262D – I Hate Non-integer Number（三维线性DP）

题目链接：ABC262D

题意：

给出$n$个正整数，选出若干个数字，求这若干个数字的平均值是正整数的方案数，答案对998244353取模。

思路：

一开始想着的是dp[i][j][k]表示前i个数选择j个数其中和为k的方案数。

k会很大，所以需要考虑取模，存储和对j取模。

不选a[i]的转移方程有dp[i][j][k] = dp[i-1][j][k]，但是如果选a[i]的时候有些难办，现在sum=k那上一个状态如何得来？(sum-a[i])%(j-1)=?这个不好办。所以这个$O(n^3)$方法不太行。

定义dp[j][k][l]为把i作为分母（说明要选i个数），前j个数，选择k个，和模i为l的方案数。i枚举的是子集大小，%i的意义就是最后要除以的那个i。

• 不选择a[j]：dp[j+1][k][l] += dp[j][k][l];
• 选择a[j]：dp[j+1][k+1][(l+a[j])%i] += dp[j][k][l];需要满足k<i，因为这是递推的

代码

mint dp[N][N][N],ans;
inline void Case_Test()
{
    cin>>n;
    for (int i=0;i<n;i++)
        cin>>a[i];
    for (int i=1;i<=n;i++)
    {
        memset(dp,0,sizeof dp);
        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;
}