题解 P3349 【[ZJOI2016]小星星】
辰星凌
·
·
题解
【题解】小星星 [ZJOI2016] [P3349]
\mathcal{My}\ \mathcal{Blog}
传送门：小星星 \text{[ZJOI2016] [P3349]}
【题目描述】
给出 n 个点的一张无向图 (V,E) 和一颗树，现需要给每个点 i 安排一个映射 a_i，满足对于树上任意边 (x,y)，均有边 (a_x,a_y)\in E。要求 a 为一个排列（即不存在两个点的映射相同），求方案数。
【分析】
组合意义天地灭，代数推导保平安。 —— tiger0133
大家似乎都是直接硬找的容斥系数，这里提供一个不需要费脑子的子集反演做法（最终柿子是一样的）。
先考虑最 \text{naive} 的暴力状压：设 dp(x,j,S) 表示点 x 映射为 j、x 子树内所有点已经使用了 S 作为映射 的方案数（S 为一个二进制数）。
转移需要枚举 $S$ 的子集，复杂度 $O(n^33^n)$，用多项式科技优化子集卷积可以做到 $O(n^42^n)$，显然还是过不了。
复杂度瓶颈在于枚举子集，必须把这个东西去掉。
优化子集 $dp$ 显然要上容斥，不过这里我们采用另一个思路：子集反演。
搞反演的第一步是设计两个状态，且需满足其中一个可以方便求得、另一个可以方便得出答案、两者之间存在关系式。
设计状态用类似二项式反演的套路去思考，如果实在想不出来就一个一个枚举限制条件，逐个检验是否可行。
本题的关键限制在于：任意两点的映射不能相同。当存在这一限制时无论怎么设都不好搞，所以设状态时需要把这个限制去掉。
$f(S)$： $n$ 个点的映射**恰好**使用了 $S$ 中的所有点（无需满足 $a$ 为排列）。
$g(S)$： $n$ 个点的映射**至多**只能够使用 $S$ 中的点（无需满足 $a$ 为排列）。
易知：
$$g(S)=\sum_{T\subseteq S}f(T)$$
由子集反演可得：
$$f(S)=\sum_{T\subseteq S}(-1)^{|S|-|T|}g(T)$$
> **注意**：
在做二项式反演时，我们所说的“至多”和“至少”都是假的，真正含义为：钦定某一部分满足某条件，其余部分随意。因此 $f,g$ 的关系式中会存在一个二项式系数（一个 $f(i)$ 会被 $g(x)$ 统计多次，当状态只有一维时，这个次数为 $C_{i}^{x}$ 或者 $C_{x}^{i}$）。
但这里子集反演定义的“至多”是真货，每个 $f(T)$ 只会被 $g(S)$ 统计一次，因此 $g(S)$ 直接就等于 $\sum_{T\subseteq S}f(T)$，不会带有奇怪的系数。
回到这道题，最终答案为 $f(V)$，其中 $V$ 为全集（即 $2^{n}-1$）。
> Q：为什喵？前面做定义时不是说的**不一定满足** $a$ 为排列吗？
A: 由于全集 $V$ 中的 $n$ 个点全都被作为映射使用了，而一个点只能映射一个，所以 $f(V)$ 统计的方案中每个点的映射必定两两不同。
那么最后的问题就是 在不涉及 $f$ 的情况下快速计算 $g(S)$ 了。
修改一下前面的暴力状压：
用 $dp(x,j,S)$ 表示点 $x$ 映射为 $j$、$x$ 子树内所有点至多只能使用 $S$ 中的点作为映射值 的方案数（无需满足映射两两不同）。
转移为：
$$dp(x,j,S)=\prod\limits_{to\in\{son(x)\}}\left(\sum\limits_{k\subseteq S,(j,k)\in E}dp(to,k,S)\right)$$
可得 $g(S)=\sum_{j\subseteq S}dp(rt,j,S)$，其中 $rt$ 为树的根。
时间复杂度为：$O(n^32^n)$，要凭信仰卡常....
## **【Code】**
```cpp
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#define LL long long
#define Re register int
using namespace std;
const int N=18,M=131072+3;
int n,m,x,y,o,V,v[N],cnt[M],head[N],A[N][N];LL ans,g[M],dp[N][N];
struct QAQ{int to,next;}a[N<<1];
inline void add(Re x,Re y){a[++o].to=y,a[o].next=head[x],head[x]=o;}
inline void in(Re &x){
int f=0;x=0;char ch=getchar();
while(ch<'0'||ch>'9')f|=ch=='-',ch=getchar();
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
x=f?-x:x;
}
inline void dfs(Re x,Re fa,Re S){
for(Re i=1;i<=v[0];++i)dp[x][i]=1;
for(Re i=head[x],to;i;i=a[i].next)
if((to=a[i].to)!=fa){
dfs(to,x,S);
for(Re j=1;j<=v[0];++j){
LL tmp=0;
for(Re k=1;k<=v[0];++k)if(A[v[j]][v[k]])tmp+=dp[to][k];
dp[x][j]*=tmp;
}
}
}
int main(){
// freopen("123.txt","r",stdin);
in(n),in(m),V=(1<<n)-1;
if(n==1){puts("1");return 0;}
while(m--)in(x),in(y),A[x][y]=A[y][x]=1;
m=n-1;
while(m--)in(x),in(y),add(x,y),add(y,x);
for(Re s=0;s<=V;++s){
cnt[s]=cnt[s>>1]+(s&1),v[0]=0;
for(Re i=1;i<=n;++i)if(s&(1<<i-1))v[++v[0]]=i;
dfs(1,0,s);LL g=0;
for(Re i=1;i<=v[0];++i)g+=dp[1][i];
ans+=(n-cnt[s]&1)?-g:g;
}
printf("%lld\n",ans);
}
```
完结洒花花~
...等等，还没完！
这题神奇地没有让取模！
虽然答案的最大值 $n!$ 没有爆 $\text{long long}$，但 $\max(g(V))=n^n$ 爆了啊。
emm....手写高精多半会 $\text{TLE}$ ....就酱吧awa
（据说用 $\text{long long}$ 和 $\text{int128}$ 算出来的结果是一样的）