雅礼集训 小c的锦标赛

玄学竞赛图和FFT

Posted by yjjr's blog on January 18, 2018

标签:FFT

题目

这里写图片描述

3<=k<=10^5

分析

考试的时候打了30分k=3的情况走人


当K==N时,问题就是有多少个N个点的强连通竞赛图数量,设这个答案为f(n)

利用补集思想,转化为有多少个N个点的竞赛图不强连通,这只需要枚举拓扑序最靠前的强连通分量大小即可

正解

问题转化为求大小为N,至少包含一个大小为K的强连通分量的竞赛图数量

这句话好绕啊,我语文果然不好qwq

可以采用补集思想,计算有多少个只包含大小小于K的强连通分量的竞赛图数量

可以通过多项式求逆做到O(n log n)

code

代码风格奇葩的std

#include <bits/stdc++.h>

#define For(i, j, k) for(int i = j; i <= k; i++)
#define Forr(i, j, k) for(int i = j; i >= k; i--)

using namespace std;

const int Mod = 998244353, r = 3;
const int N = 300010;

typedef long long LL;

LL Pow(LL x, LL e){
	LL ret = 1;
	while(e){
		if(e & 1) ret = ret * x % Mod;
		x = x * x % Mod;
		e >>= 1;
	}
	return ret;
}

int rev[N];
LL w[N];

void DFT(LL *A, int n, bool inv){
	For(i, 0, n - 1) if(i < rev[i]) swap(A[i], A[rev[i]]);
	for(int m = 1; m < n; m <<= 1){
		LL coe = Pow(r, (Mod - 1) / (m << 1));
		if(inv) coe = Pow(coe, Mod - 2);

		w[0] = 1;
		for(int i = 1; i < m; ++i) w[i] = w[i - 1] * coe % Mod;
		
		for(int i = 0; i < n; i += (m << 1))
			for(int j = 0; j < m; ++j){
				LL x = A[i + j], y = w[j] * A[i + j + m] % Mod;
				(A[i + j] += y) %= Mod;
				A[i + j + m] = (Mod + x - y) % Mod;
			}	
	}
}

LL tmp[N];

void Inverse(LL *A, LL *B, int n){
	if(n == 1){
		B[0] = Pow(A[0], Mod - 2);
		return;
	}

	Inverse(A, B, n >> 1);

	n <<= 1;
	For(i, 0, n - 1) rev[i] = (rev[i >> 1] >> 1) | ((i & 1) * (n >> 1));

	For(i, 0, n / 2 - 1) tmp[i] = A[i], tmp[i + n / 2] = 0;
	DFT(tmp, n, 0), DFT(B, n, 0);
	For(i, 0, n - 1) B[i] = (2 * B[i] - tmp[i] * B[i] % Mod * B[i] % Mod + Mod) % Mod;
	DFT(B, n, 1);

	LL inv = Pow(n, Mod - 2);
	For(i, 0, n - 1) B[i] = i < n / 2 ? B[i] * inv % Mod : 0;
}

LL fac[N], rfac[N];
LL F[N], G[N], A[N];
int k, n;

int main(){
	freopen("tournament.in", "r", stdin);
	freopen("tournament.out", "w", stdout);

	int m;
	scanf("%d%d", &m, &k);
	n = 1;
	while(n <= m) n <<= 1;

	fac[0] = 1;
	For(i, 1, n) fac[i] = fac[i - 1] * i % Mod;
	rfac[n] = Pow(fac[n], Mod - 2);
	Forr(i, n, 1) rfac[i - 1] = rfac[i] * i % Mod;

	For(i, 1, n - 1) G[i] = Pow(2, 1ll * i * (i - 1) / 2) * rfac[i] % Mod;
	G[0] = 1;

	Inverse(G, F, n);
	For(i, 0, n - 1) F[i] = i >= k ? 0 : (Mod - F[i] + (i == 0 ? 2 : 0)) % Mod;
	F[0] = Mod - 1;

	Inverse(F, A, n);
	For(i, 0, n - 1) A[i] = A[i] * fac[i] % Mod;
	
	printf("%lld\n", (G[m] * fac[m] + A[m]) % Mod);
	return 0;
}
本文可以转载,但必须附上原文链接,否则你会终生找不到妹子!!!欢迎关注我的CSDN: ahyjjr