ABC262D 题解

__vector__ · 2022-08-06 18:35:27 · 个人记录

由于知道要讲题的时候，时间不多了，所以题解做的快一些，希望没有问题吧。

题意

给定一个元素个数为 N 的集合，你可以从中选出任意多个元素（但至少选一个）。
问有多少种方式使得选出来的元素总和除以选出来的元素总个数是个整数。

做法

先列一个看完题就能想到的状态：
设 dp_{i,j,k} 代表前 i-1 个数，选了 j 个，总和为 k 的方案数。
dp 主体运行完成之后，对于所有总和为 k 的倍数的方案统计答案。

这个式子超时是一定的。

这个东西，之所以慢，是因为考虑了很多不需要考虑的东西，如总和。

可以发现，对最后有影响的，仅仅是总和取余总数量为 0 的结果。

也就是说，对于统计总和的地方，实际上只需要考虑余数就行了。

新的状态：
设 dp_{i,j,k} 代表前 i-1 个数，当前选了 j 个，总和取余总个数为 k 的方案数。

然后转移就行了。

转喻的过程：
第一层枚举一共要选多少个，记为 num。
里面枚举 i,j,k，进行转移，根据状态定义。
方程：
dp[i+1][j][k]+=dp[i][j][k] 代表这一位不选。

dp[i+1][j+1][(k+a[i])%num]+=dp[i][j][k] 代表选这一位。

第一层循环每枚举一个，就将当前的答案加上，最后输出答案总和。

题外话：

dp[i] 表示 前 i-1 位答案的很奇怪，对吧，那是因为我的设 dp[i] 表示前 i 位的答案的代码因为离奇原因寄了，所以我只写了 dp[i] 表示前 i-1 位答案版本的。

Code

#include <bits/stdc++.h>
using namespace std;
namespace Main
{
    typedef long long ll;
    const ll mod=998244353;
    const int maxn=105;
    ll dp[maxn][maxn][maxn];
    //前 i 位选 j 个
    int a[maxn];
    int n;
    void main()
    {
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
        }
        ll ans=0;
        for(int num=1;num<=n;num++)//一共选多少个
        {
            memset(dp,0,sizeof dp);
            dp[1][0][0]=1;
            for(int i=1;i<=n;i++)
            {
                for(int j=0;j<=num;j++)
                {
                    for(int k=0;k<=num;k++)
                    {
                        dp[i+1][j][k]+=dp[i][j][k];
                        dp[i+1][j][k]%=mod;
                        dp[i+1][j+1][(k+a[i])%num]+=dp[i][j][k];
                        dp[i+1][j+1][(k+a[i])%num]%=mod;
                    }
                }
            }
            ans+=dp[n+1][num][0];
            ans%=mod;
        }
        printf("%lld",ans);
    }
}
int main()
{
    Main::main();
    return 0;
}