Day 2

一道热身题

1.png

$n$ 是偶数时,奇数位对应偶数位,因此一定相等,只要满足回文即可,方案数为 $10 ^{n/2}$

$n$ 为奇数时,奇偶不对应。分情况讨论。

即 $4k + 1$ 还是 $4k + 3$ 。

当为 $4k + 1$,即奇数多了一个,那么需要满足

$2*(x_1+x_3+\cdots+x_{2k-1}) + x_{2k+1}=2*(x_2+x_4+\cdots+x_{2k})$

不妨 $/2$ ,$(x_1+x_3+\cdots+x_{2k-1})+\frac{x_{2k+1}}{2}=(x_2+x_4+\cdots+x_{2k})$

设 $\forall i \text{ mod } 2 = 1, y_i =9-x_i$ , 则

$(x_2+x_4+\cdots+x_{2k})+(y_1+y_3+\dots+y_{2k-1})=9k+\frac{x_{2k+1}}{2},x_i,y_i\in[0,9]$

枚举有多少个数 $\ge 10$ ,容斥,插板计算即可。

$\sum_{i = 0}^k (-1)^i\dbinom{n}{i}\dbinom{n-10i+k-1}{k-1}$

另一道热身题

2.png

记 $A=\{(i,j)|a_i < a_j\},B=\{(i,j)|b_i<b_j\},C = \{(i,j)|c_i<c_j\}$ ,$U$ 为全集

实际上我们要求

$$|A\bigcap B\bigcap C |=|U|-|\overline{A}|-|\overline{B}|-|\overline{C}|+|\overline{A}\bigcap\overline{B}|+|\overline{B}\bigcap\overline{C}|+|\overline{A}\bigcap\overline{C}|-|\overline{A}\bigcap\overline{B}\bigcap\overline{C}|$$

看上去我们并不能绕开三维偏序这个问题。

但是

$\overline{A}\bigcap\overline{B}\bigcap\overline{C}$ 实际上元素大小是于 $A\bigcap B\bigcap C $ 一样的,因为它们元素一一对应 $(i,j),(j,i)$ (由于是排列才这样)。

所以我们可以挪一下,

$|A\bigcap B\bigcap C |+|\overline{A}\bigcap\overline{B}\bigcap\overline{C}|=|U|-|\overline{A}|-|\overline{B}|-|\overline{C}|+|\overline{A}\bigcap\overline{B}|+|\overline{B}\bigcap\overline{C}|+|\overline{A}\bigcap\overline{C}|$

然后就可以只用二维偏序了。

ARC096 E - Everything on It

3.png

对于第三个限制,我们采用容斥的方法,枚举至少有 $i$ 个数至多出现 $1$ 次。

那么方案数为

$$\begin{aligned}\sum_{i=0}^n(-1)^i\dbinom{n}{i}2^{2^{n-i}}f(i)\end{aligned}$$

其中 $2^{2^{n-i}}$ 表示不选择钦定的 $i$ 个数的子集方案数,$f(i)$ 表示选的方案数。

接下来计算 $f(i)$ 。

仔细分析一下,可以发现 $f(i)$ 实际上求选出若干个集合,将 $i$ 个数中一部分放入集合 ,一部分不放,且每一个集合必须有数的方案数。

不妨把不放的数丢进一个新的集合里。

考虑这个集合有没有数。

方案数就为 $\begin{Bmatrix}i\\k\end{Bmatrix}+(k+1)\begin{Bmatrix}i\\k+1\end{Bmatrix}=\begin{Bmatrix}i+1\\k+1\end{Bmatrix}$

前一部分表示没有数,后一部分表示有数,且不知道哪个集合是新的。

const int N = 3e3 + 5;

int S[N][N], fac[N], ifac[N], inv[N];

inline int ksm(int a, int b, const int& mod) {
    int ans = 1; 
    for (; b; b >>= 1, a = 1ll * a * a % mod) 
        if (b & 1) ans = 1ll * ans * a % mod;
    return ans;
}

inline int binom(int n, int m, const int& mod) {
    if (n < m || n < 0 || m < 0) return 0;
    if (n == 0 || m == 0) return 1; 
    return 1ll * fac[n] * ifac[n - m] % mod * ifac[m] % mod;
}

int add(int a, int b, const int& mod) {return a += b, a >= mod ? a - mod : a;}
int sub(int a, int b, const int& mod) {return a -= b, a < 0 ? a + mod : a;}

int main() {
    S[0][0] = 1; int n, mod; scanf("%d%d", &n, &mod);
    inv[0] = ifac[0] = fac[0] = inv[1] = fac[1] = ifac[1] = 1;
    for (int i = 2; i < N; ++i) {
        inv[i] = 1ll * inv[mod % i] * (mod - mod / i) % mod;
        fac[i] = 1ll * fac[i - 1] * i % mod;
        ifac[i] = 1ll * ifac[i - 1] * inv[i] % mod;
    }
    for (int i = 1; i < N; ++i) 
        for (int j = 1; j <= i; ++j) 
            S[i][j] = (1ll * S[i - 1][j] * j % mod + S[i - 1][j - 1]) % mod;
    int ans = 0;
    for (int i = 0; i <= n; ++i) {
         int sum = 0;
         for (int j = 0; j <= i; ++j) {
             int val = ksm(2, 1ll * j * (n - i) % (mod - 1), mod);
             val = 1ll * val * S[i + 1][j + 1] % mod;
            sum = (sum + val) % mod;
        }
        if (i & 1) ans = sub(ans, 1ll * sum * ksm(2, ksm(2, n - i, mod - 1), mod) % mod * binom(n, i, mod) % mod, mod); 
        else ans = add(ans, 1ll * sum * ksm(2, ksm(2, n - i, mod - 1), mod) % mod * binom(n, i, mod) % mod, mod);
    }
    printf("%d\n", ans);
    return 0;
}

ARC093 F - Dark Horse

4.png

考虑到 $1$ 放在哪并不会影响答案。

那么不妨设 $1$ 放在位置 $1$,则需要比较的集合为

$U=\{p_2,\min\{p_3,p_4\},\min\{p_5,p_6. p_7,p_8\},\cdots,\min\{p_{2^{k-1}},\cdots,p_{2^k}\}\}$

直接求不好求,考虑容斥枚举 $S$ ,钦定 $S$ 中某一些位置的 $\min$ 为 $A$ 集合中的元素,于是方案为

$$\sum_{S} (-1)^{|S|}f(S)$$

具体推导可以考虑一个具体方案的贡献。

$f(S)$ 是可以 dp 的。

从大到小考虑 $A_i$ ,对于一个状态 $f_{i,S}$

它需要考虑当前填不填入 $A_i$ ,以及填在哪个区间。

于是就有转移方程

$$f_{i - 1,S}+=f_{i,S}\\f_{i-1,S|2^{j},j\notin S}+=f_{i,S}*\dbinom{2^n-S-A_i }{2^j -1}*(2^j)!$$

之所以是这个组合数,是因为已经钦定从大到小插入了。

最后 $f(S)=f_{0,S}*res!$

#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>

using namespace std;

const int M = 1 << 16 | 5, N = 18, mod = 1e9 + 7;

int f[N][M], inv[M], fac[M], ifac[M], a[N], pw[N], cnt[M];

inline int binom(int n, int m) { 
    if (n < m || n < 0 || m < 0) return 0;
    if (n == m || m == 0) return 1;
    return 1ll * fac[n] * ifac[n - m] % mod * ifac[m] % mod;
}

inline int add(int x, int y) {return x += y, x >= mod ? x - mod : x;}
inline int sub(int x, int y) {return x -= y, x < 0 ? x + mod : x;}

int main() {
    inv[0] = inv[1] = fac[0] = fac[1] = ifac[0] = ifac[1] = 1;
    pw[0] = 1; for (int i = 1; i <= 16; ++i) pw[i] = pw[i - 1] * 2; 
    cnt[0] = 1; cnt[1] = mod - 1;
    for (int i = 2; i < M; ++i) {
        inv[i] = 1ll * inv[mod % i] * (mod - mod / i) % mod;
        fac[i] = 1ll * fac[i - 1] * i % mod;
        ifac[i] = 1ll * ifac[i - 1] * inv[i] % mod;
        cnt[i] = (i & 1) ? mod - cnt[i >> 1] : cnt[i >> 1];
    }
    int n, m; scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; ++i) scanf("%d", &a[i]);
    sort(a + 1, a + m + 1); 
    f[m][0] = 1; 
    for (int i = m; i; --i) 
        for (int S = 0; S < (1 << n); ++S) if (f[i][S]) {
            f[i - 1][S] = add(f[i - 1][S], f[i][S]);
            int p = (1 << n) - 1 - S;
            if (p > 0) for (int j = 0; j < n; ++j) if ((~S) >> j & 1) 
                f[i - 1][S | (1 << j)] = add(f[i - 1][S | (1 << j)], 1ll * f[i][S] * binom(p - a[i] + 1, (1 << j) - 1) % mod * fac[1 << j] % mod);
         }
    int ans = 0;
    for (int i = 0; i < (1 << n); ++i)
        ans = add(ans, 1ll * f[0][i] * fac[((1 << n) - 1 - i)] % mod * cnt[i] % mod);
    ans = 1ll * ans * (1 << n) % mod;
    printf("%d\n", ans);
    return 0;
}

【集训队作业2018】小Z的礼物

设集合 $S$ 为 所有喜欢礼物组成的集合。答案要求:

$$ \mathbb{E}(\max\limits_{x\in S}\{t_x\})$$

考虑 min_max 容斥,

$$\begin{aligned} \mathbb{E}(\max\limits_{x\in S}\{t_x\})&= \mathbb{E}(\sum\limits_{T\subseteq S}(-1)^{|T|-1}\min\limits_{x\in T}\{t_x\})\\&=\sum\limits_{T\subseteq S}(-1)^{|T|-1} \mathbb{E}(\min\limits_{x\in T}\{t_x\})\end{aligned}$$

$ \mathbb{E}(\min\limits_{x\in T}\{t_x\})$ 好求,就是 $\frac{n*m-n-m}{k_T}$ ,其中 $k_T$ 为包含此子集的点对。

但是如果枚举子集,复杂度过高。

不妨直接统计 $k_T$ 的贡献。

由于一个点会与相邻四个点产生贡献。

就有轮廓线dp, $f_{j,i,S,k,0/1}$ 表示选不选 $(i,j)$ ,以及与其相邻的两个格子是否有重,$0/1$ 表示集合个数奇偶。

可以继续优化,比如 $0/1$ 可以直接在转移的时候减。

const int N = 7, M = 105, U = 1 << 6 | 5;
const int mod = 998244353;

int f[2][U][N * M * 2], inv[N * M * 2];
char s[N][M];

inline int add(int x, int y) {return x += y, x >= mod ? x - mod : x;}
inline int sub(int x, int y) {return x -= y, x < 0 ? x + mod : x;}

int main() {
    int n, m; scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i) scanf("%s", s[i] + 1);
    int sum = n * (m  - 1) + m * (n - 1);
    inv[1] = 1; for (int i = 2; i <= sum; ++i) inv[i] = 1ll * inv[mod % i] * (mod - mod / i) % mod; 
    
    f[0][0][0] = mod - 1; int p = 0, q = 1;
    for (int j = 1; j <= m; ++j) 
        for (int i = 1; i <= n; ++i) {
            swap(p, q); memset(f[p], 0, sizeof f[p]);
            for (int S = 0; S < (1 << n); ++S) 
                for (int k = 0; k <= sum; ++k) 
                    if (f[q][S][k]) {
                        int T = (~(1 << (i - 1))) & S;
                        f[p][T][k] = add(f[p][T][k], f[q][S][k]);
                        if (s[i][j] == '*') {
                            int cnt = 0; T = S | (1 << (i - 1));
                            if (i > 1 && !(S & (1 << (i - 2)))) ++cnt;
                            if (j > 1 && !(S & (1 << (i - 1)))) ++cnt;
                            if (i < n) ++cnt; if (j < m) ++cnt;
                            f[p][T][k + cnt] = sub(f[p][T][k + cnt], f[q][S][k]);
                        }
                    }
        }
    
    int ans = 0;
    for (int i = 0; i < (1 << n); ++i) 
        for (int j = 1; j <= sum; ++j)     
                ans = add(ans, 1ll * f[p][i][j] * inv[j] % mod);
    ans = 1ll * ans * sum % mod;
    printf("%d\n", ans);
    return 0;
}

【雅礼集训】方阵 / TopCoder - 13444

任意两行不重应该很好做也就是 $g_m=(c^m)^{\underline{n}}$

设计一个状态表示任意两行不重 ,且有 $i$ 列本质不同的方案数 $f_{i}$ 。

那么要求 $f_m$ ,有

$g_m=\sum\limits_{i=0}^m\begin{Bmatrix}m\\i\end{Bmatrix}f_i$

稍微解释一下,对于一个具体的方案,

我们先将本质相同的列合并,然后构成若干个集合。

因为只贡献一次,所以这些集合应该是无序的,也就是第二类斯特林数。染色交给 $f_i$

反演一下,得

$f_m=\sum\limits_{i=0}^m(-1)^{m-i}\begin{bmatrix}m\\i\end{bmatrix}g_i$

const int N = 5e3 + 5;
const int mod = 1e9 + 7;

int g[N], f[N], S[N][N], s[N][N];

inline int ksm(int a, int b) {
    int ans = 1;
    for (; b; b >>= 1, a = 1ll * a * a % mod) 
        if (b & 1) ans = 1ll * ans * a % mod;
    return ans;
}

inline int add(int x, int y) {return x += y, x >= mod ? x - mod : x;}
inline int sub(int x, int y) {return x -= y, x < 0 ? x + mod : x;}

int main() {
    int n, m, c; scanf("%d%d%d", &n, &m, &c);
    S[0][0] = s[0][0] = 1;
    for (int i = 1; i <= m; ++i) 
        for (int j = 1; j <= i; ++j) 
            S[i][j] = (S[i - 1][j - 1] + 1ll * S[i - 1][j] * j % mod) % mod,
            s[i][j] = (s[i - 1][j - 1] + 1ll * s[i - 1][j] * (i - 1) % mod) % mod;
    for (int i = 1; i <= m; ++i) {
        ll d = 1; bool flag = 0;
        for (int j = 1; j <= i; ++j) {
            d *= c; if (d >= n) flag = 1;
            d %= mod;
        }
        if (!flag) g[i] = 0;
        else {
            g[i] = 1;
            for (int j = 0; j < n; ++j) {
                ll w = d - j; if (w < 0) w += mod;
                g[i] = 1ll * g[i] * w % mod;
            }
        }
    }    
    int ans = 0;
    for (int i = 0; i <= m; ++i)
        if ((m - i) & 1) ans = sub(ans, 1ll * g[i] * s[m][i] % mod);
        else ans = add(ans, 1ll * g[i] * s[m][i] % mod);
    printf("%d\n", ans);
    return 0;
}

一道例题

5.png

设随机变量 $c_u$ 表示在随机情况下到达 $1$ 的时间参数。

$ \mathbb{E}({c_u}^k)$ 明显不能直接求,那么我们可以考虑把它拆成下降幂的形式

$$\begin{aligned}\mathbb{E}({c_u}^k)&= \mathbb{E}(\sum\limits_{i=1}^k\begin{Bmatrix}k\\i\end{Bmatrix}{c_u}^{\underline{i}})\\&=\sum\limits_{i=1}^k\begin{Bmatrix}k\\i\end{Bmatrix}i!\mathbb{E}(\tbinom{{c_u}}{i})\end{aligned}$$

$$\begin{aligned}\mathbb{E}(\tbinom{{c_u}}{i})&=p_u\mathbb{E}(\tbinom{{c_u}+1}{i})+\frac{1-p_u}{d_u}\sum\limits_{(u,v)\in E}\mathbb{E}(\tbinom{{c_v}+1}{i})\\&=p_u\mathbb{E}(\tbinom{{c_u}}{i}+\tbinom{{c_u}}{i-1})+\frac{1-p_u}{d_u}\sum\limits_{(u,v)\in E}\mathbb{E}(\tbinom{{c_v}}{i}+\tbinom{{c_v}}{i-1})\end{aligned}$$

记 $f_u=\mathbb{E}(\tbinom{{c_u}}{i}),a_u=\mathbb{E}(\tbinom{{c_u}}{i-1})$ ,整理得到:

$$\begin{aligned} f_u&=p_u(f_u+a_u)+\frac{1-p_u}{d_u}\sum_{(u,v)\in E}(f_v+a_v)\\d_uf_u&=\frac{d_up_u}{1-p_u}a_u+\sum_{v\in son(u)} (f_v+a_v)+f_{fa_u}+a_{fa_u}\end{aligned}$$

做个差分 $T_u=f_{fa_u}-f_u$ ,有

$f_u=\frac{d_up_u}{1-p_u}a_u+\sum_{v\in son(u)}(a_v+T_v)+f_{fa_v}+a_{fa_v}$

$T_u=\frac{d_up_u}{1-p_u}a_u+\sum_{v\in son(u)}(a_v+T_v)+a_{fa_v}$

于是我们乱搞一下,由于 $\tbinom{c_1}{i}=f_1=0$

$T_u$ 可以自下而上处理,$f_u$ 可以自上而下处理。

然后顺便求个斯特林数即可顺利做完此题。

另一道例题

6.png

$$\begin{aligned}\sum_{T}|T|^k&=\sum_{T}\sum_{i=1}^k\begin{Bmatrix}k\\i\end{Bmatrix}i!\tbinom{|T|}{i}\\&=\sum_{i=1}^{k}\begin{Bmatrix}k\\i\end{Bmatrix}i!\sum_{T}\tbinom{|T|}{i}\end{aligned}$$

$\sum_{T}\tbinom{|T|}{i}$ 实际上可以等价为我先选出 $i$ 个联通块所需要的人,然后剩下任意选。

$$\begin{aligned}\sum_{T}\tbinom{|T|}{i}&=\sum_{j=i}^n\tbinom{n}{j}dp_{i,j}2^{\tbinom{n-j}{2}}\end{aligned}$$

然后考虑如何求 $dp_{i,j}$ ,

$$\begin{aligned}dp_{i,j}&=\sum\limits_{k = 1}^{j}\tbinom{j-1}{k-1}dp_{1,k}dp_{i-1,j-k}\\\frac{dp_{i,j}}{(j-1)!}&=\sum_{k=1}^j\frac{dp_{1,k}}{(k-1)!}\frac{dp_{i-1,j-k}}{(j-k)!}\end{aligned}$$

这个是卷积形式,$\Theta(kn\log n)$ 。

令 $f_k$ 表示 $dp_{1,k}$ ,我们现在要求 $f_k$ ,

考虑容斥求。

$$\begin{aligned}f_k=2^{\tbinom{k}{2}}-\sum_{i=1}^{k-1}\end{aligned}\tbinom{k-1}{i-1}f_i2^{\tbinom{k-i}{2}}$$

这个显然也是一个卷积形式。

$$\frac{2^{\tbinom{k}{2}}}{(k-1)!}=\sum\limits_{i=1}^k\frac{f_i}{(i-1)!}\frac{2^\tbinom{k-i}{2}}{(k-i)!}$$

ARC 062 F - Painting Graphs with AtCoDeer

7.png

先做一个最简单的情况,是一个简单环。

就是一道模板题。

如果是一个极大的环套环(简单环套简单环),可以发现可以通过两个小的进行变换后,可以做到任意分配边的颜色。

也就是如果固定了 $k$ 种颜色的边数,那本质不同的方案唯一,所以总的方案数就是选颜色边数的方案数,即 $\dbinom{|E|+K-1}{K-1}$

如果是非环边,随意染色。

注意,由一个点相连的两个环无法相互变换,分属两个简单环,而不是环套环、

而这种情况刚好对应了点双分量中,不存在割点的要求(这种情况会有割点,即环相交的那个点)。

因此点双处理是正确的,边双处理是错误的。

inline int ksm(int a, int b = mod - 2) {
    int ans = 1; 
    for (; b; b >>= 1, a = 1ll * a * a % mod) 
        if (b & 1) ans = 1ll * ans * a % mod;
    return ans;
}

int gcd(int a, int b) {return !b ? a : gcd(b, a % b);}

vector<int> D[N];
int dfn[N], low[N], cnt, num, c[N], sta[N], top, fac[M], inv[M], ifac[M], root;
struct edge{int y, next;} a[M << 1]; int len, last[N];
void ins(int x, int y) {a[++len] = (edge){y, last[x]}; last[x] = len;}

void tarjan(int x) {
    dfn[x] = low[x] = ++cnt; sta[++top] = x; int flag = 0;
    for (int k = last[x], y; k; k = a[k].next) {
        ++flag;
        if (!dfn[y = a[k].y]) {
            tarjan(y);
            low[x] = min(low[x], low[y]);
            if (low[y] == dfn[x]) {
                ++num; int z;
                do {
                    z = sta[top--];
                    D[num].push_back(z);
                } while (z != y);
                D[num].push_back(x);
            }
        }
        else low[x] = min(low[x], dfn[y]);
    }
}

int K;

int check(int u) {
    if (D[u].size() == 1) return -1;
    if (D[u].size() == 2) return 0;
    int siz = 0;
    for (int x : D[u]) c[x] = u;
    for (int x : D[u]) {
        for (int k = last[x], y; k; k = a[k].next) {
            if (c[y = a[k].y] == u) ++siz;
        }
    }
    siz /= 2;
    return siz;
}
 
int calc1(int n) {
    int ans = ksm(K, n);
    for (int i = 1; i < n; ++i) 
        ans = (ans + ksm(K, gcd(n, i))) % mod;
    ans = 1ll * ans * ksm(n) % mod;
    return ans;
}


int binom(int n, int m) {
    if (n < m || n < 0 || m < 0) return 0;
    if (n == m || m == 0) return 1;
    return 1ll * fac[n] * ifac[n - m] % mod * ifac[m] % mod;
}

int main() {
    len = 1; memset(last, 0, sizeof last);
    int n, m; scanf("%d%d%d", &n, &m, &K);
    for (int i = 1; i <= m; ++i) {
        int x, y; scanf("%d%d", &x, &y);
        ins(x, y); ins(y, x);
    }
    fac[0] = ifac[0] = inv[0] = fac[1] = ifac[1] = inv[1] = 1;
    for (int i = 2; i <= K + m; ++i) {
        fac[i] = 1ll * fac[i - 1] * i % mod;
        inv[i] = 1ll * inv[mod % i] * (mod - mod / i) % mod;
        ifac[i] = 1ll * ifac[i - 1] * inv[i] % mod;
    }
    for (int i = 1; i <= n; ++i) if (!dfn[i]) 
        tarjan(i);
    int ans = 1;
    for (int i = 1; i <= num; ++i) {
        int flag = check(i);
        if (flag == -1) continue;
        if (!flag) {ans = 1ll * ans * K % mod; continue;}
        int siz = D[i].size();
        if (flag == siz) ans = 1ll * ans * calc1(siz) % mod;
        else ans = 1ll * ans * binom(flag + K - 1, K - 1) % mod;
    }
    printf("%d\n", ans);
    return 0;
}

无向图计数

8.png

妙不可言!


还是要言一下的。

还是 Burnside 引理,

$$|X/G|=\sum\limits_{g\in G}|X^g|$$

这里的 $g$ 其实对应着标号的变换 $i\rightarrow p_i$ 。

那对于一个排列 $p_i$ ,我们考虑不动点的个数。

这里的不动点即为重标号后图的形状不发生改变的图。

因为置换 $p_i$ 可以被拆成若干个循环置换(即环),证明过于简单,出度和入度都是 $1$,不是若干个环是什么。

我们考虑一个循环置换

$i\rightarrow p_i\rightarrow p_{p_i}\rightarrow\cdots\rightarrow i$

图中 存在一条循环置换内边 $(i,j)$,若要使图 不动

则需要满足存在边

$$(p_i,p_j)\\(p_{p_i},p_{p_j})\\~~~~~\vdots$$

也就是环上相邻距离为 $|i-j|$ 的点都必须要有边。

考虑有多少个这样的等价类。

也就是距离限制在 $[0,\lfloor\frac{L}{2}\rfloor]$ , $L$ 为环的大小,即 $\lceil\frac{L + 1}{2}\rceil$

再大就不存在这样的距离点对了,因为取 $\min(i,L-i)$

那么图在此环上不动的方案为 $2^{\lceil\frac{L + 1}{2}\rceil}$

考虑环间连边 $(i,j)$ ,设大小为 $L_1,L_2(L_1<L_2)$

为了方便起见,我们不妨重编号,设环的编号为 $c,d$。

于是满足存在边

$(c_1,d_1)\\(c_2,d_2)\\~~~~~\vdots\\(c_{L_1},d_{L_1})\\(c_{1},d_{L_1 +1})\\~~~~~\vdots\\(c_1,d_1)$

考虑这样需要走 $t$ 步才能完成一个循环,显然这个 $t=\operatorname{lcm}(L_1,L_2)$

也是有 $\frac{L_1 L_2}{t}=(L_1,L_2)$ 个等价类。

因此方案数为 $2^{(L_1,L_2)}$

然后就是考虑如何快速枚举排列,但是完全做不到。

观察到仅与环的大小有关,我们不妨进行整数拆分

于是答案为

$$\large\sum\limits_{k,\sum_{i=1}^k L_i=n\\L_{i}\le L_{i+1},i\in[1,n)}\frac{\prod\limits_{i=1}^{k}2^{\lceil\frac{L + 1}{2}\rceil}\prod\limits_{j\ne i} 2^{(L_1,L_2)}}{\prod\limits_{i=1}^k(L_i)!\prod\limits_{i=1}^n (c_i)!}$$

$c_i$ 表示大小为 $i$ 的环的个数,因为它们之间会计算重。

稍微解释一下,我们首先先把数分配到各个环,方案数为 $\frac{n!}{\prod\limits_{i=1}^k (L_i)!}$

然后去重,因为 $L_i=L_{i+1}$ 的话,是会算重的。

之后就是具体考虑了。

「TJOI / HEOI2016」求和

把 $\begin{Bmatrix}i\\j\end{Bmatrix}$ 拆开就好了。

using namespace std;
const int N = 2e5 + 5, mod = 998244353, W = mod - 1, G = 3;

int fac[N << 1], ifac[N << 1], inv[N << 1], cnt;
int pn[N << 1], p2[N << 1], w[N << 1], tr[N << 1];

il int add(int x, int y) {return x += y, x >= mod ? x - mod : x;}
il int sub(int x, int y) {return x -= y, x < 0 ? x + mod : x;}

il int ksm(int a, int b = mod - 2) {
    int ans = 1;
    for (; b; b >>= 1, a = 1ll * a * a % mod) 
        if (b & 1) ans = 1ll * ans * a % mod;
    return ans;
}

void init(int m) {
    int n = 1; for (; n <= (m << 1); n <<= 1); int wn = ksm(G, W / n);
    w[n >> 1] = 1; for (int i = (n >> 1) + 1; i < n; ++i) w[i] = 1ll * w[i - 1] * wn % mod;
    for (int i = (n >> 1) - 1; i; --i) w[i] = w[i << 1];
    fac[0] = fac[1] = inv[0] = inv[1] = ifac[0] = ifac[1] = p2[0] = 1; p2[1] = 2;
    for (int i = 2; i <= n; ++i) {
        fac[i] = 1ll * fac[i - 1] * i % mod;
        inv[i] = 1ll * inv[mod % i] * (mod - mod / i) % mod;
        ifac[i] = 1ll * ifac[i - 1] * inv[i] % mod;
        p2[i] = add(p2[i - 1], p2[i - 1]);
    }
    pn[1] = m + 1; for (int i = 2; i <= m; ++i) pn[i] = 1ll * (ksm(i, m + 1) - 1) * inv[i - 1] % mod;
}

void rev(int n) {
    if (cnt == n) return ;
    for (int i = 1; i < n; ++i) tr[i] = tr[i >> 1] >> 1 | ((i & 1) ? n >> 1 : 0);
}

void dft(int *g, bool op, int n) {
    rev(n); if (op) for (int i = 1; i < n; ++i) if (n - i < i) swap(g[i], g[n - i]);
    static ull f[N << 1]; for (int i = 0; i < n; ++i) f[i] = ((1ll * mod << 5) + g[tr[i]]) % mod;
    for (int p = 2, l = 1; p <= n; l = p, p <<= 1) {
        for (int i = 0; i < n; i += p) for (int j = 0, t; j < l; ++j) 
            t = w[j | l] * f[i | j | l] % mod, f[i | j | l] = f[i | j] + mod - t, f[i | j] += t;
        if (l == (1 << 10)) for (int i = 0; i < n; ++i) f[i] %= mod;
    } if (op) for (int i = 0, t = inv[n]; i < n; ++i) g[i] = f[i] % mod * t % mod;
    else for (int i = 0; i < n; ++i) g[i] = f[i] % mod;
}

il void px(int *f, int *g, int n) {for (int i = 0; i < n; ++i) f[i] = 1ll * f[i] * g[i] % mod;}

int f[N << 1], g[N << 1];

int main() {
    int n; scanf("%d", &n); init(n);
    f[0] = g[0] = 1; f[1] = mod - ifac[1]; g[1] = pn[1];
    for (int i = 2; i <= n; ++i) f[i] = (i & 1) ? mod - ifac[i] : ifac[i], g[i] = 1ll * pn[i] * ifac[i] % mod;
    int lim = 1; for (; lim <= (n << 1); lim <<= 1);
    dft(f, 0, lim); dft(g, 0, lim);
    px(f, g, lim); dft(f, 1, lim);
    int ans = 0;
    for (int i = 0; i <= n; ++i) ans = add(ans, 1ll * f[i] * p2[i] % mod * fac[i] % mod);
    printf("%d\n", ans);
    return 0;
}

一道例题

9.png

我们首先先考虑 $F = 1$ 的时候该怎么做,

首先我们的方案是这样的,

$$\begin{aligned}\sum\limits_{i=1}^La_i=\sum_{i=1}^L \sum_{j=1}^n[b_j=i]\end{aligned}$$

转化成图形,

$$(~+~+~+~\cdots ~+~)\\(~+~+~+~\cdots ~+~)\\~~~~~~~~~~~~~~~~\vdots\\(~+~+~+~\cdots ~+~)\\(~+~+~+~\cdots ~+~)\\$$

一共 $L$ 个括号,然后括号里面有一些 $0/1$ ,对于第 $i$ 个括号,第 $j$ 个 $0/1$ 表示第 $j$ 个括号有没有选 $i$

对于一种具体方案,我们可以采取乘法分配律的方式,把其拆成 $(0+1+\cdots)\times(1+0+\cdots)\times \cdots$ 的方式考虑贡献。

假设我们选择了对于每一个括号选出了一组 $x_i$ ,它的合法条件就是 $\forall i\in[1,L],[b_{x_i}=i]$ ,概率为 $\frac{1}{k^{L}}$ ,对答案贡献 $1$ 。

然后考虑有多少组这样的 $x_i$ ,显然就是 $n^{\underline{L}}$ ,于是期望就为 $\frac{n^{\underline{L}}}{k^{L}}$ 。

然后拓展到任意情况。

$$\begin{aligned}\sum_{i=1}^L {a_i}^F=\sum_{i=1}^L(\sum_{j=1}^n[b_j=i])^F\end{aligned}$$

转化成图形

$$(~+~+~+~\cdots ~+~)\times (~+~+~+~\cdots ~+~)\times\cdots\times (~+~+~+~\cdots ~+~)\\(~+~+~+~\cdots ~+~)\times (~+~+~+~\cdots ~+~)\times\cdots\times (~+~+~+~\cdots ~+~)\\~~~~~~~~~~~~~~~~\vdots\\(~+~+~+~\cdots ~+~)\times (~+~+~+~\cdots ~+~)\times\cdots\times (~+~+~+~\cdots ~+~)\\(~+~+~+~\cdots ~+~)\times (~+~+~+~\cdots ~+~)\times\cdots\times (~+~+~+~\cdots ~+~)$$

$L\times F$ 个括号,其中第 $L$ 行表示 $i$ 的贡献。

同样地,用乘法分配律进行计算,但是此时出现了一些问题,比如 $x_{i,j}=x_{i,k}$ 是合法的。

也就是对于同一行,我们允许存在本质相同的 $x$ ,那我们不妨枚举对于同一行,枚举有多少个本质不同的 $x$

于是对于同一行,假设有 $R$ 个不同的 $x$ ,那么我们需要让从中 $F$ 个括号选择一个 $x$ ,即把它们划分到 $R$ 个非空集合中,

方案数即为 $\begin{Bmatrix}F\\R\end{Bmatrix}$ 。

然后对于每一行,类似地进行此过程,然后背包卷起来即可。

假设总的本质不同的个数为 $T$ ,那么选出这样一组合法的 $x$ ,方案为 $n^{\underline{T}}$ ,单个方案的概率为 $\frac{1}{k^{T}}$

但是这样做是 $\Theta((FR)^2)$ ,但是 $T\ge 2333$ 则会被整除,所以背包大小开到 $2333$ 就可以了。

复杂度为 $\Theta(2333\cdot FR)$