CF838C（博弈+FWT子集卷积+多项式ln、exp）

传送门：

http://codeforces.com/problemset/problem/838/C

题解：

如果一个字符串的排列数是偶数，则先手必胜，因为如果下一层有后手必赢态，直接转移过去，不然，就一直耗着，因为是偶数，所以会让后手进入下一层，则后手必输。

排列数是偶数，打表发现\(|s|\)是奇数时，先手必赢，否则后手必赢，接下来尝试归纳这个结论。

|s|<=2时显然成立。

对于\(|S|\)奇数,排列个数是奇数时，设a[i]表示第i个字符出现次数，排列个数=\(\binom{|S|}{a[1],a[2],…,a[k]}\)，我们需要使一个a[i]减一，然后新的排列个数还是奇数，因为\(|S|\)是奇数，所以一定可以找到一个是奇数的\(a[i]\)，然后满足。

对于\(|S|\)偶数，排列个数是奇数时，不管新的的排列个数是奇数还是偶数，因为下一个长度是奇数，新状态都会先手比胜。

因此得证。

那么问题转换为选\(a[1],a[2],…,a[k]，使{\forall i,j(i≠j)}满足a[i]~and~a[j]=0\)。

一个比较容易的思路，\(>0\)的\(a[i]\)肯定不超过\(log ~ n\)个，不难想到子集卷积，最后乘一个组合数。

子集卷积解决下面这个问题：

\(c[i|j]+=a[i]*b[j](i~and~j=0)\)

套路的解决方法是再记录一维表示1的个数，只要最后搞出的结果的1的个数相符就表示没有出现\(i~and~j≠0\)。

那么复杂度是\(O(n~log^3~n)\)，卡卡常就能过。

事实上有\(O(n~log^2n)\)的做法。

考虑不枚举\(>0\)的个数，直接暴力卷积：

记\(f[i][j]\)表示1的个数为i时状态为j的的系数和。

这个东西可以快速幂卷对吧，不过还是\(log^3\)的。

把状态反过来\(f[j][i]\)表示状态为j的，1的个数为i的系数和，注意这个j已经FWT过了。

那么后面就相当于普通的多项式快速幂，求个ln*k再exp即可。

注意到项数很少，可以暴力ln和exp。

暴力exp可以用组合意义搞：

有\(F\)，设\(f(x)\)为它的EGF，即\(f(x)[x^n]=F[n]/n!\)

那么有\(g(x)=e^{f(x)}\)意义可以为有标号连通图->有标号一般图，\(g(x)\)是\(G=e^{f(x)}\)的EGF，所以有dp：

\(G[n]*n!=\sum_{i=1}^{n}\binom{n-1}{i-1}*F[i]*i!*G[n-i]*(n-i)!\)

\(G[n]=\sum_{i=1}^{n}F[i]*G[n-i]*{i\over n}\)

ln的过程即由G->F，直接反过来可得：

\(F[n]=G[n]-\sum_{i=1}^{n-1}F[i]*G[n-i]*{i \over n}\)

Code：

#include<bits/stdc++.h>

#define fo(i, x, y) for(int i = x, B = y; i <= B; i ++)

#define ff(i, x, y) for(int i = x, B = y; i <  B; i ++)

#define fd(i, x, y) for(int i = x, B = y; i >= B; i --)

#define ll long long

#define pp printf

#define hh pp("\n")

using namespace std;

const int N = 3e5 + 5;

int n, k, mo;

ll fac[N], nf[N];

ll ksm(ll x, ll y) {

	ll s = 1;

	for(; y; y /= 2, x = x * x % mo)

		if(y & 1) s = s * x % mo;

	return s;

}

ll C(int n, int m) {

	ll s = 1;

	fo(i, n - m + 1, n) s = s * i % mo;

	s = s * nf[m] % mo;

	return s;

}

ll ans;

const int nm = (1 << 17) + 5;

#define low(x) (x & -(x))

int g[nm * 4];

ll a[18][nm], f[2][18][nm]; int o;

void fwt(ll *a, int n) {

	for(int i = 1; i < n; i *= 2) for(int j = 0; j < n; j += 2 * i)

		ff(k, 0, i) a[i + j + k] += a[j + k];

	ff(i, 0, n) a[i] %= mo;

}

int tp, aw[21];

int main() {

	freopen("megalovania.in", "r", stdin);

	freopen("megalovania.out", "w", stdout);

	scanf("%d %d %d", &n, &k, &mo);

	if(n & 1) {

		pp("0\n"); return 0;

	}

	fac[0] = 1; fo(i, 1, n) fac[i] = fac[i - 1] * i % mo;

	nf[n] = ksm(fac[n], mo - 2); fd(i, n, 1) nf[i - 1] = nf[i] * i % mo;

	ff(i, 1, 1 << 19) g[i] = g[i - low(i)] + 1;

	tp = g[n]; int cw = 0;

	fo(j, 0, 18) if(n >> j & 1) {

		aw[j] = 1 << (cw ++);

	}

	fo(i, 1, n) if((i & n) == i) {

		int ni = 0;

		fo(j, 0, 18) if(i >> j & 1) ni += aw[j];

		a[g[i]][ni] = nf[i];

	}

	fo(i, 1, tp) fwt(a[i], 1 << tp);

	fo(i, 1, tp) ff(j, 0, 1 << tp) f[o][i][j] = a[i][j];

	int mx = (1 << tp) - 1;

	fo(i, 1, tp) {

		memset(f[!o], 0, sizeof f[!o]);

		if(i != tp) {

			fo(u, i, tp) fo(v, 1, tp - u) ff(j, 0, 1 << tp) if(f[o][u][j] && a[v][j])

				f[!o][u + v][j] += f[o][u][j] * a[v][j],

				f[!o][u + v][j] > 9e18 ? f[!o][u + v][j] %= mo : 0;

		}

		ll F = 0;

		ff(j, 0, 1 << tp) F += f[o][tp][j] * (g[j ^ mx] % 2 ? -1 : 1);

		F %= mo;

		ans += F * C(k, i) % mo * fac[n] % mo;

		o = !o;

		fo(u, 0, tp) ff(j, 0, 1 << tp) f[o][u][j] >= mo ? f[o][u][j] %= mo : 0;

	}

	ans = (ans % mo + mo) % mo;

	pp("%lld\n", ans);

}

巴特西

CF838C（博弈+FWT子集卷积+多项式ln、exp）

传送门：

题解：

Code：

最新文章

热门文章