郑州百度网站建设上市公司网站分析

郑州百度网站建设,上市公司网站分析,聚美优品网站设计,苏州吴江太湖新城建设局网站题目链接#xff1a;Problem - F - Codeforces 题意#xff1a; 有 n 个学生#xff0c;从1到n#xff0c;要把他们分成 连续的若干组#xff08;组数量不固定#xff09;#xff0c;满足 3 个要求#xff1a;#xff08;1 ≤ n ≤ 5 ∗ 1e3) 1.第一组从第 1 个学…题目链接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] 1k≥1ans ∑dp[i][n]i 从 1 到 n)对于j ≥ 2dp[j][k] ∑dp[j-1][t]其中t满足t k保证第 j 组是[t1, k]连续并且第 j 组的和sum(t1, 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; vectorint dp(n 1, 1); int ans 1; for (int i 2; i n; i) { vectorint 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; }