智商题

例

给出 $n$ 个正整数 $a$，你要选出 $n$ 个正整数 $b$ 和 $n$ 个正整数 $d$，对于每个 $i$ 满足 $b|a$ 且 $d|b$，求有多少种选法满足

$$\prod d_i^2\ge \prod b_i$$

s.t. $n\le 100,a_i\le {10}^9$

SOL 因为$\prod d_i^2>\prod b_i\text{ 和}\prod d_i^2<\prod b_i$ 方案数相同, 我们只需要计算 $\prod d_i^2=\prod b_i$

每个质因子相互独立, 分别背包计数即可.

---

CF838D

有 $n$ 个位置排成一排，有 $m$ 个人依次进场选位置，每个人一开始会选择一个方向，从左到右或从右到左，并选择一个位置，然后按他选择的方向入场并走到这个位置，从这个位置开始继续按他选择的方向走，直到遇到一个空位并坐下。如果一直找不到空位，他就会生气。求有多少种情况没有人生气。 s.t. $1\le m\le n\le {10}^6$

SOL 看成一个长度为 $n+1$ 的环，其中编号 $n+1$ 的点为间隔点（不能被占据），每次每个人可以选一个起点要么逆时针要么顺时针走到第一个空位上。如果编号为 $n+1$ 的点被人占据了显然不合法，否则肯定合法。 由于这是一个环，因此最终每个点没被占据的概率都是相同的。即一个点最终没被占据的概率是 $\frac{n+1-m}{n+1}$，乘以方案数 $2^m(n+1{)}^m$ 即可。

CODE

// Date: 2023-07-31 13:31:48
// Problem: Airplane Arrangements
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/CF838D
// Memory Limit: 250 MB
// Time Limit: 2000 ms

constexpr int mod = 1e9 + 7;

ll qpow(ll a, ll b, int mod) {
    ll res = 1;
    while (b) {
        if (b & 1)
            res = res * a % mod;
        b >>= 1;
        a = a * a % mod;
    }
    return res;
}

ll m, n;

signed main() {
    fastio();
	cin>> n >> m;
	ll ans = qpow(2, m, mod) * qpow(n + 1, m, mod) % mod * (n + 1 - m) % mod * qpow(n + 1, mod - 2, mod) % mod;
	cout << ans <<endl;
    return 0;
}

容斥原理

例

有 $n$ 堆石子，已知每堆石子的数量都介于 $[1,2^m-1]$ 之间且互不相同。 给定 $n,m$ ，每堆石子中的数量可以任选（但必须满足上述要求），求有多少种方案可以使得 Nim 游戏下先手取胜。 答案模${10}^9+7$。 s.t. $n\le {10}^7$, $1\le m\le {10}^9$

SOL 设 $f_n$ 表示 $n$ 的答案，考虑任选前 $n-1$ 个不同的数字，则最后一个数字是确定的，方案数为

$$\frac{(2^{m-1}-1)!}{(2^{m-1}-n)!}$$

减掉最后一个数字是 $0$ 的情况:

$$\frac{(2^{m-1}-1)!}{(2^{m-1}-n)!}-f_{n-1}$$

减掉最后一个数字和前面某个相同的情况（先枚举位置，再枚举数字）:

$$\frac{(2^{m-1}-1)!}{(2^{m-1}-n)!}-f_{n-1}-(n-1)(2^m-n+1)f_{n-2}$$

因此 $ O(n) $ 递推即可。

---

CF1036F

求 $[2,n]$ 中有多少数字不能表示成别的数字的幂次，即不能写成 $a^b$ $(b>1)$的形式 s.t. $1\le n\le {10}^{18}$

SOL 令 $f(i)$ 表示最多能开 $\mathit{i}$ 次方的数字个数，$g(i)$ 表示能开 $i$ 次方的数字个数，则:

$$g(i)=\lfloor \sqrt[i]{n}\rfloor =\sum _{i\mid j}f(j)$$

我们现在要求 $f(1)$，不难得到 $f(i)$ 的递推式:

$$f(i)=g(i)-\sum _{i|j,j>i}f(j)$$

CODE

// Date: 2023-07-31 15:47:45
// Problem: Relatively Prime Powers
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/CF1036F
// Memory Limit: 250 MB
// Time Limit: 2000 ms

constexpr int N = 100;
int pri[N], mu[N], cnt;

void init() {
    static bool st[N];
    mu[1] = 1;
    F(i, 2, N) {
        if (!st[i])
            pri[++cnt] = i, mu[i] = -1;
        for (int j = 1; j <= cnt && i * pri[j] < N; ++j) {
            st[i * pri[j]] = 1;
            if (i % pri[j] == 0) {
                mu[i * pri[j]] = 0;
                break;
            }
            mu[i * pri[j]] = -mu[i];
        }
    }
}

// 注意开方精度丢失问题
void solve(ll x) {
    ll ans = 0;
    Fe(i, 1, 60) {
        ll p = powl(x, 1.0 / i) + 2;
        while (powl(p, i) > x)
            p--;
        ans += 1ll * mu[i] * (p - 1);
    }
    cout << ans << endl;
}

signed main() {
    fastio();
    init();
    int T;
    cin >> T;
    while (T--) {
        ll x;
        cin >> x;
        solve(x);
    }
    return 0;
}

---

CF997C

用三种颜色对 $n\times n$ 的格子染色，问至少有一行或者一列只有一种颜色的方案数有多少。 s.t. $n\le {10}^6$

SOL 考虑容斥, 设 $i$ 行 $j$ 列颜色完全相同, 则答案为

$$3^{n^2}+\sum _{i=1}^n\sum _{j=1}^n(-1{)}^{i+j}(\genfrac{}{}{0ex}{}{n}{i})(\genfrac{}{}{0ex}{}{n}{j})3\times 3^{(n-i)(n-j)}+2\sum _{i=1}^n(-1{)}^i{3}^{i+n(n-i)}$$

---

CF1096E

一场游戏有 $p$ 人参加，得分总和为 $s$ 分，每个人的分数都是非负整数，且其中一号玩家的得分至少为 $r$。 而现在不知道具体的得分情况，求一号玩家获胜的概率，我们认为任何一种合法的得分情况出现的概率相等。得分最高的玩家获胜，特殊的，若有多人得分相同，他们获胜的几率相同。 s.t. $1\le p\le 100$ , $0\le r\le s\le 5000$,要求答案对 $998244353$ 取模.

SOL 先枚举第一个人最后是多少，然后枚举最后有多少个人和第一个人一样，剩下的人强制比第一个人少。

容斥，强制有若干个人至少是 $l$ ，则

$$\sum _{i=0}^k(-1{)}^i(\genfrac{}{}{0ex}{}{k}{i})(\genfrac{}{}{0ex}{}{s-il+k-1}{k-1})$$

其中 表示剩下 $k$ 个人， $s$ 表示剩下人的总分。

Matrix-Tree 定理

定义

无向图（有向图）的生成树（有向生成树）个数等于基尔霍夫矩阵去掉生成树根所在行列之后的行列式。

本质上是对环容斥，可以计算出，若选了 $k$ 个环，则其在行列式中会有 $(-1{)}^k$ 的系 数，刚好对应了容斥系数。

LGV 引理

模板题

一个 DAG，给定 $n$ 个起点 $a_1,\cdots ,a_n$ 和 $n$ 个终点 $b_1,\cdots ,b_n$ ，对于一个排列 $\sigma$ ，算出 $n$ 条路径 $(a_1,b_{{\sigma }_1}),\cdots ,(a_n,b_{{\sigma }_n})$ 且这些路径互不相交（不经过同一个点多次）的方案，作为这个排列的权重。

计算所有偶排列的权重和减掉奇排列的权重和。

s.t. $n\le 500$

SOL 设 $f(a,b)$ 表示 $a$ 到 $b$ 的方案数，那么答案就是矩阵 $[f(a_i,b_j)]$ 的行列式。

证明略

例题

NOI2021 路径交点

SOL 交点个数的奇偶性就是排列的奇偶性。裸题。