二项式反演-斯特林反演-或计数-学习笔记
i207M
2019-01-11 07:16:26
# 对于反演，有一个通用的形式
以二项式反演为例，因为$\sum \limits_{i=0}^n (-1)^{i+k}C_n^iC_i^k=[n=k]$,设矩阵$P:P[i][j]=C_i^j;Q:Q[i][j]=(-1)^{i+j}C_i^j$，则有$PQ=I,P^{-1}=Q$。比如
$\begin{aligned}f_n&=\sum_{i=0}^n{n\choose i}g_i\\g_n&=\sum_{i=0}^n(-1)^{n+i}{n\choose i}f_i\end{aligned}$
我们可以构造出列向量G,F，则有$PG=F,G=QF$，写开就是二项式反演的式子。
再比如斯特林反演：
$\sum \limits_{k=m}^n s_2(n,k)s_1(k,m)(-1)^{n+k}=[n=m]$
我们可以构造出矩阵和逆矩阵，同理就可以得到斯特林反演的式子：
$\begin{aligned}f(n)&=\sum_{i=1}^n \begin{Bmatrix}n\\i\end{Bmatrix}g(i)\\g(n)&=\sum_{i=0}^n(-1)^{n-i}\begin{bmatrix}n\\i\end{bmatrix}f(i)\end{aligned}$
证明斯特林反演的基本式子：
首先：
$x^{\underline n}=(-1)^n (-x)^{\overline n}$
$x^{\overline n}=(-1)^n (-x)^{\underline n}$
证明：
$\begin{aligned}n^m&=\sum_{i=0}^m\begin{Bmatrix}m\\i\end{Bmatrix}n^{\underline i}\\&=\sum_{i=0}^m\begin{Bmatrix}m\\i\end{Bmatrix}(-1)^i(-n)^{\overline i}\\&=\sum_{i=0}^m\begin{Bmatrix}m\\i\end{Bmatrix}(-1)^i\sum_{j=0}^i \begin{bmatrix}i\\j\end{bmatrix}(-n)^j\\&=\sum_{j=0}^m (-n)^j\sum_{i=j}^m\begin{Bmatrix}m\\i\end{Bmatrix}\begin{bmatrix}i\\j\end{bmatrix}(-1)^i\\&=\sum_{j=0}^m n^j\sum_{i=j}^m\begin{Bmatrix}m\\i\end{Bmatrix}\begin{bmatrix}i\\j\end{bmatrix}(-1)^{i+j}\end{aligned}$
显然当且仅当$j=m$时后面那堆式子才为1。
# 二项式反演
### 经典问题：错排
### 经典问题2
求长度为n且仅包含小写英文字母且循环节长度恰为n的字符串的个数。
循环节……就是最短的复制若干遍后拼起来跟原串相等的字符串。
----------------------
接下来是题目
## CF715E
比较难的题，我思考了一下午。
[yyb的Blog](https://www.cnblogs.com/cjyyb/p/10149652.html)
首先转化成数轮换的个数。然后我们要把边建出来，并把中间连续的缩点，变成四种边：已知-已知，已知-0，0-已知，0-0。（所以要注意，dfs记录的是起始点，不是上一点）
然后我们要计算用x-0或0-x边拼成环的方案数：
$g_x=\sum_{i=x}^k{k\choose i}\begin{bmatrix}i\\x\end{bmatrix}(m+k-i)^{\underline{k-i}}$
其中m是0−0边的数量。
理解：先决定环有多少x-0边构成，然后它们组成环的方案数是S1，剩下的每条x-0边可以随意选一条x-0边或0-0边作为后继，所以要乘上下降幂。
注意，这里的g不仅计算了组成环的方案数，对于没有组成环的x-0边，它们的方案数也被算进去了！手玩一下可以得到。
0-x边同理。
然后还有一类边：0-0边，它们组成环的方案数也是S1.
最后把三个数组卷积起来即可。
```cpp
#define N 4005
int cnt[4];
int C[N][N],A[N][N],S[N][N];
void calc(int f[],int n)
{
for(ri i=0; i<=n; ++i)
for(ri j=i; j<=n; ++j)
inc(f[i],mul(mul(C[n][j],S[j][i]),A[n-j+cnt[0]][n-j]));
for(ri i=0; i<=n; ++i)
for(ri j=i+1; j<=n; ++j)
if((i-j)&1) dec(f[i],mul(C[j][i],f[j]));
else inc(f[i],mul(C[j][i],f[j]));
// out(n);
// prt(f,n+1);
}
int n;
int a[N],b[N];
bool vis[N];
int e[N];
int deg[N];
void dfs(int x,int f)
{
vis[x]=1;
// printf("D %d %d\n",x,f);
if(e[x])
{
if(!vis[e[x]]) dfs(e[x],f);
else ++cnt[3];
}
else
{
if(f>n&&x>n) ++cnt[0];
else if(f>n&&x<=n) ++cnt[1];
else if(f<=n&&x>n) ++cnt[2];
}
}
int g[N],f[N],h[N];
int ans[N];
signed main()
{
#ifdef M207
freopen("in.in","r",stdin);
// freopen("out.out","w",stdout);
#endif
in(n);
for(ri i=1; i<=n; ++i) in(a[i]);
for(ri i=1; i<=n; ++i) in(b[i]);
for(ri i=1; i<=n+n; ++i) vis[i]=1;
for(ri i=1; i<=n; ++i)
{
if(!a[i]) a[i]=n+i;
if(!b[i]) b[i]=n+i;
vis[a[i]]=vis[b[i]]=0;
if(a[i]<=n||b[i]<=n) e[a[i]]=b[i],++deg[b[i]];
}
for(ri i=1; i<=n+n; ++i) if(!vis[i]&&!deg[i]) dfs(i,i);
for(ri i=1; i<=n+n; ++i) if(!vis[i]) dfs(i,i);
C[0][0]=A[0][0]=S[0][0]=1;
for(ri i=1; i<=n; ++i)
{
C[i][0]=A[i][0]=1;
for(ri j=1; j<=i; ++j)
{
C[i][j]=add(C[i-1][j-1],C[i-1][j]);
A[i][j]=mul(A[i][j-1],i-j+1);
S[i][j]=add(S[i-1][j-1],mul(S[i-1][j],i-1));
}
}
calc(f,cnt[1]); calc(g,cnt[2]);
for(ri i=0; i<=n; ++i)
for(ri j=0; j<=i; ++j)
inc(h[i],mul(f[j],g[i-j]));
for(ri i=0; i<=n; ++i)
for(ri j=0; j<=i; ++j)
inc(ans[i],mul(h[j],S[cnt[0]][i-j]));
for(ri i=0; i<=n; ++i) ans[i]=mul(ans[i],A[cnt[0]][cnt[0]]);
for(ri i=0; i<n; ++i) out(n-i-cnt[3]>=0?ans[n-i-cnt[3]]:0,' ');
return 0;
}
```