更好的阅读体验：https://www.cnblogs.com/To-Carpe-Diem/p/19648636

大意

区间加，求 $a[l]^{a[l+1]^{a[l+2]^{\dots ^{a[r]}}}} \mod p$ 的值。

思路

对于这个指数塔，非常逆天，我们首先想到的肯定的是与降幂有关的内容，也就只有欧拉定理了，由于 $p$ 并非是质数，我们需要用扩展欧拉定理，那么什么是欧拉定理和扩展欧拉呢？

$\varphi(n)$ 就表示小于等于 $n$ 与 $n$ 互质的数的个数，$\varphi(1) = 1, \varphi(p) = p - 1$，这里的 $p$ 是质数。那么 $\phi(n)$ 应该怎么算呢？我们由素数分解定理，就可以有这样的公式：

$$n \prod_{p | n} (1 - \frac{1}{p})$$

这个过程我们是可以用线性筛预处理这个 $\varphi(n)$ 的。

好的，预处理讲完了，接下来讲欧拉定理，当 $\gcd(a, m) = 1$，那么 $a ^ {\varphi(m)} \equiv 1 \pmod m$，这个在模数为质数的时候就可以快速降幂，但是要是不是质数呢？没事，我们有扩展欧拉定理，其内容如下：

$$a ^ b \equiv \begin{cases} a ^ {b \pmod{\varphi(m)}} & \gcd(a, m) = 1 \\ a ^ b & \gcd(a, m) \neq 1, b < \varphi(m) \\ a ^ {b \pmod{\varphi(m)} + \varphi(m)} & \gcd(a, m) \neq 1, b \ge \varphi(m) \end{cases} \pmod{m}$$

好了，知道了这些，我们回到这个题目，对于这个指数塔，其指数一直取 $\varphi$ 显然最后会变成 $1$，那么要取多少次呢？我们想想对于 $\varphi(2 ^ k)$ 来说，其等于 $2 ^ {k - 1}$，对于质数是 $p - 1$，其如果是质数就减去一变成偶数，然后就会很快变小。

那么我们这个题直接写递归的话，递归层数最多就是 $\log$ 的层级，我们为了维护区间加和单点查询，我们直接用个树状数组维护即可，在递归的过程中，不断判断模数是否为 $1$，注意快速幂的地方，也要改一下。

代码

#include<iostream>
using namespace std;

#define int long long
const int MAXN = 2 * 1e7 + 5;
int a[MAXN], n, m;
int pri[MAXN], phi[MAXN], tot = 0;
int sum[MAXN];
bool vis[MAXN];

void init(){
	phi[1] = 1;
	for(int i = 2;i < MAXN;i ++){
		if(!vis[i]){
			phi[i] = i - 1;
			pri[++ tot] = i;
		}
		for(int j = 1;j <= tot && i * pri[j] < MAXN;j ++){
			vis[i * pri[j]] = 1;
			if(i % pri[j] == 0){
				phi[i * pri[j]] = phi[i] * pri[j];
				break;
			}
			phi[i * pri[j]] = phi[i] * (pri[j] - 1);
		}
	}
//	for(int i = 1;i < 5;i ++){
//		cout << phi[i] << ' ';
//	}
}

int lowbit(int x){
	return x & -x;
}

void add(int x, int k){
	while(x <= n){
		sum[x] += k;
		x += lowbit(x);
	}
}

int ask(int x){
	int res = 0;
	while(x){
		res += sum[x];
		x -= lowbit(x);
	}
	return res;
}

int qpow(int a, int b, int p){
	int res = 1;
	bool flag = 0;
	if(a >= p){
		flag = 1;
		a %= p;
	}
	while(b){
		if(b & 1) res = res * a;
		if(res >= p){
			res %= p;
			flag = 1;
		}
		a = a * a;
		if(a >= p){
			a %= p;
			flag = 1;
		}
		b >>= 1;
	}
	return flag ? res + p : res;
}

int solve(int l, int r, int p){
	int val = a[l] + ask(l);
	if(p == 1) return 1;
	if(l == r){
		if(val >= p) return val % p + p;
		else return val;
	}
	int cnt = solve(l + 1, r, phi[p]);
	return qpow(val, cnt, p);
}

signed main(){
	cin.tie(0) -> ios::sync_with_stdio(0);
	init();
	cin >> n >> m;
	for(int i = 1;i <= n;i ++){
		cin >> a[i];
	}
	for(int i = 1;i <= m;i ++){
		int op, l, r, x;
		cin >> op >> l >> r >> x;
		if(op == 1) add(l, x), add(r + 1, -x);
		else cout << solve(l, r, x) % x << '\n';
	}
	return 0;
}

# T5 数据结构题 题解

我们将询问转化为如下问题

定义 $f(l,r)$ $(l \le r)$ 如下：

当 $l=r$ 时，$f(l,r)=a_l$；否则，$f(l,r)=a_l^{f(l+1,r)}$

每次操作 $2$，输出 $f(l,r)\bmod p$

那我们该如何维护呢？

这里我们需要一个前置知识，叫做扩展欧拉定理，即：

$$a^b\equiv \begin{cases}a^{b \bmod \varphi(p)}(b<\varphi(p))\\a^{b \bmod \varphi(p)+\varphi(p)}(b\ge\varphi(p))\end{cases}\pmod p$$

那么

$$f(l,r)\equiv a^{f(l+1,r)\bmod \varphi(p)+[b\ge \varphi(p)]\times \varphi(p)}\pmod p$$

那么，求解 $f(l,r)\bmod p$ 就变成了求解 $f(l+1,r)\bmod \varphi(p)$，并判断 $f(l+1,r)$ 与 $p$ 的关系

然后我们就可以递归求解了

递归边界的话，则有三个

当 $l=r$ 时，$f(l,r)\bmod p\equiv a_l\pmod p$

当 $p=1$ 时，$f(l,r)\bmod p\equiv 0\pmod p$

当 $a_l=1$ 时，$f(l,r)\bmod p\equiv 1\pmod p$

那么这个递归的复杂度是多少呢？

我们分析一下将 $\varphi(p)\to p$ 直到 $p=1$ 的时间复杂度是多少

由 $\varphi(p)=p\prod_{i=1}^{n} \frac{p_i-1}{p_i}$ $(p=\prod_{i=1}^{n}{p_i}^{k_i})$可知

当 $p$ 为偶数时，上述式子必有一项是 $\frac{1}{2}$，所以 $\varphi(p)\le\frac{1}{2}p$

当 $p$ 为奇数时，上述式子的 $p_i-1$ 必是偶数，因此 $\varphi(p)$ 为偶数，回到 $p$ 为偶数的情况

因此最多经过 $O(logn)$ 次递归就可以得出答案

至于判断 $f(l+1,r)$ 与 $p$ 的关系，可以让递归函数返回一个结构体，结构体第一项存 $f(l+1,r)\bmod \varphi(p)$ 的值，第二项存 $f(l+1,r)$ 与 $\varphi(p)$ 的大小关系，前者大于等于后者，这一项就是 $1$，反之则为 $0$

区间和我们用树状数组维护差分即可

时间复杂度：$O(mlogqlogn)$

f[i][j]统一定义为i个小球放到j个盒子里的方案数

1.m^n

2.m!/(m-n)!

3.f[i][j]=j*f[i-1][j]+(m-j+1)*f[i-1][j-1]

  考虑容斥可以O(n)

4.第二类斯特林数S[n][1]+...+S[n][m]

  O(n^2)直接递推S[i][j]=S[i-1][j-1]+j*S[i-1][j]

  O(nlogn)NTT,斯特林数反演

5.[n<=m]

6.S[n][m]

7.C(n+m-1,m-1)

8.C(m,n)

9.C(n-1,m-1)

10.f[i][j]=f[i][j-1]+f[i-j][j]

    考虑球的数量>=根号n的盒子的个数＜=根号n个可以分块O(n^1.5)

    五边形数定理可优化到O(nlogn)

11.[n<=m]

12.f[i][j]=f[i-1][j-1]+f[i-j][j]  自然数拆分

    同10

更好的阅读体验：https://www.cnblogs.com/To-Carpe-Diem/p/19645638

更好的阅读体验（加强版）：https://www.cnblogs.com/To-Carpe-Diem/p/19645952

$\newcommand{\binom}[2]{{#1 \choose #2}}$

大意

$n$ 对情侣，恰好 $k$ 对在 $2 \times n$ 的电影院中坐一起的方案数。

思路

很好的题目，使得我的大脑旋转。

首先我们先定义函数 $f(n, k)$ 表示 $n$ 对情侣有 $k$ 对恰好坐到一块的方案数。首先我们要从 $n$ 对情侣中选择 $k$ 对，这个是 $\binom{n}{k}$ 的，再从 $n$ 排选择 $k$ 排，这个也是 $\binom{n}{k}$ 的，考虑到这 $k$ 对情侣间也有先后顺序，贡献就是 $k!$，两人可以换位，贡献是 $2 ^ k$，剩下有 $n - k$ 对情侣，我们只需要将其错排即可。

定义 $g(m)$ 表示 $m$ 对情侣错排的方案数，我们考虑这个怎么求。这个我们可以利用容斥原理，我们考虑直接计算至少 $j$ 对和睦的方案数，那么这个的贡献与上面的类似，应当是 $\binom{m}{j} ^ 2 j! 2 ^ j (2(m - j))!$，那么由容斥可知：$g(m) = \sum_{j = 0} ^ {m}(-1) ^ j \binom{m}{j} ^ 2 j! 2 ^ j (2(m - j))!$

那么我们合并一下整个式子，就是：$f(n, k) = \binom{n}{k} ^ 2 k ! 2 ^ k g(n - k) = \binom{n}{k} ^ 2 k ! 2 ^ k \sum_{j = 0} ^ {n - k}(-1) ^ j \binom{n - k}{j} ^ 2 j! 2 ^ j (2(n - k - j))!$

这个式子我们是可以直接求的，于是就完成了。

接下来进入正题，我们注意到刚刚的弱化版内的 $f(n, k) = \binom{n}{k} ^ 2 k ! 2 ^ k D(n - k) $，且 $D(n) = \sum_{i = 0} ^ {n} (-1) ^ i\binom{n}{i} ^ 2 i! 2 ^ i (2(n - i))!$，我们考虑对于 $D(n)$ 进行化简.

$\sum_{i = 0} ^ {n}(-1) \binom{n}{i} ^ 2 i! 2 ^ i (2(n - i)) != (n!) ^ 2 \sum_{i = 0} ^ n \frac{(2(n - i))!}{(n - i)! ^ 2} \frac{(-2) ^ i}{i!}$

这里我们就可以直接做卷积了，但是问题在于这个题目要求的复杂度太过苛刻，卷积无法通过此题，我们考虑构造生成函数。

我们设：$F(x) = (n!) ^ 2 \sum_{i = 0} ^ n \frac{(2(n - i))!}{(n - i)! ^ 2} \frac{(-2) ^ i}{i!} x^i,G[n] = \frac{(2n)!}{n!^2},P[n] = \frac{(-2) ^ i}{n !}$。那么，由离散卷积可知：$F(x) = G(x) * P(x)$

接下来，我们只需要分别对于 $G(x)$ 和 $P(x)$ 化简即可。首先，对于 $G(x)$ 来说，我们可以利用**广义二项式定理**，那么什么是广义二项式定理呢？对于任意实数 $\alpha$，都有 $(1 + z) ^ \alpha = \sum_{i = 0} ^ {\infty} \binom{\alpha}{i} z ^ i$，那么说我们就可以化简 $G(x)$ 了：$G(x) = \sum_{i = 0} \frac{(-2x) ^ i}{i!} x ^ i = \sum_{i = 0} \binom{2i}{i}x^i = \frac{1}{\sqrt{1 - 4x}}$对于 $P(x)$ 来说，直接化简：$P(x) = \sum_{i = 0} \frac{(-2x)!}{i!} = e ^ {-2x}$

经过化简，我们可以最终得到：$F(x) = \frac{e ^ {-2x}}{\sqrt{1 - 4x}}$对于这个生成函数，为了得到与自身相关的式子进行递推，我们选择对其求导。$F'(x) = \frac{8x * e ^ {-2x}}{(1 - 4x) ^ \frac{3}{2}} = \frac{8x}{1 - 4x} F(x)$整理一下：$F'(x) = 4xF'(x) + 8xF(x)$。提取 $[x ^ n]$ 的系数：$F'[n] = 4xF'[n - 1] + 8xF[n - 1]$。稍施小计，我们可以直接得到关于 $F[n]$ 的递推式：$(n + 1)F[n + 1] = 4nF[n] + 8F[n - 1]$

你可能以为万事大吉了，但是问题是我们还有个 $(n!) ^ 2$ 的系数在最开始被我们提出去了，我们要把这玩意弄回来，带入 $F[n] = \frac{D(n)}{n!} ^ 2$：$(n + 1)\frac{D[n + 1]}{(n + 1)!} = 4n \frac{D[n]}{n!^2} + 8 \frac{D[n - 1]}{(n - 1)! ^ 2}$我们就可以得到关于 $D[n]$ 的递推式：$D[n + 1] = 4n(n + 1)D[n] + 8n ^ 2(n + 1)D[n - 1]$

直接 $O(n)$ 递推即可。

代码

#include<iostream>
using namespace std;

#define int long long
const int MOD = 998244353;
const int MAXN = 2e3 + 5;

int C[MAXN][MAXN];
int fac[MAXN];
int g[MAXN], pow2[MAXN];

void init(){
	C[0][0] = 1;
	for(int i = 1;i < MAXN;i ++){
		C[i][0] = C[i][i] = 1;
		for(int j = 1;j < i;j ++){
			C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % MOD;
		}
	}
	fac[0] = 1;
	for(int i = 1;i < MAXN;i ++){
		fac[i] = (fac[i - 1] * i) % MOD;
	}
	pow2[0] = 1;
	for(int i = 1;i < MAXN;i ++){
		pow2[i] = pow2[i - 1] * 2 % MOD;
	}
	for(int m = 0;m <= 1000;m ++){
		g[m] = 0;
		for(int j = 0;j <= m;j ++){
			int a = (j % 2 == 0) ? 1 : MOD - 1;
			int res = C[m][j] * C[m][j] % MOD;
			res = (res * fac[j]) % MOD;
			res = (res * pow2[j]) % MOD;
			res = (res * fac[2 * (m - j)]) % MOD;
			res = (res * a) % MOD;
			g[m] = (g[m] + res) % MOD;
		}
 	}
	return;
}

int f(int n, int k){
	int res = (C[n][k] * C[n][k]) % MOD;
	res = (res * fac[k]) % MOD;
	res = (res * pow2[k]) % MOD;
	res = (res * g[n - k]) % MOD;
	return res;
}

int T, n, k;

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	init();

	cin >> T;

	while(T --){
		cin >> n;
		for(int i = 0;i <= n;i ++){
			cout << f(n, i) << '\n';
		}
	}

	return 0;
}