|
//n ^ 3
#include<iostream>
using namespace std;
#define int long long
const int M = 998244353;
const int N = 1005;
int C[N][N];
int f[5][N];
int n, a, b, c, d;
void init(){
for(int i = 0;i < N;i ++){
C[i][0] = 1;
for(int j = 1;j <= i;j ++){
C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % M;
}
}
}
signed main(){
cin.tie(0) -> ios::sync_with_stdio(0);
cin >> n >> a >> b >> c >> d;
init();
int ans = 0;
int limit = min(a, min(b, min(c, min(d, n / 4))));
for(int i = 0;i <= limit;i ++){
int rev = n - 4 * i;
int lim[5] = {0, a - i, b - i, c - i, d - i};
for(int j = 0;j <= 4;j ++){
for(int k = 0;k <= rev;k ++){
f[j][k] = 0;
}
}
f[0][0] = 1;
for(int k = 1;k <= 4;k ++){
for(int j = 0;j <= rev;j ++){
for(int x = 0;x <= min(j, lim[k]);x ++){
f[k][j] = (f[k][j] + f[k - 1][j - x] * C[j][x] % M) % M;
}
}
}
int way = C[n - 3 * i][i] * f[4][rev] % M;
if(i & 1) ans = (ans - way + M) % M;
else ans = (ans + way) % M;
}
cout << ans << '\n';
return 0;
}
//n ^ 2 log n
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
#define ll long long
const int MOD = 998244353;
const int MAXN = 4005;
const int G = 3;
const int Gi = 332748118;
ll n, num[4];
ll fact[MAXN], inv[MAXN];
int rev[MAXN << 2];
ll A[MAXN << 2], B[MAXN << 2], Poly[MAXN << 2];
ll qpow(ll a, ll b){
ll res = 1;
while(b){
if(b & 1) res = res * a % MOD;
a = a * a % MOD;
b >>= 1;
}
return res;
}
void NTT(ll A[], int len, int op){
for(int i = 0;i < len;i ++) if(i < rev[i]) swap(A[i], A[rev[i]]);
for(int mid = 1;mid < len;mid <<= 1){
ll Wn = qpow(op == 1 ? G : Gi, (MOD - 1) / (mid << 1));
for(int i = 0;i < len;i += (mid << 1)){
ll wk = 1;
for(int j = 0;j < mid;j ++, wk = wk * Wn % MOD){
ll x = A[i + j], y = wk * A[i + j + mid] % MOD;
A[i + j] = (x + y) % MOD;
A[i + j + mid] = (x - y + MOD) % MOD;
}
}
}
if(op == -1){
ll invL = qpow(len, MOD - 2);
for(int i = 0;i < len;i ++) A[i] = A[i] * invL % MOD;
}
}
void NTT_init(int len){
int L = 0; while((1 << L) < len) L ++;
for(int i = 0;i < len;i ++) rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (L - 1));
}
void init(){
fact[0] = 1;
for(int i = 1;i < MAXN;i ++) fact[i] = fact[i - 1] * i % MOD;
inv[MAXN - 1] = qpow(fact[MAXN - 1], MOD - 2);
for(int i = MAXN - 2;i >= 0;i --) inv[i] = inv[i + 1] * (i + 1) % MOD;
}
ll C(int n, int m){
if(m < 0 || m > n) return 0;
return fact[n] * inv[m] % MOD * inv[n - m] % MOD;
}
ll NFT(int k){
int m = n - 4 * k;
if(m < 0) return 0;
int len = 1;
while(len <= 4 * m) len <<= 1;
NTT_init(len);
for(int i = 0;i < len;i ++) Poly[i] = 1;
for(int i = 0;i < 4;i ++){
int limit = num[i] - k;
for(int j = 0;j < len;j ++) A[j] = (j <= limit && j <= m) ? inv[j] : 0;
NTT(A, len, 1);
for(int j = 0;j < len;j ++) Poly[j] = Poly[j] * A[j] % MOD;
}
NTT(Poly, len, -1);
return C(n - 3 * k, k) * Poly[m] % MOD * fact[m] % MOD;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
init();
cin >> n >> num[0] >> num[1] >> num[2] >> num[3];
ll ans = 0;
int lim_k = min({(ll)n / 4, num[0], num[1], num[2], num[3]});
for(int k = 0;k <= lim_k;k ++){
ll res = NFT(k);
if(k & 1) ans = (ans - res + MOD) % MOD;
else ans = (ans + res) % MOD;
}
cout << ans << '\n';
return 0;
}
题目4398 孤独摇滚！
 1
评论
2026-05-04 16:45:04
|
|
|
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 5 * 1e5 + 5;
ll a[N], b[N], ans, n, k;
struct node{
ll v;
int cnt;
bool operator>(const node& o)const{
if(v != o.v) return v > o.v;
return cnt < o.cnt;
}
};
int check(ll mid){
priority_queue<node, vector<node>, greater<node>> A;
priority_queue<node, vector<node>, greater<node>> B;
int cnt = 0;
ans = 0;
for(int i = 1;i <= n;i ++){
A.push({a[i] + mid, 1});
node op1 = {A.top().v + b[i], A.top().cnt};
node op2 = B.empty() ? node{(ll)2e18, 0} : node{B.top().v + b[i], B.top().cnt};
bool flag = (op1.v < op2.v) || (op1.v == op2.v && op1.cnt > op2.cnt);
node chose = flag ? op1 : op2;
if(chose.v <= 0){
ans += chose.v;
cnt += chose.cnt;
if(flag) A.pop();
else B.pop();
B.push({-b[i], 0});
}
}
return cnt;
}
int main(){
cin >> n >> k;
for(int i = 1;i <= n;i ++) {
cin >> a[i];
}
for(int i = 1;i <= n;i ++){
cin >> b[i];
}
ll l = -1e15, r = 1e15, C = r;
while(l <= r){
ll mid = (l + r) >> 1;
if(check(mid) >= k){
C = mid;
l = mid + 1;
}
else{
r = mid - 1;
}
}
check(C);
cout << ans - k * C << '\n';
return 0;
}
题目4396 Ave Mujica
1
评论
2026-05-04 16:44:00
|
|
|
#include<iostream>
using namespace std;
#define int long long
const int M = 998244353;
const int K = 305;
const int N = 2 * 1e5 + 5;
int C[K][K];
int a;
int S[K];
int n, k;
int qpow(int a, int b){
int res = 1;
while(b){
if(b & 1) (res *= a) %= M;
(a *= a) %= M;
b >>= 1;
}
return res;
}
void init(){
for(int i = 0;i <= k;i ++){
C[i][0] = 1;
for(int j = 1;j <= i;j ++){
C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % M;
}
}
}
signed main(){
cin >> n >> k;
for(int i = 1;i <= n;i ++){
cin >> a;
int cnt = 1;
for(int x = 0;x <= k;x ++){
S[x] = (S[x] + cnt) % M;
cnt = (cnt * a) % M;
}
}
init();
for(int x = 1;x <= k;x ++){
int ans = 0;
for(int i = 0;i <= x;i ++){
ans = (ans + (C[x][i] * S[i]) % M * S[x - i] % M) % M;
}
ans = (ans + M - qpow(2, x) * S[x] % M) % M;
cout << ans * qpow(2, M - 2) % M << '\n';
}
return 0;
}
题目4397 组一辈子乐队
1
评论
2026-05-04 16:43:20
|
|
|
Pro4359 淘汰赛 题解淘汰赛：区间最大值贪心解法一、 题目大意
一共有 2n 个国家参加单场淘汰赛，两两配对比赛，能力值高的一方必胜，一直比赛直到决出冠军。比赛顺序：1 和 2 比、3 和 4 比…… 相邻编号两两对决，胜者晋级继续淘汰赛。已知所有国家的能力值互不相同，求最终亚军的国家编号 样例输入 n=3，总共有 23=8 个国家。8 个国家能力依次为：1 号：4，2 号：2，3 号：3，4 号：1，5 号：10，6 号：5，7 号：9，8 号：7整个赛程里冠军是 5 号，和冠军在决赛对战的对手就是亚军，也就是1 号，所以输出 1 二、 思路解析（核心部分）第一层：解题基石
本题不需要模拟完整淘汰赛全过程，仅用基础遍历即可解决 1.淘汰赛的赛程结构是严格的完全二叉树，所有队伍被均匀分成左右两个半区 2.冠军必然是两个半区各自的最强者之一 3.亚军一定是另外一个半区里的最强队伍 4.数据范围 n≤7，总人数最多 2^7=128，数据极小，暴力遍历完全足够 第二层：思维脉络
1.计算总参赛队伍数量:tot=2^n 2.将所有队伍平均划分为左半区、右半区两部分 3.分别遍历两个半区，找出左半区能力最强的编号、右半区能力最强的编号 4.两个最强队伍中，能力较弱的那一个，就是最终亚军 本题无动态规划，无需 DP 数组定义 可设： maxL = 左半区最大能力值，idL = 对应编号 maxR = 右半区最大能力值，idR = 对应编号决赛对决 则： max(maxL,maxR) 对应编号为冠军 min(maxL,maxR) 对应编号为亚军 第三层：难点与陷阱
1.浮点数精度使用错误：使用 pow(2,n) 计算队伍总数，pow 是浮点函数，会出现 128 变成 127.9999 的误差，导致数组越界 2.错误模拟全程比赛：当一层层模拟晋级时，代码写复杂还容易写错 3.混淆能力值和国家编号，只存数值忘记记录原始编号 4.数组下标混乱，左右半区分割错误 观察淘汰赛树形结构发现规律：亚军只会是决赛输家，而决赛双方分别是左右两大区的最强者，因此完全不需要模拟全程比赛，只需要找两个大区最大值，弱者即为答案，思路大幅简化。 三、 代码实现
四、 总结与反思（升华部分）
1.透过赛程结构找规律，不用死板模拟全过程，淘汰赛树形结构有固定结论：亚军是决赛对手，即另一半区最强者 2.规避 pow() 函数浮点误差的技巧：用位运算 1<<n 计算 2n 3.理解单胜者淘汰赛、完全二叉树比赛模型的通用性质 本题结论可以迁移到所有相邻配对、强者必胜、单败淘汰赛题目： 1.求决赛两支队伍 2.求四强、八强分别是谁 3.同类体育竞赛赛程推理题目。 1.可以封装函数实现通用区间最大值查找，代码复用性更高 2.可以扩展写法，模拟完整每一轮晋级过程，输出每一轮晋级名单，验证规律 3.若题目改为弱者获胜，只需修改大小比较符号即可，整体思路不变。 五、 推荐题目
题目4359 淘汰赛
AAAAAAAAAA
5
评论
2026-04-18 14:50:46
|
|
|
3139. [HSOI 2019] HS的新题 - COGS显然随机数据, 考虑珂朵莉树.
以下均在
注意要开
操作
|
|
|
点击查看《Cookies》题解详情附件1、解法1-dfs 程序填空#include <bits/stdc++.h>
using namespace std;
const int N = ___; // 最大孩子数
___ INF = 1e18; // 无限大值，用于初始化最小怨气
int n, m; // 孩子数、饼干总数
int g[___], idx[___]; // g[i]：孩子i的贪婪度；idx[i]：排序后第i个孩子的原始索引
int c[___]; // 当前分配方案，c[i]表示排序后第i个孩子分到的饼干数
int best_c[___]; // 最优分配方案
long long min_anger = ___; // 最小怨气总和
bool cmp(int a,int b) {
return ___;
}
/*
* 深度优先搜索枚举所有可能的分配方案
* pos：当前正在分配的孩子位置（排序后的索引）
* remaining：剩余的饼干数
* current_anger：当前已经产生的怨气（只考虑前pos-1个孩子）
*/
void dfs(int pos, int remaining, long long current_anger) {
// 如果所有孩子都已分配且饼干刚好用完，检查是否找到更优解
if (pos == ___) { //得到一种分配方案
if (remaining == ___ && current_anger ___ min_anger) {
___ // 更新最小怨气
for (int i = 1; i <= n; ++i) ___; // 保存最优分配方案
}
___
}
// 确定当前孩子饼干数的上限：
// 1. 不能超过剩余饼干数（因为后面每个孩子至少1块饼干，所以剩余饼干数必须至少为n-pos）
// 2. 为了保持分配序列非递增（这是最优解的性质），不能超过前一个孩子的饼干数（如果pos>1）
int max_val = ___; // 至少给后面每个孩子留 1 块饼干
if (pos > 1) max_val = min(___, ___); // 非递增约束
// 枚举当前孩子的饼干数（从大到小枚举，有助于更快找到较优解）
for (int val = ___; val >= 1; --val) {
c[pos] = ___; // 尝试分配 val 块饼干给当前孩子
// 计算当前孩子的怨气：统计前 pos-1 个孩子中饼干数大于 val 的数量
int a_i = ___;
for (int j = 1; j < pos; ++j) {
if (___) ___;
}
long long new_anger = ___ + 1LL * ___;
// 如果新怨气已经超过当前最优解，剪枝，不再继续搜索
if (___) ___;
// 递归搜索下一个孩子，剩余饼干数减少val，怨气更新为new_anger
dfs(___, ___, ___);
}
}
int main() {
freopen("Cookies.in", "r", stdin);
freopen("Cookies.out", "w", stdout);
cin >> n >> m; // 输入孩子数和饼干总数
// 输入每个孩子的贪婪度
for (int i = 1; i <= n; ++i) {
cin >> g[i];
idx[i] = ___; // 记录原始索引
}
// 将孩子按贪婪度降序排序（存在最优解使得分配序列与贪婪度降序对应）
sort(idx ___, idx ___, ___);
// 将贪婪度数组按照排序后的顺序重新排列，便于搜索时使用
int sorted_g[N];
for (int i = 1; i <= n; ++i) {
sorted_g[i] = ___;
}
memcpy(g, sorted_g, sizeof(sorted_g));
// 开始深度优先搜索
dfs(___, ___, ___);
// 输出最小怨气总和
cout << min_anger << endl;
// 将最优分配方案还原到原始孩子顺序
int final_ans[N];
for (int i = 1; i <= n; ++i)
final_ans[___] = ___;
// 输出每个孩子分到的饼干数
for (int i = 1; i <= n; ++i) {
cout << ___ << " ";
}
cout << endl;
return 0;
}
附件2、解法1-dp 程序填空#include <bits/stdc++.h>
using namespace std;
const int N = ___; // 最大孩子数
const int M = ___; // 最大饼干数
const long long INF = ___; // 无穷大，用于初始化DP
struct Child {
int id; // 原始编号
long long g; // 贪婪度
} children[___]; // 存储孩子信息
int n, m; // 孩子数量和饼干总数
long long g[___]; // 排序后的贪婪度数组
long long prefixSum[___]; // 贪婪度前缀和，用于快速计算区间和
long long dp[___][___]; // DP数组：dp[i][j]表示前i个孩子分配j块饼干的最小怨气
// 记录转移路径的结构体
struct Path {
int type; // 转移类型：0-整体加一，1-新增层级
int param; // 参数：type=0 时无用，type=1 时表示层级长度
int prev_i, prev_j; // 前一个状态
} path[___][___];
int allocation[___]; // 最终分配方案（排序后的顺序）
int originalAns[___]; // 最终分配方案（原始顺序）
/**
* 比较函数：按贪婪度降序排序
* 原理：根据交换论证，最优解中贪婪度大的孩子饼干数不少于贪婪度小的孩子
* 所以我们可以将孩子按贪婪度降序排序，然后只考虑非递增的分配方案
*/
bool compareChildren(___ a, ___ b) {
return ___;
}
/**
* 功能：回溯构造分配方案
* i 当前孩子数
* j 当前饼干数
*
* 从最终状态(n, m)开始回溯：
* 1. 如果是从整体加一转移过来的，说明前 i 个孩子的饼干数都加了 1
* 2. 如果是从新增层级转移过来的，说明最后 param 个孩子饼干数设为 1
*/
void reconstruct(int i, int j) {
// 记录每个孩子的基础饼干数（1或0）
vector<int> base(___, ___);
// 记录每个孩子额外加的饼干数（通过整体加一操作）
vector<int> add(___, ___);
// 从最终状态开始回溯，直到处理完所有孩子
while (___) {
Path p = path[___][___];
if (___) { // 类型0：整体加一转移
// 说明当前状态是通过给前 i 个孩子每人加一块饼干得到的
// 所以给前 i 个孩子的 add 值都加 1
for (int ___) {
add___;
}
} else { // 类型1：新增层级转移
// 说明最后 p.param 个孩子（从 i-p.param+1 到 i）饼干数设为 1
int len = ___;
for (int t = ___; t <= ___; t++) {
base[t] = ___; // 这些孩子的基础饼干数为 1
}
}
// 回溯到前一个状态
i = p.___;
j = ___
}
// 合并基础值和额外值，得到最终分配方案
for (int t = 1; t <= n; t++) allocation[t] = ___
}
int main() {
// freopen("Cookies.in", "r", stdin);
// freopen("Cookies.out", "w", stdout);
// 输入孩子数量和饼干总数
cin >> n >> m;
if (m % n == 0) {//特殊情况
___
return 0;
}
// 输入每个孩子的贪婪度
for (int i = 1; i <= n; i++) {
cin >> children[i].___;
children[i].id = ___; // 记录原始编号
}
/****************************************************************
* 第一步：按贪婪度降序排序
*
* 为什么需要排序？
* 1. 根据交换论证，最优解中贪婪度大的孩子饼干数不少于贪婪度小的孩子
* 2. 排序后，我们可以假设分配序列是非递增的，大大减少搜索空间
* 3. 这样我们只需要考虑满足 c[1] >= c[2] >= ... >= c[n] 的方案
****************************************************************/
sort(___, ___, ___);
// 提取排序后的贪婪度，并计算前缀和
for (int i = 1; i <= n; i++) {
g[i] = ___;
prefixSum[i] = ___;
// prefixSum[i] = g[1] + g[2] + ... + g[i]，用于快速计算区间和
}
/****************************************************************
* 第二步：动态规划初始化
*
* dp[i][j] 表示前 i 个孩子（排序后）分配 j 块饼干的最小怨气
* 初始状态：
* dp[0][0] = 0: 0 个孩子分配 0 块饼干，怨气为 0
* 其他状态设为无穷大，表示不可达
****************************************************************/
for (int i = ___; i <= ___; i++) {
for (int j = ___; j <= ___; j++) dp[i][j] = ___; //状态初始化
}
dp[___][___] = ___; //边界状态
/****************************************************************
* 第三步：动态规划状态转移
*
* 考虑两种情况：
* 1. 整体加一转移（对应所有孩子饼干数都大于1）
* 如果给前 i 个孩子每人加一块饼干，怨气不变
* 转移：dp[i][j] = dp[i][j-i] (前提：j >= i)
*
* 2. 新增层级转移（对应最后 len 个孩子饼干数为 1）
* 设最后 len 个孩子饼干数为 1，前面 i-len 个孩子饼干数大于 1
* 这 len 个孩子每人都会产生怨气：每个孩子前面有 (i-len) 个孩子饼干数多于他
* 总怨气增加：(i-len) * (g[i-len+1] + ... + g[i])
* 转移：dp[i][j] = min{ dp[i-len][j-len] + (i-len)*(sum[i]-sum[i-len]) }
*
* 其中len从 1 到 i，表示最后一个层级（饼干数为 1）的孩子数量
****************************************************************/
for (int i ___) { //阶段
for (int j ___) { // j 至少为 i，因为每人至少一块饼干
// 情况1：整体加一转移
// 如果 j>=i，说明可以从前 i 个孩子每人少一块饼干的状态转移过来
if (j ___ i && dp[i][___] ___ dp[i][j]) {
dp[i][j] = dp[___][___];
path[i][j] = {0, 0, ___, ___}; // 记录转移路径
}
// 情况2：新增层级转移
// 枚举最后一个层级的长度 len（即饼干数为 1 的孩子数量）
for (int len = ___; len <= ___; len++) {
if (j >= ___) { // 确保有足够的饼干
// 计算新增的怨气
// (i-len) 是前面饼干数大于 1 的孩子数量
// (prefixSum[i] - prefixSum[i-len]) 是最后 len 个孩子的贪婪度之和
long long newAnger = dp[___][___] + (___) * (prefixSum[___] - prefixSum[___]);
if (newAnger ___ dp[i][j]) {
dp[i][j] = ___;
path[i][j] = {___, ___, ___, ___}; // 记录转移路径
}
}
}//for len
}//for j
}//for i
/****************************************************************
* 第四步：输出最小怨气
*
* dp[n][m] 就是前 n 个孩子（所有孩子）分配 m 块饼干的最小怨气
****************************************************************/
cout << ___;
/****************************************************************
* 第五步：回溯构造分配方案
*
* 通过记录的转移路径，从最终状态(n, m)开始回溯，构造出具体的分配方案
* 有两种类型的转移：
* 1. 整体加一：给前i个孩子每人加一块饼干
* 2. 新增层级：最后len个孩子饼干数设为1
****************************************************************/
reconstruct(n, m);
/****************************************************************
* 第六步：将排序后的分配方案映射回原始顺序
*
* 因为我们是按贪婪度降序排序后进行的DP和方案构造
* 所以需要将分配方案映射回原始的孩子顺序
****************************************************************/
for (int i = 1; i <= n; i++) {
// children[i].id 是排序后第 i 个孩子的原始编号
// allocation[i] 是排序后第 i 个孩子分到的饼干数
originalAns[___] = ___;
}
// 输出每个孩子的饼干数（按原始顺序）
for (int ___) cout << ___ << " ";
___
return 0;
}
题目3155 Cookies
1
评论
2026-04-09 21:26:17
|