每日一题：Classroom （计数DP)

题目链接：Problem - F - Codeforces

题意：

有 n 个学生，从1到n，要把他们分成连续的若干组（组数量不固定），满足 3 个要求：（1 ≤ n ≤ 5 ∗ 1e3)

1.第一组从第 1 个学生开始，最后一组到第 n 个学生结束，组内为连续整数，组间也需要连续；

2.第 1 组的总和能被 1 整除，第 2 组的总和能被 2 整除，……，第 k 组的总和能被 k 整除（k 是组的序号）；例如：1 2 3 4 5可分为[1] [2 3 4 5] 或 [1 2] [3 4 5]等。

计算这样的分组方法有多少种，结果对 10⁹+7 取模。

核心思路：

定义dp[i][j]表示：将前j个学生分割成i个组，且满足所有条件的方法数。

初始化：dp[1][k] = 1（k≥1）

ans =∑（dp[i][n]）（i 从 1 到 n)

对于j ≥ 2，dp[j][k] = ∑（dp[j-1][t]），其中t满足：t < k（保证第 j 组是[t+1, k]，连续）并且第 j 组的和sum(t+1, k)能被j整除。但直接写会超时。

转移方程中 t 同时也满足sum(1,t)与sum(1,k)关于j同余，可以用一个数组维护，复杂度O(n2)。

#include <bits/stdc++.h> using namespace std; #define int long long const int mod = 1e9 + 7; void solve() { int n; cin >> n; vector<int> dp(n + 1, 1); int ans = 1; for (int i = 2; i <= n; i++) { vector<int> f(i + 1), ndp(n + 1); int tem = 0; for (int j = 1; j <= n; j++) { tem = (tem + j) % i; ndp[j] = f[tem]; f[tem] = (f[tem] + dp[j]) % mod; } dp = ndp; (ans += dp[n]) %= mod; } cout << ans; } signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); int t = 1; // cin >> t; while (t--) solve(); return 0; }