Loj 6609 无意识的石子堆 加强版

Posted on | Edited on | Views:

容斥原理 + NTT .

每行必须有 $2$ 个石子,考虑枚举 $k$ 列有 $2$ 个石子,则有 $2(n-k)$ 列有 $1$ 个石子.

记 $S(k)$ 表示选出了这 $2n-k$ 列后放入石子的方案数,则
$$
ans=\sum_{k=0}^n \binom{m}{k} \binom{m-k}{2(n-k)} \cdot S(k)
$$
可以转化成二分图模型,左边有 $n$ 个点,度数均为 $2$ ,右边有 $k$ 个点度数为 $2$ ,有 $2(n-k)$ 个点度数为 $1$ .

那么 $S(k)$ 就是这样的二分图的数目.

将每个度数为 $2$ 的点拆成两个点,直接在这 $4n$ 个点中连边,再去掉出现了重边的方案数.

考虑容斥,枚举有 $i$ 条重边,得到

$$
S(k)=\frac{1}{2^{n+k}} \sum_{i=0}^n (-1)^i \binom{n}{i} \binom{k}{i} i!\cdot 2^i\cdot (2n-2i)!
$$
这可以用 NTT 做一次卷积直接算出,时间复杂度 $O(n\log n)$ .

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
//%std
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
inline ll read()
{
	ll out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		fh=-1,jp=getchar();
	while (jp>='0'&&jp<='9')
		out=out*10+jp-'0',jp=getchar();
	return out*fh;
}
const int P=943718401,G=7;
int add(int a,int b)
{
	return (a+b>=P)?(a+b-P):(a+b);
}
void inc(int &a,int b)
{
	a=add(a,b);
}
int mul(int a,int b)
{
	return 1LL * a * b % P;
}
int fpow(int a,int b)
{
	int res=1;
	while(b)
	{
		if(b&1)
			res=mul(res,a);
		a=mul(a,a);
		b>>=1;
	}
	return res;
}
const int MAXN=8e6+10;
int rev[MAXN],omega[MAXN],inv[MAXN],curn=0;
void init(int n)
{
	if(curn==n)
		return;
	for(int i=0;i<n;++i)
		rev[i]=(rev[i>>1]>>1)|((i&1)*(n>>1));
	for(int l=2;l<=n;l<<=1)
	{
		omega[l]=fpow(G,(P-1)/l);
		inv[l]=fpow(omega[l],P-2);
	}
	curn=n;
}
void DFT(int *a,int n,bool invflag)
{
	init(n);
	for(int i=0;i<n;++i)
		if(i<rev[i])
			swap(a[i],a[rev[i]]);
	for(int l=2;l<=n;l<<=1)
	{
		int m=l>>1;
		int gi=omega[l];
		if(invflag)
			gi=inv[l];
		for(int *p=a;p!=a+n;p+=l)
		{
			int g=1;
			for(int i=0;i<m;++i)
			{
				int t=mul(g,p[i+m]);
				p[i+m]=add(p[i],P-t);
				p[i]=add(p[i],t);
				g=mul(g,gi);
			}
		}
	}
	if(invflag)
	{
		int invn=fpow(n,P-2);
		for(int i=0;i<n;++i)
			a[i]=mul(a[i],invn);
	}
}
void NTT(int *A,int *B,int *C,int lenA,int lenB)
{
	int lenC=lenA+lenB-1,n=1;
	while(n<lenC)
		n<<=1;
	static int a[MAXN],b[MAXN];
	copy(A,A+lenA,a);
	fill(a+lenA,a+n,0);
	copy(B,B+lenB,b);
	fill(b+lenB,b+n,0);
	DFT(a,n,false);
	DFT(b,n,false);
	for(int i=0;i<n;++i)
		C[i]=mul(a[i],b[i]);
	DFT(C,n,true);
}
int n,m,fac[MAXN],invfac[MAXN];
int A[MAXN],B[MAXN],S[MAXN];
int binom(int M,int N)
{
	if(M<0 || N<0 || M<N)
		return 0;
	return mul(fac[M],mul(invfac[N],invfac[M-N]));
}
ll M;
int main()
{
	n=read(),M=read();
	m=M%P;
	fac[0]=1;
	for(int i=1;i<=2*n;++i)
		fac[i]=mul(fac[i-1],i);
	invfac[2*n]=fpow(fac[2*n],P-2);
	for(int i=2*n-1;i>=0;--i)
		invfac[i]=mul(invfac[i+1],i+1);
	int pw=1,inv2=(P+1)>>1;
	for(int i=0;i<=n;++i)
	{
		A[i]=mul(binom(n,i),mul(pw,fac[2*n-2*i]));
		if(i&1)
			A[i]=add(P,-A[i]);
		B[i]=invfac[i];
		pw=mul(pw,2);
	}
	NTT(A,B,S,n+1,n+1);
	pw=fpow(inv2,n);
	for(int i=0;i<=n;++i)
	{
		S[i]=mul(S[i],mul(fac[i],pw));
		pw=mul(pw,inv2);
	}
	int pos=(M>=2*n)?0:2*n-M;
	int ans=0,tmp=1;
	for(int i=pos;i<=2*n-1;++i)
		tmp=mul(tmp,add(m+i+1,P-2*n));
	for(int i=pos;i<=n;++i)
	{
		int delta=mul(mul(invfac[i],invfac[2*n-2*i]),tmp);
		delta=mul(delta,S[i]);
		inc(ans,delta);
		tmp=mul(tmp,fpow(add(m+i+1,P-2*n),P-2));
	}
	cout<<ans<<endl;
	return 0;
}