尧图网站建设 免费方案咨询
ARTICLE DETAIL

资讯详情

深耕网站建设、视觉设计与SEO优化的一线实战洞察。

首页/资讯中心/资讯详情

计数题 - L

发布时间：2026/8/10 18:57:24 尧图网站建设
计数题 - L

计数题

P1350 车的放置

link

Description

给定一个这样的棋盘：

图片

求在棋盘上放置 \(k\) 个互不攻击的车的方案数对 \(10^5 +3\) 取模的结果。

\(1 \le a,b,c,d,k \le 10^3\)。

Solution

显然要从低往高考虑，也就是从右往左考虑。

设 \(dp_{i,j}\) 表示前 \(i\) 列，放了 \(j\) 个车的方案数。对于第 \(i\) 列，可以放或不放，仍然是二重决策状物。容易推出

\[dp_{i,j} = dp_{i-1,j} + dp_{i-1,j-1} \times (h_i - (j-1)) \]

这样定义状态的原因是，可以覆盖前面的子问题，使得某些离散的状态被归并到一个状态中。

Code

#include <bits/stdc++.h>
// #pragma GCC optimize(2)
#define int long long
#define inf 1e18
#define debug cout << '!';
#define filein(x) freopen(#x".in", "r", stdin);
#define fileout(x) freopen(#x".out", "w", stdout);
#define file(x) filein(x) fileout(x)
using namespace std;
const int N = 2e3+5, mod = 1e5+3;
int a, b, c, d, k;
int h[N], dp[N][N];
signed main() {cin.tie(0) -> sync_with_stdio(0);cin >> a >> b >> c >> d >> k;for (int i = 1; i <= a+c; i++) {if (i <= c) h[i] = d;else h[i] = b + d;}for (int i = 0; i <= a+c; i++) dp[i][0] = 1;for (int i = 1; i <= a+c; i++) {for (int j = 1; j <= k; j++) {dp[i][j] = (dp[i][j] + dp[i-1][j] + dp[i-1][j-1] * (h[i] - (j - 1)) % mod) % mod;}}cout << dp[a+c][k];return 0;
}

AtCoder ARC226 A - Meeting Division

link

Description

给定数轴上的 \(n\) 条互不相同的线段。Takahashi 和 Aoki 要选择其中的一些线段，保证：

  • 每条线段都被且仅被其中一人所选；
  • 每人所选的线段集合中，不能存在两两相交的线段。

求分配两人选择线段的方案数。

\(1 \le n \le 3 \times 10^5,\ 1 \le l_i \lt r_i \le 2n\)。

Solution

这种推性质的计数题，有一些巧妙的方法来完成计数。

我们可以发现，当一个点被覆盖大于或等于 \(3\) 次时，一定无解。

又注意到对于一个连通块，它仅有 \(2\) 种方案，即按照左端点排序后交替选择。因此答案为 \(2\) 的连通块个数次方。

Code

代码不太好写。可以用优先队列存储目前正在安排的线段，当一个线段完成安排后，直接弹出；如果优先队列的 size 超过了 \(3\)，那么可以快速地判断无解。

#include <bits/stdc++.h>
#pragma GCC optimize(2)
#define int long long
#define inf 1e18
#define debug cout << '!';
#define filein(x) freopen(#x".in", "r", stdin);
#define fileout(x) freopen(#x".out", "w", stdout);
#define file(x) filein(x) fileout(x)
using namespace std;
const int N = 3e5+5, mod = 998244353;
int n;
struct Seg {int l, r;friend bool operator < (Seg x, Seg y) {if (x.l == y.l) return x.r < y.r;return x.l < y.l;}
};
struct DSU {int fa[N], siz[N];void init() {for (int i = 0; i < n; i++) {fa[i] = i;siz[i] = 1;}}int find(int x) {if (fa[x] == x) return x;return fa[x] = find(fa[x]);}void unite(int x, int y) {x = find(x), y = find(y);if (siz[x] < siz[y]) swap(x, y);fa[y] = x;siz[x] += siz[y];}
} dsu;
int qpow(int x, int y) {if (y == 0) return 1;int tmp = qpow(x, y/2);if (y&1) return tmp * tmp % mod * x % mod;return tmp * tmp % mod;
}
vector<Seg> seg;
signed main() {cin.tie(0) -> sync_with_stdio(0);cin >> n;dsu.init();for (int i = 1; i <= n; i++) {int l, r; cin >> l >> r;seg.push_back({l, r});}sort(seg.begin(), seg.end());priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> q;int L = seg[0].l, R = seg[0].r;for (int i = 0; i < n; i++) {while (not q.empty() and q.top().first < seg[i].l) q.pop();if ((int)q.size() >= 2) {return cout << 0, 0;}if (not q.empty()) {dsu.unite(i, q.top().second);}q.push({seg[i].r, i});}int cnt = 0;for (int i = 0; i < n; i++) {if (dsu.find(i) == i) cnt++;}cout << qpow(2, cnt);return 0;
}

P7961 [NOIP2021] 数列

link

Description

给定整数 \(n, m, k\) 和下标从 \(0\) 开始、长度为 \(m + 1\) 的数组 \(v\)。

对于一个长度为 \(n\)、下标从 \(1\) 开始且每个元素均不超过 \(m\) 的非负整数序列 \(\{a_i\}\)，其权值为 \(\prod\limits_{i=1}^n v_{a_i}\)。

对于一个 \(\{a_i\}\)，若 \(S = \sum\limits_{i=1}^n 2^{a_i}\) 满足 \(\mathrm{popcount}(S) \le k\)，则 \(\{a_i\}\) 合法。

计算所有合法序列 \(\{a_i\}\) 的权值和对 \(998244353\) 取模的结果。

\(1 \le k \le n \le 30,\ 0 \le m \le 100,\ 1 \le v_i \lt 998244353\)。

Solution

抽象东西。

由于贡献产生在 \(S\) 上，显然要对 \(S\) 计数。从低位向高位 DP，同时，我们需要考虑进位问题。

定义 \(dp_{i,j,k,p}\) 表示对于 \(S\) 的前 \(i\) 个二进制位，确定了 \(j\) 个 \(a\) 中的元素，其中 \(\mathrm{popcount}(S) = k\)，向下一位进位 \(p\) 的权值和。

考虑状态 \((i,j,k,p)\) 的后继状态。假设确定了 \(a\) 中的 \(t\) 个 \(i\)，那么下一位是否为 \(1\) 决定于 \(2 | (p+t)\)，并产生 \(\Big\lfloor\dfrac{p+t}{2}\Big\rfloor\) 的进位。即后继状态为 \(\Big(i+1,j+t,k+(p+t)\bmod 2,\Big\lfloor\dfrac{p+t}{2}\Big\rfloor\Big)\)。

对于这 \(t\) 个 \(i\)，它们产生了 \(v_i^t\) 的贡献，要分配到 \(n-j\) 个空位，有 \(\dbinom{n-j}t\) 种分法，因此贡献系数为 \(v_i^t \cdot \dbinom{n-j}t\)。

答案为 \(\sum\limits_{k=0}^K \sum\limits_{p=0}^{n/2} dp_{m+1,n,k,p}\)，其中需要保证 \(\mathrm{popcount}(p) + k \le K\)。

Code

#include <bits/stdc++.h>
// #pragma GCC optimize(2)
#define int long long
#define inf 1e18
#define debug cout << '!';
#define filein(x) freopen(#x".in", "r", stdin);
#define fileout(x) freopen(#x".out", "w", stdout);
#define file(x) filein(x) fileout(x)
using namespace std;
const int M = 105, N = 35, mod = 998244353;
int n, m, K, v[M], ans;
// dp[i][j][k][p] 表示考虑到 S 的前 i 个二进制位，已经确定了 a 序列中的 j 个元素，目前这些二进制位中有 k 个 1，且向第 i+1 个二进制位的进位为 p 的方案数
int dp[M][N][N][N];
int C[N][N], powv[M][N], popcnt[N];
void init() {for (int i = 0; i <= n; i++) {C[i][0] = C[i][i] = 1;for (int j = 1; j < i; j++) {C[i][j] = (C[i-1][j-1] + C[i-1][j]) % mod;}}for (int i = 0; i <= m; i++) {powv[i][0] = 1;for (int j = 1; j <= n; j++) {powv[i][j] = powv[i][j-1] * v[i] % mod;}}for (int i = 0; i <= n; i++) {popcnt[i] = __builtin_popcountll(i);}
}
signed main() {cin.tie(0) -> sync_with_stdio(0);cin >> n >> m >> K;for (int i = 0; i <= m; i++) {cin >> v[i];}init();dp[0][0][0][0] = 1;for (int i = 0; i <= m; i++) {for (int j = 0; j <= n; j++) {for (int k = 0; k <= K; k++) {for (int p = 0; p <= n/2; p++) {for (int t = 0; t <= n-j; t++) {dp[i+1][j+t][k+(p+t)%2][(p+t)/2] = (dp[i+1][j+t][k+(p+t)%2][(p+t)/2] + dp[i][j][k][p] * powv[i][t] % mod * C[n-j][t] % mod) % mod;}}}}}for (int k = 0; k <= K; k++) {for (int p = 0; p <= n/2; p++) {if (popcnt[p] + k <= K) {ans = (ans + dp[m+1][n][k][p]) % mod;}}}cout << ans;return 0;
}

P8865 [NOIP2022] 种花

link

Description

给定 \(n \times m\) 的网格图，指定其中的一些格子不能种花。在能种花的格子中，统计种出 C 形和 F 形图案的方案数对 \(998244353\) 取模的结果。

\(1 \le n,m \le 10^3\)。

Solution

需要递推计算。

考虑 C 形图案的来源。可以先计算 — 形图案的方案数，然后顺延着计算 ┌ 形的方案数，最后将 — 和 ┌ 拼到一起形成 C 形。

至于 F 形，它可以看作 C 形的下沿。

具体递推过程见代码。

Code

#include <bits/stdc++.h>
// #pragma GCC optimize(2)
#define int long long
#define inf 1e18
#define debug cout << '!';
#define filein(x) freopen(#x".in", "r", stdin);
#define fileout(x) freopen(#x".out", "w", stdout);
#define file(x) filein(x) fileout(x)
using namespace std;
const int N = 1005, mod = 998244353;
int T, id, n, m, c, f;
char a[N][N];
int dp[N][N][4];
void solve() {memset(a, 0, sizeof a);memset(dp, 0, sizeof dp);cin >> n >> m >> c >> f;for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {cin >> a[i][j];}}for (int i = 1; i <= n; i++) {for (int j = m-1; j >= 1; j--) {if (a[i][j] == '0' and a[i][j+1] == '0') {dp[i][j][0] = (dp[i][j+1][0] + 1) % mod;} else {dp[i][j][0] = 0;}}}for (int i = 2; i <= n; i++) {for (int j = 1; j <= m; j++) {if (a[i][j] == '0' and a[i-1][j] == '0') {dp[i][j][1] = (dp[i-1][j][1] + dp[i-1][j][0]) % mod;} else {dp[i][j][1] = 0;}}}for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {if (a[i-1][j] == '0' and a[i][j] == '0') {dp[i][j][2] = (dp[i-1][j][1] * dp[i][j][0]) % mod;} else {dp[i][j][2] = 0;}}}for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {if (a[i-1][j] == '0' and a[i][j] == '0') {dp[i][j][3] = (dp[i-1][j][3] + dp[i-1][j][2]) % mod;} else {dp[i][j][3] = 0;}}}int ansc = 0, ansf = 0;for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {ansc = (ansc + dp[i][j][2]) % mod;ansf = (ansf + dp[i][j][3]) % mod;}}cout << c * ansc << ' ' << f * ansf << '\n';
}
signed main() {cin.tie(0) -> sync_with_stdio(0);cin >> T >> id;while (T--) {solve();}return 0;
}

P11362 [NOIP2024] 遗失的赋值

link

Description

给定一个数列 \(x\)，值域为 \([1,v]\)。给定 \(m\) 条一元限制，第 \(i\) 条限制包含二元组 \((c_j,d_j)\)，内容为 \(x_{c_j} = d_j\)。

在满足所有一元限制的条件下，试构造 \(n-1\) 条二元限制，使得这些二元限制均被满足。其中第 \(i\) 条限制包含二元组 \((a_i,b_i)\)，内容为：

  • \(a_i,b_i \in [1,v]\)；
  • 若 \(x_i = a_i\)，则要求 \(x_{i+1} = b_i\)；
  • 若 \(x_i \ne a_i\)，则无其他限制。

求构造这 \(n-1\) 条二元限制的方案总数对 \(10^9+7\) 取模的结果。

\(1 \le n \le 10^9,\ 1 \le m \le 10^5,\ 2 \le v \le 10^9\)。

Solution

首先不难发现，\(x\) 数列中元素具体的值是无用的，因为根据对称性，完全可以将其替换成另一个值而总方案数不变。

如果存在两个一元限制，使得它们对某一位的要求不同，则一定不合法。否则，将所有一元限制映射到序列上。此时，序列被一元限制划分成了若干长度不一的段。

假设某段长度为 \(i+1\)（包括首尾两个已填的数），那么对于这一段，我们需要构造 \(i\) 对二元限制。设构造 \(i\) 对连续二元限制的方案数为 \(f(i)\)，可以考虑递推。

对于这一段，设首尾的数分别为 \(x\) 和 \(y\)。考虑分类讨论：

  • 当第 \(1\) 对二元限制为 \((x,\cdots)\) 时，它不得不被满足，第 \(2\) 位的方案数为 \(v\)，剩下的部分则需构造连续的 \(i-1\) 对二元限制，总的方案数为 \(vf(i-1)\)。

  • 当第 \(1\) 对二元限制为 \((z,\cdots)(z\ne x)\) 时，它一定不被满足，其中 \(z\) 有 \(v-1\) 种取值方案，第二位的方案数为 \(v\)；对于剩下的 \(i-1\) 对二元限制，随便填数即可，共有 \((v^2)^{i-1}\) 种取值方案，总的方案数为 \((v-1)v\cdot v^{2i-2} = v^{2i} - v^{2i-1}\)。

综上，我们得到 \(f(i) = vf(i-1) + v^{2i} - v^{2i-1}\)，边界为 \(f(1) = v^2 - v+1\)。至此可以拿到 80 pts。

考虑 \(O(1)\) 计算 \(f(i)\) 的值。事实上，如果将 \(f(i-1)\) 再次代入，可以得到 \(f(i) = v^2(i-2) + v^{2i} - v^{2i-2}\)。不断代入，终究会发现 \(f(i) = v^kf(i-k) + v^{2i} - v^{2i-k}\)。不妨将 \(k=i-1\) 代入，则可得 \(f(i) = v^{2i} - v^i + v^{i-1}\)，即可 \(O(1)\) 计算。

对于首尾两段，填数方案不受任何限制，为 \(v^{2i}\)。

Code

#include <bits/stdc++.h>
// #pragma GCC optimize(2)
#define int long long
#define inf 1e18
#define debug cout << '!';
#define filein(x) freopen(#x".in", "r", stdin);
#define fileout(x) freopen(#x".out", "w", stdout);
#define file(x) filein(x) fileout(x)
using namespace std;
const int mod = 1e9+7;
int T, n, m, v;
int qpow(int x, int y) {if (y == 0) return 1;int tmp = qpow(x, y/2);if (y&1) return tmp * tmp % mod * x % mod;return tmp * tmp % mod;
}
inline int f(int x) {return ((qpow(v, 2*x) - qpow(v, x) + mod) % mod + qpow(v, x-1)) % mod;
}
void solve() {map<int, int> mp;vector<int> pos;cin >> n >> m >> v;for (int i = 1; i <= m; i++) {int c, d; cin >> c >> d;if (mp[c] != 0 and mp[c] != d) {cout << 0 << '\n';return;}mp[c] = d;pos.push_back(c);}sort(pos.begin(), pos.end());pos.erase(unique(pos.begin(), pos.end()), pos.end());int len = pos.size(), ans = 1;for (int i = 0; i < len-1; i++) {ans = (ans * f(pos[i+1] - pos[i])) % mod;}if (pos[0] != 1) {ans = (ans * qpow(v, 2*(pos[0]-1))) % mod;}if (pos[len-1] != n) {ans = (ans * qpow(v, 2*(n-pos[len-1]))) % mod;}cout << ans << '\n';
}
signed main() {cin.tie(0) -> sync_with_stdio(0);cin >> T;while (T--) {solve();}return 0;
}

P6144 [USACO20FEB] Help Yourself P

link

Description

数轴上有 \(n\) 条线段，其中第 \(i\) 条线段为 \([l_i,r_i]\)。对于这些线段的一个子集 \(S\)，它的复杂度 \(f(S)\) 为 \(S\) 中连通块数目的 \(k\) 次方。求这 \(n\) 条线段所有子集的复杂度之和对 \(10^9+7\) 取模的结果。

\(1 \le n \le 10^5,\ 1 \le l_i,r_i \le 2n,\ 2 \le k \le 10\)。

Solution

看到这种 \(k\) 次方加和且 \(k\) 很小的问题，直接考虑第二类 Stirling 数转化。

我们熟知

\[\begin{aligned}&\sum_{S \subseteq I} f^k(S) \\ =& \sum_{S \subseteq I} \sum_{i=0}^k \begin{Bmatrix} k \\ i \end{Bmatrix} i! \binom{f(S)}{i} \\ =& \sum_{i=0}^k \begin{Bmatrix} k \\ i \end{Bmatrix} i! \sum_{S \subseteq I} \binom{f(S)}{i} \end{aligned} \]

因此，对于每个集合 \(S\)，只需维护对于每个 \(i\)，对应的 \(\dbinom{f(S)}{i}\) 即可。

若设 \(dp_i\) 表示遍历到第 \(i\) 个线段时的答案显然不可行，因为多项式内部相加不可做。考虑更改状态定义。

定义 \(dp_{r,i}\) 表示在当前所有已处理的线段中，所有子集的并集的最大右端点恰为 \(r\) 时，这些子集的 \(\dbinom{f(S)}{i}\) 之和。

将所有线段按照左端点排序。对于已有的子集 \(T\)，设其最大的右端点为 \(x\)。对于加入的一条新线段 \([l,r]\)，我们有以下三种情况：

  • \(x < l\)

    此时，新线段与 \(T\) 分离，连通块数 \(+1\)，最大右端点变为 \(r\)。根据帕斯卡恒等式（即 \(\binom{c+1}{i} = \binom{c}{i-1} + \binom ci\)），有

    \[dp_{r,i} \overset{+}{\leftarrow} dp_{x,i-1} + dp_{x,i} \]

  • \(l \le x \le r\)

    连通块数不变，最大右端点变为 \(r\)，即

    \[dp_{r,i} \overset{+}{\leftarrow} dp_{x,i} \]

  • \(x > r\)

    新情况被旧情况包含，对于目前的线段，选或不选不会影响连通块数和最大右端点，因此原来的每个子集都可以扩展成两个子集，即

    \[dp_{x,i} \leftarrow 2 \times dp_{x,i} \]

这三种情况，可以用线段树维护。

我们需要支持：

  • 区间查询；
  • 区间乘；
  • 单点加。

具体地，我们在线段树内的每个节点维护：

  • \(dp\) 值之和（\(k\) 维数组，记录每一个 \(i\) 对应的信息）；
  • 乘法懒标记。

Code

这题代码非常不好写，需要研究一下

#include <bits/stdc++.h>
// #pragma GCC optimize(2)
#define int long long
#define inf 1e18
#define debug cout << '!';
#define filein(x) freopen(#x".in", "r", stdin);
#define fileout(x) freopen(#x".out", "w", stdout);
#define file(x) filein(x) fileout(x)
using namespace std;
const int N = 2e5+5, mod = 1e9+7;
int n, k;
struct Element {int l, r;friend bool operator < (Element x, Element y) {if (x.l == y.l) return x.r < y.r;return x.l < y.l;}
} ele[N];
struct SegmentTree {#define mid ((l + r) / 2)#define lson (id << 1)#define rson (id << 1 | 1)struct Node {int val[11];int lzy;} t[N << 2];void pushup(int id) {for (int i = 0; i <= k; i++) t[id].val[i] = (t[lson].val[i] + t[rson].val[i]) % mod;}void setlzy(int id, int lzy) {for (int i = 0; i <= k; i++) t[id].val[i] = 1ll * t[id].val[i] * lzy % mod;t[id].lzy = 1ll * t[id].lzy * lzy % mod;}void pushdown(int id) {if (t[id].lzy != 1) {setlzy(lson, t[id].lzy);setlzy(rson, t[id].lzy);t[id].lzy = 1;}}void build(int id, int l, int r) {if (l == r) {for (int i = 0; i <= k; i++) t[id].val[i] = 0;t[id].lzy = 1;} else {build(lson, l, mid);build(rson, mid + 1, r);pushup(id);}}void modify(int id, int l, int r, int ql, int qr, int lzy) {if (ql == l and qr == r) {setlzy(id, lzy);return;} else {pushdown(id);if (qr <= mid) modify(lson, l, mid, ql, qr, lzy);else if (ql > mid) modify(rson, mid + 1, r, ql, qr, lzy);else {modify(lson, l, mid, ql, mid, lzy);modify(rson, mid + 1, r, mid + 1, qr, lzy);}pushup(id);}}void change(int id, int l, int r, int pos, int* val) {if (l == r) {for (int i = 0; i <= k; i++) t[id].val[i] = (t[id].val[i] + val[i]) % mod;} else {pushdown(id);if (pos <= mid) change(lson, l, mid, pos, val);else change(rson, mid + 1, r, pos, val);pushup(id);}}void query(int id, int l, int r, int ql, int qr, int* res) {if (ql == l and qr == r) {for (int i = 0; i <= k; i++) {res[i] = (res[i] + t[id].val[i]) % mod;}} else {pushdown(id);if (qr <= mid) query(lson, l, mid, ql, qr, res);else if (ql > mid) query(rson, mid + 1, r, ql, qr, res);else {query(lson, l, mid, ql, mid, res);query(rson, mid + 1, r, mid + 1, qr, res);}}}#undef mid#undef lson#undef rson
} seg;
int S[11][11], fac[11];
void init() {S[0][0] = 1;for (int i = 1; i <= k; i++) {S[i][0] = 0, S[i][i] = 1;for (int j = 1; j < i; j++) {S[i][j] = (S[i-1][j-1] + 1ll * j * S[i-1][j]) % mod;}}fac[0] = 1;for (int i = 1; i <= k; i++) {fac[i] = 1ll * fac[i-1] * i % mod;}
}
signed main() {cin.tie(0) -> sync_with_stdio(0);cin >> n >> k;for (int i = 1; i <= n; i++) {cin >> ele[i].l >> ele[i].r;}sort(ele+1, ele+1+n);init();seg.build(1, 0, 2*n);int tmp0[11] = {0}; tmp0[0] = 1; // LET dp[0][0] = 1seg.change(1, 0, 2*n, 0, tmp0);for (int i = 1; i <= n; i++) {int l = ele[i].l, r = ele[i].r;int tmp1[11] = {0}, f[11] = {0};if (l-1 >= 0) seg.query(1, 0, 2*n, 0, l-1, tmp1);// CASE 1f[0] = tmp1[0];for (int j = 1; j <= k; j++) f[j] = (tmp1[j] + tmp1[j-1]) % mod;// CASE 2int tmp2[11] = {0};seg.query(1, 0, 2*n, l, r, tmp2);for (int j = 0; j <= k; j++) f[j] = (f[j] + tmp2[j]) % mod;// CASE 3if (r+1 <= 2*n) seg.modify(1, 0, 2*n, r+1, 2*n, 2);// UPDATEseg.change(1, 0, 2*n, r, f);}int tot[11] = {0}, ans = 0;seg.query(1, 0, 2*n, 0, 2*n, tot);for (int i = 0; i <= k; i++) {ans = (ans + 1ll * fac[i] * S[k][i] % mod * tot[i] % mod) % mod;}cout << ans << '\n';return 0;
}

P2606 [ZJOI2010] 排列计数

link

Description

求所有满足下列约束的长度为 \(n\) 的排列 \(p\) 的个数对 \(m\) 取模的结果：

\[\forall i \in [2,n],\ p_i > p_{\lfloor i/2 \rfloor} \]

\(1 \le n \le 10^6,\ 1 \le m \le 10^9\)，\(m\) 是一个质数。

Solution

注意到这个约束可被抽象为大小为 \(n\) 的小根堆。（？）

预处理出大小为 \(i\) 的小根堆的左右子树大小，随便乱搞就行。设 \(dp_i\) 表示大小为 \(i\) 的小根堆的方案数。左右子树相互独立，且根节点必须为最小值，因此要在 \(i-1\) 个点中选出 \(lsiz_i\) 个点作为左子树，剩下的作为右子树，即

\[dp_i = dp_{lsiz_i} \times dp_{rsiz_i} \times \binom{i-1}{lsiz_i} \]

组合数取模需要用到 Lucas 定理。注意阶乘预处理的上限应为 \(\min(n,m-1)\)，否则会在 \(m\le n\) 的 case 出错。

Code

#include <bits/stdc++.h>
// #pragma GCC optimize(2)
#define int long long
#define inf 1e18
#define debug cout << '!';
#define filein(x) freopen(#x".in", "r", stdin);
#define fileout(x) freopen(#x".out", "w", stdout);
#define file(x) filein(x) fileout(x)
using namespace std;
const int V = 1e6;
int n, mod;
int qpow(int x, int y) {if (y == 0) return 1;int tmp = qpow(x, y/2);if (y&1) return tmp * tmp % mod * x % mod;return tmp * tmp % mod;
}
int fac[V+5], inv_fac[V+5];
void init_fac() {fac[0] = 1;int lmt = min(n, mod-1);for (int i = 1; i <= lmt; i++) {fac[i] = fac[i-1] * i % mod;}inv_fac[lmt] = qpow(fac[lmt], mod-2);for (int i = lmt-1; i >= 0; i--) {inv_fac[i] = inv_fac[i+1] * (i+1) % mod;}
}
// LUCAS THEOREM
int C(int x, int y) {if (x < y or y < 0) return 0;if (x < mod and y < mod) return fac[x] * inv_fac[y] % mod * inv_fac[x-y] % mod;return C(x/mod, y/mod) * C(x%mod, y%mod) % mod;
}
int lc[V+5], rc[V+5], pow2[V+5];
void init_son() {pow2[0] = 1;for (int i = 1; i <= floor(log2(n))+10; i++) {pow2[i] = pow2[i-1] * 2;}for (int i = 1; i <= n; i++) {int lvl0 = floor(log2(i+1));lc[i] = rc[i] = pow2[lvl0-1]-1;int rest = i - 1 - lc[i] - rc[i];if (rest <= pow2[lvl0-1]) lc[i] += rest;else lc[i] += pow2[lvl0-1], rc[i] += rest - pow2[lvl0-1];}
}
int dp[V+5];
signed main() {cin.tie(0) -> sync_with_stdio(0);cin >> n >> mod;init_fac();init_son();dp[0] = 1;for (int i = 1; i <= n; i++) {dp[i] = dp[lc[i]] * dp[rc[i]] % mod * C(i-1, lc[i]) % mod;}cout << dp[n];return 0;
}

P3214 [HNOI2011] 卡农

link

Description

现有由 \(1 \sim n\) 的正整数构成的全集 \(I\)。对于 \(I\) 的若干子集构成的集合 \(U\)，满足：

  • \(|U| = m\)；
  • \(U\) 中不存在空集；
  • \(U\) 中不存在两个相同集合；
  • 对于 \(U\) 中的所有集合，其内部所有元素的出现次数必须为偶数。

求满足条件的 \(U\) 的个数对 \(10^8+7\) 取模的结果。

Solution

可以假定 \(U\) 有序，最后除以 \(m!\) 即可。

设 \(dp_i\) 表示确定到 \(U\) 的第 \(i\) 个集合时的方案数。

我们发现，由于第四条性质的约束，若前 \(i-1\) 个集合都被确定，那么第 \(i\) 个集合也必然随之确定，因此现有的方案数为 \(A_{2^n-1}^{i-1}\)。

接下来考虑容斥。对于第二条约束，如果第 \(i\) 个集合为空集，那么前 \(i-1\) 个集合必然构成一组合法排列，方案数为 \(dp_{i-1}\)。

对于第三条约束，设 \(j(1 \le j \le i-1)\) 满足第 \(j\) 个集合与第 \(i\) 个集合相同，那么它们之中的元素数之和必为偶数，进而剩下 \(i-2\) 个集合必然构成一组合法排列。其中 \(j\) 有 \(i-1\) 种选法；\(i\) 不能与剩下 \(i-2\) 个集合相同，有 \(2^n-1-(i-2)\) 种选法，则总方案数为 \(dp_{i-2} \times (i-1) \times (2^n-1-(i-2))\)。

受到考虑顺序的约束，显然不存在同时违反第二条和第三条约束的方案，因此直接做减法即可。综上，有

\[dp_i = A_{2^n-1}^{i-1} - dp_{i-1} - dp_{i-2} \times (i-1) \times (2^n-1-(i-2)) \]

边界为

\[dp_0 = 1,\ dp_1 = 0 \]

排列数可以递推计算。

Code

#include <bits/stdc++.h>
// #pragma GCC optimize(2)
#define int long long
#define inf 1e18
#define debug cout << '!';
#define filein(x) freopen(#x".in", "r", stdin);
#define fileout(x) freopen(#x".out", "w", stdout);
#define file(x) filein(x) fileout(x)
using namespace std;
const int V = 1e6, mod = 1e8+7;
int n, m;
int qpow(int x, int y) {if (y == 0) return 1;int tmp = qpow(x, y/2);if (y&1) return tmp * tmp % mod * x % mod;return tmp * tmp % mod;
}
int A[V+5], m_fac;
void init() {int base = qpow(2, n);base = (base - 1 + mod) % mod;A[0] = 1;for (int i = 1; i <= m; i++) {A[i] = 1ll * A[i-1] * (base - i + 1 + mod) % mod;}m_fac = 1;for (int i = 2; i <= m; i++) {m_fac = m_fac * i % mod;}
}
int dp[V+5];
signed main() {cin.tie(0) -> sync_with_stdio(0);cin >> n >> m;init();dp[0] = 1, dp[1] = 0;for (int i = 2; i <= m; i++) {dp[i] = ((A[i-1] - dp[i-1] + mod) % mod - 1ll * dp[i-2] * (i-1) % mod * (qpow(2, n) - i + 1 + mod) % mod + mod) % mod;}cout << dp[m] * qpow(m_fac, mod-2) % mod;return 0;
}
网站建设 视觉设计 SEO优化
返回列表