NKOJ 4028（HZOI 2015）疯狂的机器人（NTT+卡特兰数）

发表于 |
字数统计: 983字 | 阅读时长 ≈ 5min

P4028[HZOI 2015]疯狂的机器人

问题描述

现在在二维平面内原点上有一只机器人

他每次操作可以选择向右走，向左走，向下走，向上走和不走(每次如果走只能走一格）

但是由于本蒟蒻施展的大魔法，机器人不能走到横坐标是负数或者纵坐标是负数的点上

否则他就会big bang

给定操作次数n，求有多少种不同的操作序列使得机器人在操作后会回到原点

输出答案模998244353后的结果

注意如果两个操作序列存在某一时刻操作不同，则我们认为这两个操作序列不同

输入格式

输入n，表示操作次数

n<=100000

输出格式

按要求输出答案

样例输入

3

样例输出

3

首先不考虑不走的情况，容易发现上下走和左右走是独立的，而只考虑上下走的话等价于一个进出栈序列，那么就是一个卡特兰数，因此我们令不考虑不走，走$2k$步的方案数为$G(2k)$，由于卡特兰数第k项为$\frac{C_{2k}^{k}}{k+1}$，容易得到
$$
G(2k)=\sum_{i=0}^{k}\frac{C_{2i}^{i}}{i+1}\times \frac{C_{2k-2i}^{k-i}}{k-i+1}\times C_{2k}^{2i}
$$
即枚举上下走的步数，然后排列一下。前两项分别表示上下走和左右走的方案数。然后打开组合数得到
$$
G(2k)=\sum_{i=0}^{k}\frac{(2i)!}{i!(i+1)!}\times \frac{(2k-2i)!}{(k-i)!(k-i+1)!}\times\frac{(2k)!}{(2i)!(2k-2i)!}
$$
化简一下得到
$$
G(2k)=(2k)!\sum_{i=0}^{k}\frac{1}{i!(i+1)!}\times\frac{1}{(k-i)!(k-i+1)!}
$$
容易发现这是个卷积，因此可以用NTT来加速。

然后考虑不走的情况，令最终方案数为$F(n)$，容易得到
$$
F(n)=\sum_{i=0}^{n}C_{n}^{i}\times G(n-i)
$$
这也是个卷积，但只需要算一项，那么直接暴力枚举就行了。也可以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
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#define ll long long
#define N 400005
using namespace std;
const ll P=998244353LL,g=3;
ll jc[N],inv[N],inv_jc[N],D[N];
ll wi[N],A[N],B[N];
ll QM(ll a,ll b)
{
	ll o=1;a%=P;
	while(b)
	{
		if(b&1)o=o*a%P;
		b>>=1;a=a*a%P;
	}
	return o;
}
void NTT(ll C[],ll n,ll ty)
{
	ll i,j,k,m,t0,t1;
	for(i=j=0;i<n;i++)
	{
		if(i<j)swap(C[i],C[j]);
		for(k=n>>1;(j^=k)<k;k>>=1);
	}
	wi[0]=1;
	for(m=1;m<n;m<<=1)
	{
		t0=QM(g,P-1+ty*(P-1)/(m<<1));
		for(i=1;i<m;i++)wi[i]=wi[i-1]*t0%P;
		for(k=0;k<n;k+=m<<1)
		for(i=k;i<k+m;i++)
		{
			t0=C[i];
			t1=C[i+m]*wi[i-k]%P;
			C[i]=t0+t1;C[i]-=C[i]<P?0:P;
			C[i+m]=t0-t1;C[i+m]+=C[i+m]<0?P:0;
		}
	}
	if(ty==1)return;t0=QM(n,P-2);
	for(i=0;i<n;i++)C[i]=C[i]*t0%P;
}
int main()
{
	ll n,i,j,k,L=1;inv[0]=jc[0]=inv[1]=jc[1]=inv_jc[0]=inv_jc[1]=A[0]=1;
	scanf("%lld",&n);while(L<=n+n)L<<=1;
	for(i=2;i<=n+n;i++)inv[i]=(P-P/i)*inv[P%i]%P;
	for(i=2;i<=n+n;i++)jc[i]=jc[i-1]*i%P;
	for(i=2;i<=n+n;i++)inv_jc[i]=inv_jc[i-1]*inv[i]%P;
	for(i=0;i<=n;i++)D[i]=inv_jc[i]*inv_jc[i]%P*inv[i+1]%P;
	NTT(D,L,1);
	for(i=0;i<L;i++)D[i]=D[i]*D[i]%P;
	NTT(D,L,-1);
	for(i=0;i<=n;i+=2)B[i]=jc[i]*D[i>>1]%P;
	for(i=1;i<=n;i++)A[i]=A[i-1]*(n-i+1)%P*inv[i]%P;
	NTT(A,L,1);NTT(B,L,1);
	for(i=0;i<L;i++)A[i]=B[i]*A[i]%P;
	NTT(A,L,-1);
	printf("%lld",(A[n]%P+P)%P);
}