生成函数

“鲜花是自然的光彩，生命是世界的奇迹。”

观前提醒

本文设有大量，请确保在所有数学公式渲染完毕之后再阅读，否则会影响阅读体验。

定义一个无穷级数，即一个长度为无限的序列，设：

$\nonumber g(x)=a_0+a_1x+a_2x^2+\cdots+a_nx^n+\cdots$

一般设定，则称是序列的生成函数（）。

为什么 x 有限制？

毕竟是一个无穷级数，根据一些微积分初步的知识，当的时候，该数列是收敛的。而实际上，只有当收敛时，这个才发挥了作用。

生成函数与乘法原理：单项式计算

砝码称重

现有个砝码，重量为，求使用这个砝码能够称出多少的重量，以及每一种重量有多少种称法。

生成函数的一大重要思想体现于——乘法原理与多项式卷积互相转换。

我们考虑设定表示重量为的砝码的生成函数。

我们设定无限长的数列，表示的实际意义：表示重量为的选取方案。对于每一个砝码，都有，即选和不选的选择，那么，我们可以求出每一个砝码的生成函数：

分别表示，重量为的砝码，就可以称出和，分别有一种称法。

我们设定一个不定次多项式表示为重量为的称法有种，此时只是我们设定的一个不影响答案的自变量。

好了，我们已经将三种砝码的生成函数都求出来了，那如何求得答案，这里首先给出结论：

答案便是：的所有系数，对应关系与我们设定的多项式表达一致。

先来验证一下是否正确：

$\begin{align} f(x)&=\nonumber f_1(x)\ast f_2(x)\ast f_3(x) \\&=\nonumber (1+x)(1+x^2)(1+x^3) \\&=\nonumber (1+x+x^2+x^3)(1+x^3) \\&=\nonumber 1+x+x^2+2x^3+x^4+x^5+x^6 \end{align}$

意味着，的称法分别是：。经过手玩验证，这是正确的。

为什么是正确的？

前面我们讲过：

乘法原理与多项式卷积互相转换。

如果我们仅从原问题出发，这也是一种乘法原理的计算，我们设定的多项式只是从一种并不抽象的代数方式来解决乘法原理。

对于我们展开的卷积：

$\nonumber (1+x)(1+x^2)(1+x^3)$

我们可以考虑多项式卷积的进行过程，从每一个括号中选出一项进行计算，便可以理解为，当前砝码是否会被使用，这在生成函数中也是对应的。

生成函数与乘法原理：多项式计算

我们对上述问题进行变式。

砝码称重之二

现有种砝码，重量为，分别有个，求使用这种砝码能够称出多少的重量，以及每一种重量有多少种称法。

容易发现，这样我们构造出的生成函数并不只的计算了，所以考虑应当怎么计算：

观察得出，有无限项，我们并不能在有限时间呢对其进行多项式卷积。这个时候就要考虑生成函数的另一种使用技巧了。

我们先来考虑另一个问题：

分苹果

现有种苹果，第种苹果有无限个，求从这些苹果中选出个的方案数。

转换成方程，变成求：

其中的解数。

考虑用隔板法解决，设定变成求：

的方案数（正整数解），就可以使用隔板法解决了：即在个小球（个间隙）中放个隔板的方案数。

则答案为。

我们用生成函数的方式来考虑：对于每一种苹果，我们设定多项式表示选个苹果的方案数为。

则对于任意苹果有

同样是无限项，无法计算，那我们是否有办法，可以让无限项转换为有限项呢。当然是有的。

容易发现，此是一个无限项的等比数列，所以我们可以得到：

差项相减得到：，所以有：

同样地，对于砝码的生成函数，我们也能得到：

这是无限序列多项式的封闭形式。

这样就可以利用多项式卷积得到最后答案，而最后答案可能是一个带分式的多项式，就需要将封闭形式重新拆分成无限项形式得到最终某一项的系数。

关于另一种化简的探讨

按照更官方的来讲，生成函数的化简实际上依据的是牛顿二项式定理。

一般二项式定理：

牛顿将其扩展到了指数范围，得到牛顿二项式定理：

其中：

$\nonumber \displaystyle\binom nm=\frac{n(n-1)(n-2)\cdots(n-m+1)}{m!}$

当时，得到，因为当时，，所以，即二项式定理。

据此，便可以推导出：

$\begin{align} \nonumber f(x)&=1+x+x^2+x^3+\cdots \\&=\nonumber \frac{1}{1-x} \end{align}$

设，得到：

其中：

$\begin{align} \nonumber \binom{-1}i&=\frac{(-1)(-1-1)\cdots(-1-i+1)}{i!} \\ &=\nonumber \frac{(-1)^i[1\times 2\times 3\times\cdots\times i]}{i!} \\ &=\nonumber (-1)^i \end{align}$

所以有：

$\begin{align} (1+x)^{-1}&=\nonumber \sum_{i=0}^{\infty}(-1)^i\times x^i \\&=\nonumber \sum_{i=0}^{\infty}(-1)^i(-x)^i \\&=\nonumber \sum_{i=0}^{\infty}x^i \\ &=\nonumber 1+x+x^2+x^3+\cdots \end{align}$

当然，这是一个逆推的过程，一般证明时候用。

生成函数的推算

一般而言，最后得到的式子有两种：

，即有限项；

，即无限项。

两者都可以化简，对于无限项，上述提到，而对于有限项，我们也可以化简为。

这样的话，相乘得到的很多式子都可以分子分母互相化简，从而得到的答案式子十分简单，然后就可以用高精度或者模数或者轻松解决了。

普通生成函数（OGF）

序列（有穷或无穷皆可）的普通生成函数（）定义为形式幂级数，形式如：

$\nonumber G(x)=\sum_{i}a_ix^i$

如果序列有通项公式，则其的系数就是其通项公式。

运算规则

设序列的分别为。

满足相加性，表现为：

$\nonumber F(x)\pm G(x)=\sum_{i}(a_i\pm b_i)x^i$

即是序列的。

也有卷积，形式为：

$\nonumber F(x)\ast G(x)=\sum_{i}x^i\sum_{j=0}^{i}a_j\cdot b_{i-j}$

即是序列的。

在上文中我们提及的所有与生成函数有关的都是。

指数生成函数（EGF）

序列的指数生成函数（）定义为形式幂级数，形式为：

$\nonumber \hat F(x)=\sum_{i}a_i\times\frac{x^i}{i!}$

一般用于解决组合问题，而一般用于解决排列问题。

我们考虑下面这个问题：

序号选取

现在有个带标号的小球，从其中选取个组成一个序列，求不同的序列个数。

这是一个很经典的排列问题，与原先问题不同的地方在于，顺序会影响结果。

如果我们考虑用来做的话，可以用背包实现（前面的题同样也可以），但每一次转移的贡献并不一定是，需要乘上一个组合数，会导致问题变得麻烦。而对于这一种题，我们也有一个很显而易见的做法。

将所有组合的方案求出，并对于每一个组合的方案计算其排列数，相加即可。

多重集排列数（重复元素排列）

对于一个长度为的序列，设表示元素在序列中出现的个数，一共有个不同的元素，则该序列的全排列个数为：

$\frac{n!}{\displaystyle\prod_{i=1}^{m} c_i!}$

理解也较简便，我们先将所有重复元素视为本质不同元素，而对于这些重复元素，将其交换并不会产生新的排列，而其交换的排列方案即是，即可。

考虑下面一个比较实在的问题：

排水果

现在有个苹果，个梨，个西瓜，求任意选个水果排成一列能组成的排列方案数。

考虑用来解决这个问题。

设指数型生成函数表示水果的选择情况，则有：

苹果：

梨：

西瓜：

相乘所得的的系数就是我们需要的答案了。

封闭形式

当然，这复杂的多项式卷积肯定不是我们想要的结果，所以我们的第一步还是考虑将优化为封闭形式。

如果是有限项的话，并不能将其化简为单项式封闭形式，的封闭形式仅针对无限项。

我们来解决最简单的无限项，将其化为封闭形式：

$\begin{align} \sum_{i=0}^{\infty}\frac{1}{i!}x^i &=\nonumber 1+x+\frac{x^2}{2!}+\frac{x^3}{3!}+\cdots+\frac{x^{\infty}}{\infty!} \\&=\nonumber e^x \end{align}$

其推导需要用到泰勒展开，~~笔者没学，所以不写。~~

给出一些常见的无穷项的封闭形式写法：

$\begin{align} \hat G(x)&=\nonumber 1+x+\frac{x^2}{2!}+\frac{x^3}{3!}+\cdots+\frac{x^\infty}{\infty!}&=&e^x \\ \hat G(x)&=\nonumber 1-x+\frac{x^2}{2!}-\frac{x^3}{3!}+\cdots\pm\frac{x^\infty}{\infty!}&=&e^{-x} \\ \hat G(x)&=\nonumber 1+\frac{x^2}{2!}+\frac{x^4}{4!}+\cdots+\frac{x^{2\infty}}{(2\infty)!}&=&\frac{e^x+e^{-x}}{2} \\ \hat G(x)&=\nonumber x+\frac{x^3}{3!}+\frac{x^5}{5!}+\cdots+\frac{x^{2\infty+1}}{(2\infty+1)!}&=&\frac{e^x-e^{-x}}{2} \\ \hat G(x)&=\nonumber x+\frac{x^2}{2}+\frac{x^3}{3}+\frac{x^4}{4}+\cdots+\frac{x^\infty}{\infty}&=&\ln\left(\frac{1}{1-x} \right) \\ \hat G(x)&=\nonumber x-\frac{x^2}{2}+\frac{x^3}{3}-\frac{x^4}{4}+\cdots\pm\frac{x^\infty}{\infty}&=&\ln\left(1+x\right) \\ \hat G(x)&=\nonumber x^1-\frac{x^3}{3!}+\frac{x^5}{5!}-\frac{x^7}{7!}+\frac{x^9}{9!}-\cdots&=&\sin x \\ \hat G(x)&=\nonumber x^0-\frac{x^2}{2!}+\frac{x^4}{4!}-\frac{x^6}{6!}+\frac{x^8}{8!}-\cdots&=&\cos x \\ \hat G(x)&=\nonumber x+\left(\frac{1}{2}\times\frac{x^3}{3}\right)+\left(\frac{1\times3}{2\times4}\times\frac{x^5}{5}\right)+\left(\frac{1\times3\times5}{2\times4\times6}\times\frac{x^7}{7} \right)+\cdots&=&\arcsin x \\ \hat G(x)&=\nonumber 1+\frac{a^{\underline 1}}{1!}x+\frac{a^{\underline 2}}{2!}x^2+\frac{a^{\underline 3}}{3!}x^3+\cdots&=&(1+x)^a \end{align}$

指数型生成函数卷积

与类似，也存在卷积，其计算方式如下：

$\begin{align} \hat F(x)\ast \hat G(x)&=\nonumber \left(\sum_{i=0}^{\infty}a_i\frac{x^i}{i!} \right) \left(\sum_{i=0}^{\infty}b_i\frac{x^i}{i!} \right) \\&=\nonumber \sum_{i=0}^{\infty}\left(\sum_{i=0}^{n}\frac{a_ix^i}{i!}\cdot\frac{b_{n-i}x^{n-i}}{(n-i)!} \right)x^n \\&=\nonumber \sum_{n=0}^{\infty}\left(\sum_{i=0}^{n}\binom{n}{i}a_ib_{n-i} \right)\frac{x^n}{n!} \end{align}$

因此，是序列的。

EGF 的变换

我们考虑对于我们应该如何求出其某一项的系数，因为生成函数都是以的形式存在的。

所以，实际上，对于，其就是。

那对于呢，我们考虑用，这样就会得到：

实际上，作为形式幂级数，无论是还是，都对结果没有影响，所以有：

如果作为，则其第项系数为；如果作为，则其第项系数为。

EGF 的使用

排列与圆排列

对于有个不重复元素的序列，其排列有种，其为：

注意：这是而不是。其应该是：

什么是圆排列？

圆排列又称环排列。指有一个有个槽位的圆环，同样有一个长度为的不重复元素序列，将其填入个槽位中，会得到很多的填法。

对于每一个填法，我们将圆环展开并无限循环，得到的所有本质不同的无限元素串的个数为该序列的圆排列数。举个例子，对于圆排列来说，是同一种圆排列。

对于一个长度为的不重复元素序列，其圆排列数为。

而对于有个不重复元素的圆排列，其为：

对于圆排列生成函数的推导

首先化简：

$\nonumber \sum_{n=1}^\infty\frac{(n-1)!}{n\times(n-1)!}x^n=\sum_{n=1}^\infty\frac{x^n}{n}$

然后通过求导得到：。

然后将求得的导数进行积分，通过公式，得到：。

最后化简得到：。

容易发现，这两者有一个奇妙的关系：。在带标号计数指数函数计数问题中，只要我们能够把一个大问题拆分成若干个子问题，就会有类似的结论。

错排问题

有个不同的信封，其对应了个不同的邮箱，问所有信封都放错的方案数。

给定一个长度为序列，问满足的排列数。

设长度为的序列（默认无重复元素）的错排数为，我们先手玩几组小数据，得到：

~~然后我们放到 oeis 跑一跑，~~，得到错排数的通项公式：

$\begin{align} D(n)&=n!\left( \frac{(-1)^0}{0!}+\frac{(-1)^1}{1!}+\frac{(-1)^2}{2}+\frac{(-1)^3}{3!}+\cdots+\frac{(-1)^n}{n!} \right) \nonumber \\ D(n)&=\nonumber n!\times\sum_{i=0}^{n}\frac{(-1)^i}{i!} \end{align}$

容易发现，这个公式长得很像一个，但又不完全像，我们尝试代入使其成为形式幂级数，得到：

$\hat F(x)=\sum_{i=0}^{\infty}\frac{(-1)^i}{i!}x^i=e^{-x}$

则有：

$D(n)=n!\ast\hat F(x)=n!\times(\frac{1}{e})^x$

其第项系数为：。

容易发现这是一个实数，但错排数显然是一个整数，所以我们做一些调整，经过各路数学家的验证，得到错排数的简单公式：

$D(n)=\left\lfloor \frac{n!}{e}+\frac{1}{2} \right\rfloor$

也可以直接通过四舍五入。

其写为：

$\hat D(x)=\exp\left( \ln(\frac{1}{1-x})+x \right)$

错排问题递推公式推导

对于当前第封信，我们有步处理：

对于当前信，我们可以放在除了当前邮箱的另外个邮箱中，因此有种排法。
讨论另外封信的错排问题。

设如果第封信占据了第个邮箱（），即令，那对于，我们分以下两种情况来讨论：

如果，则对剩下的封信进行错排，不参与贡献，此时贡献为。
如果，则有种取值（），而除了之外的所有元素都存在了种取值（除开之外），此时参与贡献，相当于除了之外的错排问题，总贡献为。

根据加法原理，得到答案为。

但事实上，对于一个，其有种分类，所以再使用乘法原理得到答案，所以真正的递推公式应该是：

$\begin{align} D(1)&=0,D(2)=1\nonumber \\ D(n)&=(n-1)\Big( D(n-1)+D(n-2) \Big) \nonumber \end{align}$

带标号无向连通图计数

给定一张有个结点（从标号）的无向图，任意两点之间都可以有连边，问使得两两结点之间连通的连边方案数。

首先给出带标号无向图计数的生成函数：

$\hat f(x)=\sum_{n=0}^{\infty}2^{n(n-1)}\cdot\frac{x^n}{n!} \nonumber$

第项系数为。

根据一个~~我不会证~~的定理，对于一张无向图，其全图计数与其联通图计数的生成函数满足性质：

$\hat g(x)=\ln\hat f(x)$

在「排列与圆排列」中也提及过，很多很多的都存在这个性质，虽然证法和用法不同，但好像都是这个式子。

例题

拯救世界

题目简介

题目名称：拯救世界
题目来源：洛谷月赛
评测链接：https://www.luogu.com.cn/problem/P2000

形式化题意：有种石头，每种有不同要求，设其块数为，有：

为的倍数；
；
；
为的倍数；
；
为的倍数
；
为的倍数
为的倍数；
。

求选择块石头的方案个数。

数据范围：

显然的生成函数。

$\begin{align} f_1(x)&=\nonumber \frac{1}{1-x^6} ,& f_2(x)&=\nonumber \frac{1-x^{10}}{1-x} \\ f_3(x)&=\nonumber \frac{1-x^6}{1-x} ,& f_4(x)&=\nonumber \frac{1}{1-x^4} \\ f_5(x)&=\nonumber \frac{1-x^8}{1-x} ,& f_6(x)&=\nonumber \frac{1}{1-x^2} \\ f_7(x)&=\nonumber \frac{1-x^2}{1-x} ,& f_8(x)&=\nonumber \frac{1}{1-x^8} \\ f_9(x)&=\nonumber \frac{1}{1-x^{10}} ,& f_{10}(x)&=\nonumber \frac{1-x^4}{1-x} \end{align}$

然后相乘，消次：

$\begin{align} ans=&\nonumber \frac{1}{1-x^6}\times\frac{1-x^{10}}{1-x}\times\frac{1-x^6}{1-x}\times\frac{1}{1-x^4}\times\frac{1}{1-x^2} \\&\nonumber \times\frac{1-x^2}{1-x}\times\frac{1}{1-x^8}\times\frac{1}{1-x^{10}}\times\frac{1-x^4}{1-x} \\ =&\nonumber \frac{1}{(1-x)^5} \end{align}$

最后得到的无限次多项式则为：

$\nonumber A(x)=(1+x+x^2+x^3+\cdots)^5$

根据二项式定理，可以知道：

$\nonumber (1-x)^{-n}=\sum_{i=0}^{\infty}\mathbb C(n+i-1,i)x^i$

所以第项的系数就是也就是。

当时，得到答案：

$\begin{align} \nonumber ans&=\frac{(n+4)!}{4!\times n!} \\ &=\nonumber \frac{(n+1)(n+2)(n+3)(n+4)}{24} \end{align}$

然后用高精解决分子，再高精除低精得到答案。注意要一边乘一边进位，避免越过模数，~~被 auto 耍了。~~

AC Code

// ----- Eternally question-----
// Problem: P2000 拯救世界
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P2000
// Memory Limit: 128 MB
// Time Limit: 500 ms
// Written by: Eternity
// Time: 2023-01-11 10:10:36
// ----- Endless solution-------

#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ putchar(x?'1':'0'); }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
const int MAXN=1e6+10;
const int P=998244353,G=3,invG=332748118;
char N[MAXN];
ll A[MAXN],B[MAXN],C[MAXN],D[MAXN],ans[MAXN];
inline int qPow(ll a,ll b)
{
	ll res=1;
	while(b)
	{
		if(b&1) res=res*a%P;
		a=a*a%P;b>>=1;
	}
	return res;
}
int Rev[MAXN],Tot,Bit;
inline void NTT(ll a[],int inv)
{
	for(int i=0;i<Tot;++i)
		if(i<Rev[i]) std::swap(a[i],a[Rev[i]]);
	for(int mid=1;mid<Tot;mid<<=1)
	{
		ll w1=qPow(inv==1?G:invG,(P-1)/(mid<<1));
		for(int i=0;i<Tot;i+=mid*2)
		{
			ll wk=1;
			for(int j=0;j<mid;++j,wk=wk*w1%P)
			{
				ll x=a[i+j],y=a[i+j+mid]*wk%P;
				a[i+j]=(x+y)%P,a[i+j+mid]=(x-y+P)%P;
			}
		}
	}
	if(inv==-1)
	{
		ll iv=qPow(Tot,P-2);
		for(int i=0;i<Tot;++i) a[i]=a[i]*iv%P;
	}
}
int LenE,Len;
inline void Mul(ll a[],ll b[])
{
	NTT(a,1),NTT(b,1);
	for(int i=0;i<Tot;++i) a[i]=a[i]*b[i]%P;
	NTT(a,-1);
	for(int i=0,x=0;i<Tot;++i)
	{
		a[i]=a[i]+x;
		x=a[i]/10,a[i]%=10;
		if(a[i]) LenE=i+1;
	}
}
inline void debug()
{
	puts("debug start:");
	for(int i=Len-1;i>=0;--i) write(A[i]);puts("");
	for(int i=Len-1;i>=0;--i) write(B[i]);puts("");
	for(int i=Len-1;i>=0;--i) write(C[i]);puts("");
	for(int i=Len-1;i>=0;--i) write(D[i]);puts("");
	puts("debug end.");
}
int main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	scanf("%s",N);
	Len=strlen(N);
	std::reverse(N,N+Len);
	for(int i=0;i<Len;++i) A[i]=N[i]-'0';
	int LenA=Len,LenB=0,LenC=0,LenD=0;
	for(int i=0,x=1;i<LenA;++i)
	{
		A[i]=A[i]+x;
		x=A[i]/10,A[i]%=10;
		if(A[i]) LenB=i+1;
	}
	for(int i=0,x=1;i<LenB;++i)
	{
		B[i]=A[i]+x;
		x=B[i]/10,B[i]%=10;
		if(B[i]) LenC=i+1;
	}
	for(int i=0,x=1;i<LenC;++i)
	{
		C[i]=B[i]+x;
		x=C[i]/10,C[i]%=10;
		if(C[i]) LenD=i+1;
	}
	for(int i=0,x=1;i<LenD;++i)
	{
		D[i]=C[i]+x;
		x=D[i]/10,D[i]%=10;
		if(D[i]) Len=i+1;
	}
	while((1<<Bit)<(Len*4)) ++Bit;
	Tot=1<<Bit;
	for(int i=0;i<Tot;++i) Rev[i]=(Rev[i>>1]>>1)|((i&1)<<(Bit-1));
	// debug();
	Mul(A,B),Mul(A,C),Mul(A,D);
	int Lenans=0;
	for(int i=LenE-1,x=0;i>=0;--i)
	{
		x=x*10+A[i];
		ans[i]=x/24,x%=24;
		if(ans[i]&&(!Lenans)) Lenans=i+1;
	}
	if(!Lenans) Lenans=1;
	for(int i=Lenans-1;i>=0;--i) write(ans[i]);
	return 0;
}
/*

*/

城市规划

题目简介

题目名称：城市规划
题目来源：中国国家集训队第二次作业

评测链接：https://www.luogu.com.cn/problem/P4841

形式化题意：求出个点的简单（无重边无自环）有标号无向连通图数目，对取模。

数据范围：

似乎用和都可以求解。我们这里用来实现。

个点的带标号任意无向图的为：

则设连通的为，则有：，所以对进行多项式即可。

AC Code

// ----- Eternally question-----
// Problem: P4841 [集训队作业2013]城市规划
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P4841
// Memory Limit: 125 MB
// Time Limit: 2000 ms
// Written by: Eternity
// Time: 2023-01-11 16:20:25
// ----- Endless solution-------

#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ putchar(x?'1':'0'); }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
const int MAXN=1e6+10;
const int Mod=1004535809,G=3;
int N;
inline ll qPow(ll a,ll b)
{
	ll res=1;
	while(b)
	{
		if(b&1) res=res*a%Mod;
		a=a*a%Mod;b>>=1;
	}
	return res;
}
ll A[MAXN],B[MAXN],C[MAXN],invB[MAXN],Mul[MAXN];
int Rev[MAXN],Tot,Bit;
inline void NTT(ll a[],int n,int inv)
{
	int invG=qPow(G,Mod-2);
	for(int i=0;i<n;++i)
		if(i<Rev[i]) std::swap(a[i],a[Rev[i]]);
	for(int mid=1;mid<n;mid<<=1)
	{
		ll w1=qPow(inv==1?G:invG,(Mod-1)/(mid<<1));
		for(int i=0;i<n;i+=mid*2)
		{
			ll wk=1;
			for(int j=0;j<mid;++j,wk=wk*w1%Mod)
			{
				ll x=a[i+j],y=a[i+j+mid]*wk%Mod;
				a[i+j]=(x+y)%Mod,a[i+j+mid]=(x-y+Mod)%Mod;
			}
		}
	}
	if(inv==-1)
	{
		ll iv=qPow(n,Mod-2);
		for(int i=0;i<n;++i) a[i]=a[i]*iv%Mod;
	}
}
void Inverse(ll a[],ll b[],int n)
{
	static ll tmp[MAXN];
	if(n==1) return (b[0]=qPow(a[0],Mod-2)),void();
	Inverse(a,b,n>>1);
	for(int i=0;i<n;++i) tmp[i]=a[i],tmp[n+i]=0;
	int L=0;
	while(!(n>>L&1)) ++L;
	for(int i=1;i<(n<<1);++i) Rev[i]=(Rev[i>>1]>>1)|((i&1)<<L);
	NTT(tmp,n<<1,1),NTT(b,n<<1,1);
	for(int i=0;i<(n<<1);++i) tmp[i]=b[i]*(2+Mod-tmp[i]*b[i]%Mod)%Mod;
	NTT(tmp,n<<1,-1);
	for(int i=0;i<n;++i) b[i]=tmp[i],b[n+i]=0;
}
int main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	read(N),Mul[0]=1;
	for(Bit=1;(1<<Bit)<=N;++Bit);
	Tot=1<<Bit;
	for(int i=1;i<=N;++i) Mul[i]=Mul[i-1]*i%Mod;
	for(int i=0;i<=N;++i) B[i]=qPow(2,(1ll*i*(i-1)>>1)%(Mod-1))*qPow(Mul[i],Mod-2)%Mod;
	for(int i=1;i<=N;++i) C[i]=qPow(2,(1ll*i*(i-1)>>1)%(Mod-1))*qPow(Mul[i-1],Mod-2)%Mod;
	Inverse(B,invB,Tot),Tot<<=1;
	NTT(invB,Tot,1),NTT(C,Tot,1);
	for(int i=0;i<Tot;++i) A[i]=invB[i]*C[i]%Mod;
	NTT(A,Tot,-1);
	write(A[N]*Mul[N-1]%Mod);
	return 0;
}
/*

*/

拯救世界2

题目简介

题目名称：拯救世界

题目来源：洛谷月赛
评测链接：https://www.luogu.com.cn/problem/P2012

形式化题意：对于数，没有限制，必须出现偶数次，必须出现奇数次。

求由组成的长度为的排列个数。多测。

数据范围：

考虑是一个求解排列的问题，所以不能使用，使用。容易发现，这些的的较为好求。

$\begin{align} f_{1\sim4}(x)&=\nonumber \sum_{i=0}^{\infty}\frac{x^i}{i!}&=&e^x \\ f_{5\sim8}(x)&=\nonumber \sum_{i=0}^{\infty}\frac{x^{2i}}{(2i)!}&=&\frac{e^x+e^{-x}}{2} \\ f_{9\sim12}(x)&=\nonumber \sum_{i=0}^{\infty}\frac{x^{2i+1}}{(2i+1)!}&=&\frac{e^x-e^{-x}}{2} \end{align}$

然后相乘，得到：

$\begin{align} ans&=\nonumber \left((e^x)\times\left(\frac{e^x+e^{-x}}{2}\right)\times\left(\frac{e^x-e^{-x}}{2}\right) \right)^4 \\ &=\nonumber \frac{\displaystyle e^{12x}-4e^{8x}+6e^{4x}-4+e^{-4x} }{2^{8}} \end{align}$

我们需要求的是第项，所以消掉所有的得到：

$ans=\frac{1}{2^8}\Big(12^n-4\times8^n+6\times4^n-4+(-1)^n\times4^n \Big)$

但是在内是过不了的，所以我们需要一点点数论知识——欧拉定理，即：

有，这样的话，在的时间内是可以过的。

当然，也可以用光速幂解决。

需要注意的是，对模并没有逆元，所以但是后面所有项中都包含了巨多的质因子，所以完全可以通过化简来把不必要的逆元去掉，但是当的时候后面的质因子是不够用的，所以把的答案手玩特判，然后就解决了。

AC Code

// ----- Eternally question-----
// Problem: P2012 拯救世界2
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P2012
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// Written by: Eternity
// Time: 2023-01-11 19:15:44
// ----- Endless solution-------

#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ putchar(x?'1':'0'); }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
#define int long long
const int Mod=1e9;
const int P=4e8;
ll N;
inline int qPow(int a,int b)
{
	int res=1;
	while(b)
	{
		if(b&1) res=1ll*res*a%Mod;
		a=1ll*a*a%Mod;b>>=1;
	}
	return res;
}
signed main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	read(N);
	while(N)
	{
		if(N<=3) puts("0");
		else if(N==4) puts("24");
		else
		{
			ll a=N-4,b=N-2;
			a%=P,b%=P;
			write((((((81*qPow(12,a)%Mod-qPow(8,b)%Mod)%Mod+Mod)%Mod+6*qPow(4,a)%Mod)%Mod+qPow(-1,a)*qPow(4,a)%Mod)+Mod)%Mod,'\n');
		}
		read(N);
	}
	return 0;
}
/*

*/