当前位置: 首页 > news >正文

[HZOI] CSP-S模拟29

[HZOI] CSP-S模拟29

今天是 罚坐场 组合数计数专题

早知道昨天就不口嗨了。。。今天直接被真实

T1:一个赢家

我怎么就赢不了呢?

是不简单题。上来直接手膜样例,发现样例二是 6452640 / 7484400 (输入是 6 )

啊?

有点离谱。

很容易地想到去枚举可能的二元组的和。

然后分别去考虑该种情况下的数量。

like 4

1 2 3 4 5 6 7 8

可能的二元组 二元组的和
1-8、2-7、3-6、4-5 9
2-8、3-7、4-6 10
3-8、4-7、5-6 11
4-8、5-7 12
5-8、6-7 13
6-8 14
7-8 15

对于和为 9 来说,对于每一组可能的二元组,不存在只有一组为最大值的情况,所以该种情况下可能的情况是 0 。

相似的,对于和为 10 来说,我们钦定仅有的二元组是 2-8 。

这样,我们可以从后往前看,找所有可匹配的可能解。

1 2 3 4 5 6 7 8

因为已经钦定 2-8 是唯一的最大值了,那么对于 7 来说,只能选择与 1 配对。

以此类推。

我们发现这只有一种可行解。

相似地,对于 3-7、4-6 也只有一种可行解。

之后就可以依次推出所有的情况。

这就是我的赛时思路,但是实现假了,又没有暴力可以打表找规律,于是就寄了。

奋战两个半多小时后,0 pts 带回。

分析一下错误原因:

首先,我想的是正难则反,求出所有的不合法情,但是这里边有重合,所以还需要容斥一下,而我没看出要容斥,然后就 WA 了。

好的,现在我们有了 \(O(n ^ 2)\) 做法,现在考虑如何转化到 \(O(n)\)

没什么好办法,打表找规律呗。

然后就出了。。。

先放赛时错解代码。。。

点击查看代码
#include <bits/stdc++.h>
#define int long long 
#define Blue_Archive return 0
#define con putchar_unlocked(' ')
#define ent putchar_unlocked('\n')
using namespace std;
constexpr int N = 5e6 + 3;
constexpr int INF = 0x3f3f3f3f;
constexpr int mod = 1e9 + 7;int n;
int sum;
int ans;
int s[N];
int fac[N];
int inv[N];inline int read()
{int k = 0,f = 1;char c = getchar_unlocked();while(c < '0' || c > '9'){if(c == '-') f = -1;c = getchar_unlocked();} while(c >= '0' && c <= '9') k = (k << 3) + (k << 1) + c - '0',c = getchar_unlocked();return k * f;
}inline void write(int x)
{if(x < 0) putchar_unlocked('-'),x = -x;if(x > 9) write(x / 10);putchar_unlocked(x % 10 + '0');
}inline int qpow(int a,int b)
{int res = 1;while(b){if(b & 1) res = (res * a) % mod;a = (a * a) % mod;b >>= 1;}return res;
}inline void init()
{fac[0] = inv[0] = 1;for(int i = 1;i <= 2 * n;i ++) {fac[i] = fac[i - 1] * i % mod;inv[i] = qpow(fac[i],mod - 2);}
}inline int C(int n,int m)
{if(n < m) return 0;return fac[n] * inv[n - m] % mod * inv[m] % mod;  
}signed main()
{// freopen("data.in","r",stdin);freopen("data.out","w",stdout); freopen("data.in","r",stdin);freopen("data.out","w",stdout);n = read();init();sum = 1;for(int i = 2;i <= 2 * n;i += 2){sum = (sum * C(i,2)) % mod;s[i / 2] = sum;}ans = 1;for(int i = 2 * n + 2,op,tot,tim = 2 * n - 1;i <= 4 * n - 1;i ++,tim --) // tim / 2 是和为 i 的二元组的个数{op = 1; // 求积tot = n - 1; // 是最多选择个数for(int j = 2 * n;tot >= 1;j --,tot --) // 选择两个二元组,计算剩下的合法排列个数(手膜出来:二元组的选择与其剩余元素的排列无关){op = (op * min(tot,(i - j - 1))) % mod;}ans = (ans + op * (tim / 2) % mod) % mod; // 任选二元组,所以乘一个 C(tim - 2,2)cout << i << ' ' << op * (tim / 2) << '\n';}cerr << ans << '\n';ans = (ans * fac[n]) % mod;cerr << ans << ' ' << sum << '\n'; // !!! ans 求的是不合法的次数ans = ((sum - ans + mod) % mod) * qpow(sum,mod - 2) % mod;write(ans);ent;Blue_Archive;
}
// 4 18 
// 8962 / 10395
// 6452640 / 7484400  // 1031760 // 这是样例 2 

然后是正解

正解代码
#include <bits/stdc++.h>
#define int long long 
#define Blue_Archive return 0
#define con putchar_unlocked(' ')
#define ent putchar_unlocked('\n')
using namespace std;
constexpr int N = 1e7 + 3;
constexpr int INF = 0x3f3f3f3f;
constexpr int mod = 1e9 + 7;int n;
int ans;
int k[N];
int fac[N];
int inv[N];inline int read()
{int k = 0,f = 1;char c = getchar_unlocked();while(c < '0' || c > '9'){if(c == '-') f = -1;c = getchar_unlocked();} while(c >= '0' && c <= '9') k = (k << 3) + (k << 1) + c - '0',c = getchar_unlocked();return k * f;
}inline void write(int x)
{if(x < 0) putchar_unlocked('-'),x = -x;if(x > 9) write(x / 10);putchar_unlocked(x % 10 + '0');
}inline int qpow(int a,int b)
{if(b < 0) return 1;int res = 1;while(b){if(b & 1) res = (res * a) % mod;a = (a * a) % mod;b >>= 1;}return res;
}inline void init()
{fac[0] = inv[0] = 1;for(int i = 1;i <= 2 * n;i ++) {fac[i] = fac[i - 1] * i % mod;inv[i] = qpow(fac[i],mod - 2);}
}inline int C(int n,int m)
{if(n < m) return 0;return fac[n] * inv[n - m] % mod * inv[m] % mod;  
}signed main()
{freopen("card.in","r",stdin);freopen("card.out","w",stdout); // freopen("data.in","r",stdin);freopen("data.out","w",stdout);n = read();init();k[1] = 1;for(int i = 3;i <= 2 * n;i ++) k[i] = k[i - 2] * i % mod;for(int i = 2 * n + 1,tim,tot = 0;i <= 4 * n;i ++,tot ++){tim = 2 * n - (i / 2);ans = (ans + k[2 * (i / 2 - n) - 1] * tim % mod * qpow(tot,tim - 1) % mod) % mod;}ans = ans * qpow(k[2 * n - 1],mod - 2) % mod;write(ans == 0 ? 1 : ans);ent;Blue_Archive;
}
// 8962 / 10395
// 6452640 / 7484400  // 1031760

T2:排列计数(count)

容斥啊容斥,我怎么就不会呢。。。

非常显然的容斥,但是我不会。。。

但其实正解是 dp (也是容斥就是了)

考虑每次加入不合法点集合造成的贡献。

设 dp 状态为 \(dp[i][j]\) 其中 \(i\) 指已经处理了 \(i\) 对不合法点集,\(j\) 代表处理之后的总集合中还有 \(j\) 处不合法的地方。

考虑将现在枚举的第 \(i\)\(cnt\) 个不合法点分成 \(p\) 组后插入总集合。

枚举其中插入 \(v\) 个在原有的不合法集中,使其合法,剩下的插入到总集合中依然不合法。

然后我们就有了转移方程:

\(dp[i + 1][j - v + u] = dp[i + 1][j - v + u] + dp[i][j] * C(cnt - 1,p - 1) * C(j,v) * C(sum - j + 1,p - v)\) 其中 \(sum\) 为总集合中已插入的数的个数。\(u\) 是剩下的数(\(cnt - p\))。

于是就可以十分愉快的A了这道题了。

以后一定好好学容斥!

T3:树上染黑

树形DP

赛时一眼出做法,但是真没时间写了,连暴力都没打完 T_T 。

首先考虑根的贡献。

显然是 \((n - 1)(n - 1)!\) 。(因为一共枚举 \((n - 1)!\) 次,每次都会被计入 \((n - 1)\) 次贡献)

然后考虑每个点的贡献。

对于每个非根的点,其贡献是 \(\sum_{i = 1}^{n - 1}(n - i) \sum_{|S| = i,u \in S} (i - 1)!(n - i - 1)!\)

稍稍化简一下,可得:

\(\sum_{i = 1}^{n - 1}(n - i)!(i - 1)!\sum_{|S| = i,u \in S}\sum_{w \in son_v}[subtree(w) \cap S == \emptyset]\)

\(\sum_{i = 1}^{n - 1}(n - i)!(i - 1)!\sum_{w \in son_v}C(n - 1 - siz_w,i - 1)\)

\(\sum_{i = 1}^{n - 1}(n - i)!(i - 1)!C(n - 1 - siz_w,i - 1)siz_w\)

然后我们发现,这玩意儿好像可以预处理出来

\(g_j = sum_{i = 1}^{n - 1}(n - i)!(i - 1)!C(n - 1 - j,i - 1)j\)

然后接着化简这个式子qwq

\(g_j = sum_{i = 1}^{n - 1}(n - i)!(i - 1)!C(n - 1 - j,i - 1)j\)

\(g_j = j(n - 1 - j)!\sum_{i = 0}^{n - j - 1}j!C(i + j,i)\)

\(g_j = j(n - 1 - j)!j!C(n,n - j - 1)\)

\(g_j = j / (j + 1) · n!\)

终于结束了qwq

对于这个玩意儿直接预处理即可。

然后考虑换根DP。

发现如果将根从 \(u\) 换为 \(v\),实际上是减少了一个以 \(v\) 为子树的贡献,增加了一个除去以 \(v\) 为子树剩下的一坨的贡献。

直接加减就行。

\(dp_v = dp_u - tr_{siz_v} + tr_{n - siz_v}\)

最后,放上代码

点击查看代码
#include <bits/stdc++.h>
#define int long long 
#define add(x,y) to[++ tot] = y,nxt[tot] = h[x],h[x] = tot
#define Blue_Archive return 0
#define con putchar_unlocked(' ')
#define ent putchar_unlocked('\n')
using namespace std;
constexpr int N = 1e6 + 3;
constexpr int M = 2e6 + 7;
constexpr int INF = 0x3f3f3f3f;
constexpr int mod = 998244353;int n;
int tot;
int h[N];
int to[M];
int tr[N];
int nxt[M];
int dis[N];
int fac[N];
int siz[N];
int ans[N];inline int read()
{int k = 0,f = 1;char c = getchar_unlocked();while(c < '0' || c > '9'){if(c == '-') f = -1;c = getchar_unlocked();} while(c >= '0' && c <= '9') k = (k << 3) + (k << 1) + c - '0',c = getchar_unlocked();return k * f;
}inline void write(int x)
{if(x < 0) putchar_unlocked('-'),x = -x;if(x > 9) write(x / 10);putchar_unlocked(x % 10 + '0');
}inline int qpow(int a,int b)
{int res = 1;while(b){if(b & 1) res = (res * a) % mod;a = (a * a) % mod;b >>= 1;}return res;
}inline void init()
{fac[0] = 1;for(int i = 1;i <= n;i ++) fac[i] = fac[i - 1] * i % mod;for(int i = 1;i <= n;i ++) tr[i] = i * qpow(i + 1,mod - 2) % mod * fac[n] % mod;
}inline void dfs1(int x,int f)
{siz[x] = 1;for(int i = h[x];i;i = nxt[i]){if(to[i] == f) continue;dfs1(to[i],x);siz[x] += siz[to[i]];}if(x != 1) ans[1] = (ans[1] + tr[siz[x]]) % mod;else ans[1] = (ans[1] + (n - 1) * fac[n - 1] % mod) % mod;
}inline void dfs2(int x,int f)
{for(int i = h[x];i;i = nxt[i]){if(to[i] == f) continue;ans[to[i]] = (ans[x] - tr[siz[to[i]]] + tr[n - siz[to[i]]] + mod) % mod;dfs2(to[i],x);}
}signed main()
{freopen("black.in","r",stdin);freopen("black.out","w",stdout);// freopen("data.in","r",stdin);freopen("data.out","w",stdout);n = read();init();for(int i = 1,x,y;i < n;i ++){x = read();y = read();add(x,y);add(y,x);}dfs1(1,0);dfs2(1,0);for(int i = 1;i <= n;i ++) write(ans[i]),ent;Blue_Archive;
}

T4:摆放花盆

还没改,赛时打了个 \(O(n ^ 2 logn)\) 的暴力,还打假了。。。

无语至极。。。

菜到离谱。。。

丑陋的赛时错解
#include <bits/stdc++.h>
#define int long long 
#define Blue_Archive return 0
#define con putchar_unlocked(' ')
#define ent putchar_unlocked('\n')
using namespace std;
constexpr int N = 1e6 + 3;
constexpr int INF = 0x3f3f3f3f;
constexpr int mod = 1e9 + 7;int n;struct miku
{int id,l,r,val;bool del;friend bool operator < (miku x,miku y){return x.val == y.val ? x.id < y.id : x.val < y.val;}
}a[N];vector<int> op[N];set<miku> s;
set<miku>::iterator it;inline int read()
{int k = 0,f = 1;char c = getchar_unlocked();while(c < '0' || c > '9'){if(c == '-') f = -1;c = getchar_unlocked();} while(c >= '0' && c <= '9') k = (k << 3) + (k << 1) + c - '0',c = getchar_unlocked();return k * f;
}inline void write(int x)
{if(x < 0) putchar_unlocked('-'),x = -x;if(x > 9) write(x / 10);putchar_unlocked(x % 10 + '0');
}inline void work()
{for(int i = 1;i <= n;i ++) s.insert(a[i]);while(!s.empty()){it = s.begin();miku u = *it;a[u.id].del = 1;write(u.id),con;s.erase(it);for(int v : op[u.id]){if(a[v].del) continue;s.erase(s.find(a[v]));if(a[v].l < u.l && a[v].r > u.r) a[v].val -= u.val;else if(a[v].l <= u.l && a[v].r <= u.r && a[v].r >= u.l){a[v].r = u.l;a[v].val = a[v].r - a[v].l + 1;}else if(a[v].l >= u.l && a[v].r >= u.r && a[v].l <= u.r){a[v].l = u.r;a[v].val = a[v].r - a[v].l + 1;}s.insert(a[v]);}}
}inline void solve_baoli()
{for(int i = 1;i <= n;i ++){for(int j = i + 1;j <= n;j ++){if(a[i].l > a[j].r || a[j].l > a[i].r) continue;op[i].push_back(j);op[j].push_back(i);}}work();exit(0);
}inline void solve_sub()
{sort(a + 1,a + n + 1);for(int i = 1;i <= n;i ++){write(a[i].id),con;}exit(0);
}signed main()
{freopen("gardener.in","r",stdin);freopen("gardener.out","w",stdout);// freopen("data.in","r",stdin);freopen("data.out","w",stdout);n = read();bool sub = 1;for(int i = 1;i <= n;i ++){a[i].id = i;a[i].l = read();a[i].r = read();if(a[i].r != a[i].l + 1) sub = 0;a[i].val = a[i].r - a[i].l + 1;}if(sub) solve_sub();if(n <= 100000) solve_baoli();	for(int i = 1;i <= n;i ++){for(int j = 1;j < i;j ++){if(a[i].l > a[j].r || a[j].l > a[i].r) continue;op[i].push_back(j);op[j].push_back(i);}}work();Blue_Archive;
}
http://www.hskmm.com/?act=detail&tid=28973

相关文章:

  • 初识pytorch:数据标准化及数据增强的transforms
  • 谈程序员如何做好业务
  • 10.11 CSP-S模拟29 改题记录
  • 二三阶行列式
  • 2025 年 10 月 8 日 语文作业
  • CHAR与VARCHAR深度解析:MySQL字符类型选择指南与性能对比
  • vivo霸榜背后:以技术打赢用户保卫战
  • 国庆期间做题记录
  • 02020508 EF Core高级08-表达式树、Expression和委托的关系、查看表达式树结构、AST、手动创建表示树、工厂方法
  • UnitTask中的Forget()与 CTS
  • commons-net - 详解
  • 12 种 Pandas 测试技巧,让数据处理少踩坑
  • 02020505 EF Core高级05-实体的5种状态、EntityEntry、AsNoTracking、实体状态跟踪
  • securityCTF 2025 pwn方向题解
  • 02020507 EF Core高级07-悲观并发控制、乐观并发控制、EF Core连接MySQL、RowVersion
  • linux防火墙操作命令
  • 02020506 EF Core高级06-EF Core批量删除更新插入、全局筛选器、软删除、全局筛选的性能问题
  • 机器学习社会影响与导航系统研究
  • ubuntu24.04 desktop 安装vnc远程桌面(亲测)
  • 完整教程:游标查询在对话历史场景下的独特优势
  • [论文笔记] A Contemporary Survey of Large Language Model Assisted Program Analysis
  • 251011
  • 一种整理HTML和JS代码的方法
  • 元推理框架,是人类文明的《神农本草经》,源于自指自洽的觉悟与洗礼
  • SSL/TLS加密算法:守护网络通信的安全框架
  • 未来计划
  • 【程序员必看】MySQL数据类型全解析:选错类型性能直接掉80%!
  • NOIP2023
  • 理解WPF Stylet中Command=“{s:Action 方法名}“的设计与实现 - 实践
  • 2025环氧地坪漆厂家推荐:常州新禾,品质保证施工无忧!