F题菜鸡题解

没等来官方题解，菜鸡不自量力发一发

说实话，F题还是蛮合我口味的，虽然赛时竭尽全力没能A掉，但是需要的知识点我都是掌握的，只是脑子迟顿，融会贯通的速度不够哈

设表示n步之后到达m点的路径个数，则根据题目的定义，可推导出递归关系：

设,对上面的递归公式左右乘, 然后从到累加起来： 整理下得到：.

0步操作只能到0，所以, 所以

要求在的系数和，其实是求在的系数和。

到这里，一个直白的想法就是快速幂+FFT展开，复杂度，n实在有点大，直接TLE，(菜鸡赛时还不死心，尝试多次常数优化...)

有趣的事情是，赛时有一小段时间，我把错看成了，这个可以简单分解, 这样子, 这样可以二项式展开成两个多项式，然后再FFT乘出来，（算法也不见得能过，此乃后话哈） 后来发现错误后，就没有在这个思路上延伸下去，有点可惜了的

赛后琢磨这个因式分解的思路，，出现complex number,但是，不影响generating function的正确性；唯一需要解决的问题是在模998244353的field内，是否存在，还好，即23是模998244353的square residule. 暴力搜索一下可得 (多少有点大，但是依然能暴力出来...)

这样可以展开成两个“共轭”的多项式，令,那么 , 所以,和是可以计算出来的。所以，到这里我就觉得只需要快速计算出和即可，FFT搞一把，然后就有TLE了哈...本地测试最大的数据要10s左右，我的FFT模板或许有优化的可能，但是把常数5倍优化掉可能性渺茫....

继续琢磨一下，要求的其实只是区间和，并不是每一项，所以可以遍历的每一项，找出每一项对应的区间和即可；使用前缀和就可以。（对也是一样），这样子复杂度就是的了！～

不知道官方正解到底是咋样的，等了半天也没等来官方题解....这题的着实有那么点，那啥哈

贴个草率的代码

#include<stdio.h>

typedef long long LL;
#define MOD 998244353
#define MAXN 3000004
int ft[MAXN], ift[MAXN];

int comb(int n, int m) {
	if (n<m) return 0;
	LL r=ft[n];
	r = (r*ift[m])%MOD;
	r = (r*ift[n-m])%MOD;
	return r;
}
int expit(LL b, int e) {
	LL r=1;
	while(e) {
		if (e&1) r=(r*b)%MOD;
		b=(b*b)%MOD;
		e>>=1;
	}
	return r;
}

int psr[MAXN];
int psi[MAXN];
int ss[MAXN];
#define QR23 457454087
int count(int *ps, int n, int m) {
	int r=0, s, e, i;
	ss[0]=0; for (i=0; i<=n; i++) ss[i+1]=(ss[i]+ps[i])%MOD;
	LL v;
	for (i=0; i<=n; i++) {
		// [-m+n, m+n]
		s=-m+n-i; if (s<0) s=0;
		e=m+n-i; if (e>n) e=n;
		v=ss[e+1]-ss[s]; if (v<0) v+=MOD;
		v*=ps[i]; v%=MOD;
		r+=v; r%=MOD;
	}
	return r;
}
int main() {
	int n, m, i, j;
	LL v, a, b, rp, ip, nrp, nip;
	scanf("%d %d", &n, &m);
	ft[0]=1; for (i=1; i<=n; i++) ft[i]=(ft[i-1]*(LL)i)%MOD;
	ift[n]=expit(ft[n], MOD-2);
	for (i=n-1; i>=0; i--) ift[i]=(ift[i+1]*(LL)(i+1))%MOD;
	a=expit(6, MOD-2);
	b=QR23; b*=a; b%=MOD;
	rp=1; ip=0;
	for (i=0; i<=n; i++) {
		v=comb(n, i);
		psr[n-i]=(v*rp)%MOD;
		psi[n-i]=(v*ip)%MOD;
		nrp=(a*rp-b*ip)%MOD; if (nrp<0) nrp+=MOD;
		nip=(a*ip+b*rp)%MOD;
		rp=nrp; ip=nip;
	}
	LL r=count(psr, n, m);
	r+=count(psi, n, m); r%=MOD;
	r*=expit(3, n); r%=MOD;
	printf("%lld\n", r);
	return 0;
}