牛客多校第七场 J 题解

J 题题意：求长度为 $nn$，且每个数字都在 $[0,k-1][0,k-1]$，使得区间连续和为 $kk$ 倍数的子区间有 $tt$ 个的序列个数。$n,k\le 64n,k\; \backslash leq\; 64$，$t\le {\displaystyle \frac{n(n-1)}{2}}t\; \backslash leq\; \backslash dfrac\{n(n-1)\}\{2\}$。

解法：区间连续和很容易想到前缀和，那么问题转化为前缀和的差的倍数有 $tt$ 个的序列个数。又数字范围在 $[0,k-1][0,k-1]$，因而前缀和序列取模后也可以一一对应原序列。同时，区间 $[i,j][i,j]$ 的连续和为 $kk$ 的倍数要求前缀和序列中 $s_{i-1}=s_{j}s\_\{i-1\}=s\_j$，那么问题进一步被转化为，长度为 $n+1n+1$ 的序列，第一个数字强制为 $00$，后面每个数字范围在 $[0,k-1][0,k-1]$，使得 ${\displaystyle \sum _{i=0}^{k-1}\frac{c_i(c_i-1)}{2}=t}\backslash displaystyle\; \backslash sum\_\{i=0\}^\{k-1\}\backslash dfrac\{c\_i(c\_i-1)\}\{2\}=t$ 的序列个数，其中 $c_{i}c\_i$ 为数字 $ii$ 的出现次数，那么简单背包转移即可：${\displaystyle f_{i,j,l}\leftarrow \sum _{k=0}^j{f}_{i-1,j-k,l-\frac{k(k-1)}{2}}\left(\genfrac{}{}{0px}{}{n-j+k}{k}\right)}\backslash displaystyle\; f\_\{i,j,l\}\; \backslash leftarrow\; \backslash sum\_\{k=0\}^jf\_\{i-1,j-k,l-\backslash frac\{k(k-1)\}\{2\}\}\; \{n-j+k\backslash choose\; k\}$。总复杂度 $\mathcal{O}(nkt)\backslash mathcal\; O(nkt)$。

#include <bits/stdc++.h>
using namespace std;
const int N = 100, mod = 998244353;
int f[N + 5][N + 5][N * N + 5];
int S[N + 5], C[N + 5][N + 5];
int main()
{
    int n, k, t;
    scanf("%d%d%d", &n, &k, &t);
    for (int i = 0; i <= n;i++)
        C[i][0] = C[i][i] = 1;
    for (int i = 1; i <= n;i++)
        for (int j = 1; j < i;j++)
            C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % mod;
    for (int i = 1; i <= n + 5; i++)
        S[i] = i * (i - 1) / 2;
    f[0][0][0] = 1;
    for (int i = 0; i < k;i++)
        for (int j = 0; j <= n;j++)
            for (int l = 0; j + l <= n;l++)
                for (int s = 0; s + S[l + (!i)] <= t;s++)
                    f[i + 1][j + l][s + S[l + (!i)]] = (f[i + 1][j + l][s + S[l + (!i)]] + 1ll * f[i][j][s] * C[n - j][l] % mod) % mod;
    printf("%d", f[k][n][t]);
    return 0;
}