[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;
}