## 莫比乌斯反演与容斥原理

mobius_and_inclusion_exclusion_principle

Download：http://oi.cyo.ng/wp-content/uploads/2018/03/mobius_and_inclusion_exclusion_principle.pdf

## 【BZOJ 4599】[JLOI2016] 成绩比较

### Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 200;
const int MOD = 1000000007;

int n,m,K,r[N],u[N],f[N],g[N],h[N],alpha[N],C[N][N];

inline int read() {
char c=getchar(); int f=1,ret=0;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret * f;
}

inline int Pow(int w, int t) {
int ret = 1;
for (;t;t>>=1,w=(LL)w*w%MOD) {
if (t & 1) {
ret = (LL)ret * w % MOD;
}
}
return ret;
}

inline int LagrangePolynomial(int x, int len, int *ff, int *xx) {
int ret = 0;
for (int i=1;i<=len;i++) {
int tmp = ff[i];
for (int j=1;j<=len;j++) {
if (i == j) continue;
tmp = (LL)tmp * (x - xx[j]) % MOD;
tmp = (LL)tmp * Pow(xx[i] - xx[j], MOD-2) % MOD;
}
ret = (ret + tmp) % MOD;
}
return (ret + MOD) % MOD;
}

int main() {
n = read(); m = read(); K = read();
for (int i=1;i<=m;i++) {
u[i] = read();
}
for (int i=1;i<=m;i++) {
r[i] = read();
}
//预处理组合数
C[0][0] = 1;
for (int i=1;i<=n;i++) {
C[i][0] = 1;
for (int j=1;j<=i;j++) {
C[i][j] = (C[i-1][j-1] + C[i-1][j]) % MOD;
}
}
//拉格朗日插值
for (int w=1;w<=m;w++) {
for (int i=1;i<=n+1;i++) {
f[i] = 0; h[i] = i;
for (int j=1;j<=i;j++) {
f[i] = (f[i] + (LL)Pow(i-j, r[w]-1) * Pow(j, n-r[w])) % MOD;
}
}
g[w] = LagrangePolynomial(u[w], n+1, f, h);
}
//广义容斥原理
int ans = 0;
for (int i=K,t=1;i<=n;i++,t*=-1) {
alpha[i] = C[n-1][i];
for (int j=1;j<=m;j++) {
alpha[i] = (LL)alpha[i] * C[n-1-i][r[j]-1] % MOD * g[j] % MOD;
}
ans = (ans + t * (LL)C[i][K] * alpha[i]) % MOD;
}
printf("%d\n",(ans+MOD)%MOD);
return 0;
}


## 【日常小测】魔术卡

### Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 5009;
const int MOD = 998244353;

int n, m, K, a[N], pw[N], inv[N], f[N][N], C[N][N];

inline int read() {
char c = getchar();
int ret = 0, f = 1;
while (c < '0' || c > '9') {
f = c == '-'? -1: 1;
c = getchar();
}
while ('0' <= c && c <= '9') {
ret = ret * 10 + c - '0';
c = getchar();
}
return ret * f;
}

inline int Pow(int w, int t) {
int ret = 1;
for (; t; t >>= 1, w = (LL)w * w % MOD) {
if (t & 1) {
ret = (LL)ret * w % MOD;
}
}
return ret;
}

int main() {
freopen("magic.in", "r", stdin);
freopen("magic.out", "w", stdout);
m = read(); n = read(); K = read();
for (int i = 1; i <= m; i++) {
a[i] = read();
}
C[0][0] = 1;
for (int i = 1; i <= n; i++) {
C[i][0] = 1;
for (int j = 1; j <= n; j++) {
C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % MOD;
}
}
pw[0] = inv[0] = 1;
for (int i = 1; i <= n; i++) {
pw[i] = (LL)pw[i - 1] * i % MOD;
inv[i] = Pow(pw[i], MOD - 2);
}
f[0][0] = 1;
for (int i = 1, pre_sum = 0; i <= m; i++) {
pre_sum += a[i] - 1;
for (int j = 0; j <= pre_sum; j++) {
for (int k = min(a[i] - 1, j); ~k; k--) {
f[i][j] = (f[i][j] + (LL)f[i - 1][j - k] * C[a[i]][k] % MOD * pw[a[i] - 1] % MOD * inv[a[i] - 1 - k]) % MOD;
}
}
}
int ans = 0;
for (int i = K, ff = 1; i < n; i++, ff *= -1) {
f[m][i] = (LL)f[m][i] * pw[n - i] % MOD;
ans = (ans + (LL)ff * C[i][K] * f[m][i]) % MOD;
}
for (int i = 1; i <= m; i++) {
ans = (LL)ans * inv[a[i]] % MOD;
}
printf("%d\n", (ans + MOD) % MOD);
return 0;
}


## 【BZOJ 3622】已经没有什么好害怕的了

### Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 2009;
const int MOD = 1000000009;

int n,K,a[N],b[N],sum[N],fac[N],alpha[N],f[N][N],C[N][N];

inline int read() {
char c=getchar(); int f=1,ret=0;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret * f;
}

int main() {
n = read(); K = read();
if ((n + K) & 1) {
puts("0");
exit(0);
}
K = n + K >> 1;
for (int i=1;i<=n;i++) {
a[i] = read();
}
sort(a+1, a+1+n);
for (int i=1;i<=n;i++) {
b[i] = read();
}
sort(b+1, b+1+n);
for (int i=1,j=0;i<=n;i++) {
for (;j < n && b[j+1] < a[i];++j);
sum[i] = j;
}
C[0][0] = 1;
for (int i=1;i<=n;i++) {
C[i][0] = 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<=n;i++) {
fac[i] = fac[i-1] * (LL)i % MOD;
}
f[0][0] = 1;
for (int i=1;i<=n;i++) {
for (int j=0;j<=i;j++) {
f[i][j] = (f[i-1][j] + (j?f[i-1][j-1] * max(0ll, (sum[i] - j + 1ll)):0ll)) % MOD;
}
}
for (int i=0;i<=n;i++) {
alpha[i] = (LL)f[n][i] * fac[n - i] % MOD;
}
int ans = 0;
for (int i=K,t=1;i<=n;i++,t*=-1) {
ans = (ans + (LL)alpha[i] * C[i][K] * t) % MOD;
}
printf("%d\n",(ans+MOD)%MOD);
return 0;
}


## 【HDU 4626】Jinkeloid

### Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 3000000;
const int M = 100009;
const int UNIVERSE = (1 << 20) - 1;
const int SGZ = 20;

char pat[M];
int n,m,sta;
LL a[N],f[N],zero;

inline int read() {
char c=getchar(); int f=1,ret=0;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret * f;
}

inline void FWT(LL *arr, int len, int ty) {
for (int d=1;d<len;d<<=1) {
for (int i=0;i<=len;i+=d*2) {
for (int j=0;j<d;j++) {
LL t1 = arr[i+j], t2 = arr[i+j+d];
arr[i+j] = t1 + t2;
arr[i+j+d] = t1 - t2;
if (ty == -1) {
arr[i+j] /= 2;
arr[i+j+d] /= 2;
}
}
}
}
}

int main() {
for (int T=read();T;T--) {
memset(a, 0, sizeof(a));
scanf("%s",pat);
n = strlen(pat);
a[0]++; sta = zero = 0;
for (int i=0;i<n;i++) {
sta ^= 1 << pat[i] - 'a';
zero += a[sta]++;
}
FWT(a, UNIVERSE, 1);
for (int i=0;i<=UNIVERSE;i++) {
a[i] = a[i] * a[i];
}
FWT(a, UNIVERSE, -1);
a[0] = zero;
for (int i=1;i<=UNIVERSE;i++) {
a[i] /= 2;
}
for (int i=0;i<=UNIVERSE;i++) {
if ((i ^ UNIVERSE) < i) {
swap(a[i], a[i^UNIVERSE]);
}
}
for (int j=0;j<SGZ;j++) {
for (int i=0;i<=UNIVERSE;i++) {
if (i & (1<<j)) {
a[i^(1<<j)] += a[i];
}
}
}
m = read();
for (int tt=1;tt<=m;tt++) {
int k = read(), sta = 0;
for (int i=1;i<=k;i++) {
scanf("%s",pat);
sta |= 1 << pat[0] - 'a';
}
printf("%lld\n",a[sta]);
}
}
return 0;
}


## 【BZOJ 4714】旋转排列

### 题目大意

1. 对于$\forall i \in [1,n]$ 都有$a_i \ne i$
2. 存在一个长度为$k$的序列$B$，使得$P_{B_i}=B_{i+1}$且$P_{B_k} = B_1$

### Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 500009;
const int MOD = 1000000007;

int n,ans,fac[N],rev[N],q[N];

inline int C(int a, int b) {
if (a > b || a < 0) return 0;
else return ((LL)fac[b] * rev[a] % MOD) * rev[b-a] % MOD;
}

inline int Pow(int w, int t) {
int ret = 1;
for (;t;t>>=1,w=(LL)w*w%MOD)
if (t&1) ret=(LL)ret*w%MOD;
return ret;
}

int main() {
fac[0] = fac[1] = q[2] = q[0] = 1;
for (int i=2;i<N;i++) fac[i] = (LL)fac[i-1] * i % MOD;
rev[N-1] = Pow(fac[N-1], MOD - 2);
for (int i=N-2;~i;i--) rev[i] = rev[i+1] * (i + 1ll) % MOD;
for (int i=3;i<N;i++) q[i] = (i - 1ll) * (q[i-1] + q[i-2]) % MOD;
cin>>n;
for (int k=2,g;g=1,k<=n;k++) {
for (int t=1;t*k<=n;t++) {
g = ((LL)g * C(k-1, t*k-1) % MOD) * fac[k-1] % MOD;
ans = (ans + ((t&1)?1:-1) * ((LL)g * C(k*t, n) % MOD) * q[n - k*t]) % MOD;
}
}
printf("%d\n",(ans+MOD)%MOD);
return 0;
}


## 【BZOJ 4710】[JSOI2011] 分特产

### Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 2009;
const int MOD = 1000000007;

int n,m,ans,a[N],C[N][N];

inline int read() {
char c=getchar(); int f=1,ret=0;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret * f;
}

inline int cal(int x) {
int ret = C[x][n];
for (int i=1;i<=m;i++) {
ret = (LL)ret * C[n-x-1][a[i]+n-x-1] % MOD;
}
return ret;
}

int main() {
n = read(); m = read();
C[0][0] = 1;
for (int i=1;i<N;i++) {
C[0][i] = 1;
for (int j=1;j<N;j++) {
C[j][i] = (C[j-1][i-1] + C[j][i-1]) % MOD;
}
}
for (int i=1;i<=m;i++) a[i] = read();
for (int i=0;i<n;i++) {
if (i&1) ans = (ans - cal(i)) % MOD;
else ans = (ans + cal(i)) % MOD;
}
printf("%d\n",(ans+MOD)%MOD);
return 0;
}


## 【日常小测】迷宫

### Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int MOD = 1004535809;

int n,tot,vout,sta[100][7],cur[7];
struct Matrix{
int f[100][100];
inline Matrix() {memset(f,0,sizeof(f));}
inline Matrix(int x) {memset(f,0,sizeof(f));for(int i=1;i<=tot;i++)f[i][i]=x;}
inline Matrix(const Matrix &M) {for(int i=1;i<=tot;i++)for(int j=1;j<=tot;j++)f[i][j]=M.f[i][j];}
inline Matrix operator * (const Matrix &M) {
Matrix ret;
for (int i=1;i<=tot;i++) for (int j=1;j<=tot;j++) for (int k=1;k<=tot;k++)
ret.f[i][k] = (ret.f[i][k] + (LL)f[j][k] * M.f[i][j]) % MOD;
return ret;
}
inline Matrix operator ^ (int t) {
Matrix ret(1),tmp(*this);
for (;t;t>>=1,tmp=tmp*tmp)
if (t&1) ret=ret*tmp;
return ret;
}
inline void out() {
for (int i=1;i<=tot;i++) {
for (int j=1;j<=tot;j++) {
printf("%d ",f[j][i]);
} cout<<endl;
}
}
}ans,trans;

inline int read() {
char c=getchar(); int f=1,ret=0;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret * f;
}

void DFS(int w, int v) {
if (w == 7) {
memcpy(sta[++tot],cur,sizeof(cur));
} else {
for (int i=1;i<=3;i++) if (i != v)
cur[w] = i, DFS(w+1, i);
}
}

inline int Pow(int w, LL t) {
int ret = 1;
for (;t;t>>=1,w=(LL)w*w%MOD)
if (t&1) ret=(LL)ret*w%MOD;
return ret;
}

inline bool check(int a, int b) {
for (int i=1;i<=6;i++) {
if (i > 1 && sta[a][i-1] == sta[b][i]) return 0;
if (i < tot && sta[a][i+1] == sta[b][i]) return 0;
} return 1;
}

int main() {
freopen("board.in","r",stdin);
freopen("board.out","w",stdout);
n = read(); DFS(1, -1);
for (int i=1;i<=tot;i++) for (int j=1;j<=tot;j++)
if (check(i, j)) trans.f[j][i] = 1 << 6;
for (int i=1;i<=tot;i++) if (sta[i][1] == 1) ans.f[i][1] = 1 << 5;
trans = trans ^ (n - 1); ans = ans * trans;
for (int i=1;i<=tot;i++) vout = (vout + ans.f[i][1]) % MOD;
vout = (vout - 2ll * Pow(2, n * 6ll - 1)) % MOD;
vout = (LL)vout * Pow(4, MOD-2) % MOD;
vout = (vout + Pow(2, n * 6ll - 1)) % MOD;
printf("%d\n",(vout+MOD)%MOD);
return 0;
}


## 【BZOJ 4635】数论小测验

### Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int MOD = 1000000007;
const int N = 10000009;
const int M = 32;

int n,m,SZ,s1[N],hc[N],to[1001];
int tot,pri[N>>3],mu[N]; bool vis[N];

inline int read() {
char c=getchar(); int f=1,ret=0;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret * f;
}

inline int Pow(int w, int t) {
int ret = 1;
for (;t;t>>=1,w=(LL)w*w%MOD)
if (t&1) ret=(LL)ret*w%MOD;
return ret;
}

inline void GetMu() {
mu[1] = 1;
for (int i=2;i<N;i++) {
if (!vis[i]) mu[i] = -1, pri[++tot] = i;
for (int j=1;j<=tot&&pri[j]*i<N;j++) {
vis[i*pri[j]] = 1;
if (i%pri[j]) mu[i*pri[j]] = -mu[i];
else {mu[i*pri[j]] = 0; break;}
}
mu[i] = mu[i-1] + mu[i];
}
}

inline int cal(int mx) {
int ret = 0;
for (int l=1,r,tmp;l<=mx;l=r+1) {
r = mx / (mx / l);
tmp = (LL)(mu[r] - mu[l-1]) * hc[mx/l] % MOD;
ret = (ret + tmp) % MOD;
}
return (ret + MOD) % MOD;
}

struct Matrix{
int a[M][M];
inline Matrix() {memset(a,0,sizeof(a));}
inline Matrix(const Matrix *A) {
for (int i=0;i<M;i++) for (int j=0;j<M;j++) a[i][j] = A->a[i][j];
}
inline Matrix(int x) {
memset(a,0,sizeof(a));
for (int i=0;i<SZ;i++) a[i][i] = x;
}
inline void operator *= (const Matrix &A) {
Matrix ret;
for (int i=0,*t1,*t3;i<SZ;i++) {
t1 = ret.a[i]; const int *t2 = A.a[i];
for (int j=0;j<SZ;j++) {
t3 = a[j];
for (int k=0;k<SZ;k+=4) {
t1[k] = (t1[k] + (LL)t3[k] * t2[j]) % MOD;
t1[k+1] = (t1[k+1] + (LL)t3[k+1] * t2[j]) % MOD;
t1[k+2] = (t1[k+2] + (LL)t3[k+2] * t2[j]) % MOD;
t1[k+3] = (t1[k+3] + (LL)t3[k+3] * t2[j]) % MOD;
}
}
}
for (int i=0;i<SZ;i++) for (int j=0;j<SZ;j++) a[i][j] = ret.a[i][j];
}
inline Matrix operator ^ (int t) {
Matrix ret(1),w(this);
for (;t;t>>=1,w*=w) if (t&1) ret*=w;
return ret;
}
}ans,trans;

inline int solve(int w) {
tot = 0;
for (int i=2,tmp=w;i<=tmp;i++) {
if (tmp % i == 0) {
pri[++tot] = i; tmp /= i;
while (tmp % i == 0) pri[tot] *= i, tmp /= i;
}
}
ans = Matrix(); trans = Matrix();
ans.a[0][0] = 1; SZ = 1 << tot;
memset(to,0,sizeof(to));
for (int i=1,t=1,ww;ww=pri[i],i<=tot;i++,t<<=1)
for (int j=ww;j<=m;j+=ww) to[j] |= t;
for (int i=1,tt;tt=to[i],i<=m;i++) {
for (int p=0,ww;ww=p,p<SZ;p++)
++trans.a[p|tt][p];
}
trans = trans ^ n;
ans *= trans;
return ans.a[SZ-1][0];
}

int main() {
int T = read(), type = read();
if (type == 1) {
GetMu();
for (int t=1,vout;vout=0,t<=T;t++) {
n = read(); m = read();
int L = read(), R = read();
for (int l=1,r;l<=m;l=r+1) {
r = m / (m / l);
hc[m / l] = Pow(m / l, n);
}
for (int l=L,r,tmp;l<=R;l=r+1) {
r = m / (m / l); tmp = cal(m / l);
vout = (vout + (min(r,R)-max(L,l)+1ll) * tmp) % MOD;
}
printf("%d\n",vout);
}
} else if (type == 2) {
for (int t=1,vout,l,r;vout=0,t<=T;t++) {
n = read(); m = read(); l = read(), r = read();
for (int w=l;w<=r;w++) vout = (vout + solve(w)) % MOD;
printf("%d\n",vout);
}
}
return 0;
}


## 【BZOJ 4762】最小集合

### 解题报告

1. $f[i][j][k] \to f[i+1][j|a_i][k-(k \& a_i)]$表示不强制非法
2. $-f[i][j][k] \to f[i+1][j|a_i][(k-(k \& a_i))|(a_i-(a_i \& j))]$表示强制非法
ps: 根据容斥原理，第二种转移会配上$-1$的系数

### Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 1001;
const int M = (1 << 10) - 1;
const int MOD = 1000000007;

int n,vout,a[N],f[1<<10][1<<10];

inline int read() {
char c=getchar(); int ret=0,f=1;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret*f;
}

int main() {
n = read();
for (int i=1;i<=n;i++) a[i] = read() ^ M;
f[0][0] = 1;
for (int t=1;t<=n;t++) {
for (int i=M,ti,tj,uni;~i;--i) {
if ((ti = (a[t] | i)) > i) {
uni = ti - i;
for (int j=i;;(--j)&=i) {
tj = (j - (j & a[t]));
f[ti][tj] = (f[ti][tj] + f[i][j]) % MOD;
f[ti][tj|uni] = (f[ti][tj|uni] - f[i][j]) % MOD;
if (!j) break;
}
}
}
}
printf("%d\n",(f[M][0]+MOD)%MOD);
return 0;
}


## 【TopCoder】[TCO2013 2A] The Powers

### Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 32000;

int vis[N],pri[N],tot;
LL ans[40];
vector<int> que;

class ThePowers{
public:
long long find(LL A, LL B) {
prework(N-1, B); LL ret = B - 1;
for (LL r=2,t,vi;r*r<=A;r++) {
if (judge(r)) {
for (t=0,vi=r;vi<=A;t++,vi*=r);
ret += t * B - ans[t];
}
}
return (LL)A * B - ret;
}
private:
LL DFS(LL t, LL B, LL cnt, LL lcm) {
if (!t) {
if (cnt & 1) return (LL)B / lcm;
else if (cnt) return -(LL)B / lcm;
else return 0;
} else {
return
DFS(t-1, B, cnt, lcm) +
DFS(t-1, B, cnt+1, lcm / Gcd(lcm, que[t-1]) * que[t-1]);
}
}
inline void prework(LL n, LL B) {
for (int i=2;i<=n;i++) {
if (!vis[i]) vis[i] = i, pri[++tot] = i;
for (int j=1;j<=tot&&pri[j]*i<=n;j++) {
vis[i*pri[j]] = pri[j];
if (i % pri[j] == 0) break;
}
}
for (int i=1;i<30;i++) {
for (int j=1;j<=i;j++) {
que.clear();
for (int k=j,tag=0;k<=i;k++,tag=0) {
for (int l=que.size()-1;l>=0;l--)
if (k % que[l] == 0)
{tag = 1; break;}
if (!tag) que.push_back(k);
}
ans[i] += DFS(que.size(), j * B, 0, 1);
ans[i] -= DFS(que.size(), j * B - B, 0, 1);
}
cout<<ans[i]<<endl;;
}
}
inline LL Gcd(LL a, LL b) {
return b? Gcd(b, a%b): a;
}
inline bool judge(int w) {
int GCD = 0;
for (int t=0,p=vis[w];w>1;t=0,p=vis[w]) {
while (w % p == 0) t++, w /= p;
if (!GCD) GCD = t;
else GCD = Gcd(GCD, t);
}
return GCD == 1;
}
};


## 【SPOJ DIVCNT2】Counting Divisors (square)

### 解题报告

spoj_divcnt2_solution

## 【BZOJ 2986】Non-Squarefree Numbers

### 解题报告

prefix_sum_of_mobius_function

## 【TopCoder】[TCO2013 2B] Lit Panels

### 解题报告

topcoder_LitPanels

## 【BZOJ 3861】Tree

Claris还给出了一个方法：

### Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 1009;
const int MOD = 1000000007;

int n,cnt[N],f[2][N],POW[N];

inline int read() {
char c=getchar(); int f=1,ret=0;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret * f;
}

inline int Pow(int w, int t) {
int ret = 1;
while (t) {
if (t & 1) ret = (LL)ret * w % MOD;
w = (LL)w * w % MOD; t >>= 1;
}
return ret;
}

int main() {
POW[0] = 1;
for (int i=1;i<N;i++) POW[i] = (LL)POW[i-1] * i % MOD;
for (int tag=0,tot=1,spj=0;n=read();tag=spj=0,++tot) {
for (int i=1;i<=n;i++) {
cnt[i] = read();
if (cnt[i] == n) tag = 1;
if (!cnt[i]) spj++;
for (int j=1;j<=cnt[i];j++)
read();
}
if (tag) {printf("Case #%d: 0\n",tot); continue;}
int p = 1, w = 0, vout = 0;
memset(f[p],0,sizeof(f[p]));
f[p][0] = 1;
for (int i=1;i<=n;++i,p^=1,w^=1) {
memset(f[w],0,sizeof(f[w]));
f[w][0] = f[p][0];
for (int j=1;j<=n;j++) {
(f[w][j] += f[p][j]) %= MOD;
(f[w][j] += (LL)f[p][j-1] * cnt[i] % MOD) %= MOD;
}
}
for (int i=0,t=1;i<=n;i++,t*=-1) {
f[p][i] = (LL)f[p][i] * POW[n-i] % MOD;
(vout += f[p][i] * t) %= MOD;
}
vout = (LL)vout * Pow(POW[spj], MOD-2) % MOD;
printf("Case #%d: %d\n",tot,(vout+MOD)%MOD);
}
return 0;
}


## 【BZOJ 4455】[ZJOI2016] 小星星

### 解题报告

$f(i,j,S)$ 表示树上第$i$个点，对应图中第$j$个点，子树中的对应状态状压后为$S$的方案数

1. 这样会T
2. 我不会更优的算法了