AtCoder-abc262_d I Hate Non-integer Number

I Hate Non-integer Number

dp

如果能平均分，说明选了 /(n/) 个数字，且其和在 /(n/) 的意义下为 /(0/)

因此考虑用 /(dp/) 跑 /(n/) 次，第 /(i/) 次代表选择 /(i/) 个数字

/(dp[j][k][u]/) 代表前 /(j/) 个数字，选择 /(k/) 个数字，模意义下为 /(u/) 的个数

因此有状态转移方程

/(dp[j][k][u] = dp[j-1][k][u] + dp[j-1][k-1][(u-a_j)/%i]/)

显然转移的话，对于第二维和第三维都要进行转移，因此转移复杂度为 /(O(n^2)/)

总的算法复杂度为 /(O(n^4)/)

我就是算出这个复杂度，然后不敢写，寄

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
using namespace std;
typedef long long ll;
const int maxn = 110;
const ll mod = 998244353;
ll dp[maxn][maxn][maxn];
ll a[maxn];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    for(int i=1; i<=n; i++) cin >> a[i];
    ll ans = 0;
    for(int i=1; i<=n; i++)
    {
        for(int j=0; j<=n; j++)
            for(int k=0; k<=i; k++)
                for(int u=0; u<i; u++)
                    dp[j][k][u] = 0;
        for(int i=0; i<=n; i++) dp[i][0][0] = 1;
        for(int j=1; j<=n; j++)
        {
            for(int k=i; k; k--)
            {
                for(int u=0; u<i; u++)
                {
                    dp[j][k][u] = (dp[j-1][k][u] + dp[j-1][k-1][(u-a[j]%i+i)%i]) % mod;
                    int x = 0;
                    x += 1;
                }
            }
        }
        ans += dp[n][i][0];
    }
    cout << ans % mod << endl;
    return 0;
}