被Dyd教育了（QWQ）。
讲课的第一题，理论应该不是很难，但涉及$SG$函数，本人不会，被现场教育了。
题目传送门
题目描述
$n$个点，$m$条边，所有的边$(u, v)$满足：$u < v$，求$SG(1) \ != SG(2)$的方案数。
$$
\begin{aligned}
n &\le 15 \\
m &\le n*(n-1)
\end{aligned}
$$
solution
题目要求过于苛刻，考虑转化。可以发现总方案数为：$2^m$，所以我们只要求出$SG(1) = SG(2)$的方案数即可，于是我们考虑状压$dp$，令$dp[S]$为点集为$S$的方案数,考虑转移方程怎么写。
根据由小推大的原则，考虑$S$的子集$T$和$U=S-T$，令$ \forall SG_{i|U}=0$且$\forall SG_{i|T} \ !=0$，那么我们可以发现：
- 1和2必须在同一子集，否则根据定义$SG(1)$不可能等于$SG(2)$。
- 根据$SG$函数的定义，$T$中必定有一条边连向$U$，且$U$中有多少条边连向$T$却无所谓。
那么可以得到$U$，$T$对$dp[S]$的影响就是：
$$
\begin{aligned}
dp[S] &+= 2^{count(g[i] \ \wedge \ U)}, i \in U \\
dp[S] &+= 2^{count(g[i] \ \wedge \ T) - 1}, i \in T
\end{aligned}
$$
$g[i]$指从$i$可以一次到达的边的集合。
其实也非常好理解，对于任意一条从$U$出发到$T$的边（总数为$tem1$）在不影响正确性的情况下可以有任意两种选择，而从$U$出发到$T$的边（总数为$tem2$）只有$tem2 - 1$条边可以有任意两种选择（至少有一条边连向$U$）。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
| #include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 16, mod = 1e9 + 7;
int n, m;
LL g[N], dp[1 << N], pow2[1 << N];
int main()
{
scanf("%d%d", &n, &m);
dp[0] = pow2[0] = 1;
for(int i = 1;i <= m;i ++) pow2[i] = (pow2[i - 1] * 2) % mod;
for(int i = 1;i <= m;i ++)
{
int o, u;
scanf("%d%d", &o, &u);
o --, u --;
g[o] |= (1 << u);
}
for(int S = 1; S < (1 << n); S ++)
{
if((S & 1) != (S >> 1 & 1)) continue;
for(int u = S; u;u = u - 1 & S)
{
if((u & 1) != (u >> 1 & 1)) continue;
LL ans = 1;
for(int i = 0;i < n;i ++)
if(S >> i & 1)
{
if(u >> i & 1) ans = ans * pow2[__builtin_popcount(g[i] & (S ^ u))] % mod;
else ans = ans * (pow2[__builtin_popcount(g[i] & u)] - 1) % mod;
}
dp[S] = (dp[S] + dp[S ^ u] * ans % mod) % mod;
}
}
printf("%lld",(pow2[m] - dp[(1 << n) - 1] + mod) % mod);
return 0;
}
|