自动搬运

查看原文

来自洛谷，原作者为

	SSerxhs 我仍然在/无人问津的阴雨霉湿之地/和着雨音/唱着没有听众的歌曲

搬运于2025-08-24 22:08:25，当前版本为作者最后更新于2019-04-10 21:39:27，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

提供一种乱搞做法

由递推式可以知道,$f[i][j](j\leq i)$一定是一个关于$i$的$j-1$次函数。具体证明可以通过数学归纳法，这里略去。所以可以考虑打表打出$f[2000][1000]$以内的值，用拉格朗日重心插值法$O(k)$插值并求值，总复杂度$O(k^2)$。

#include <stdio.h>
#include <string.h>
typedef long long ll;
const int N=2002,M=1002,p=998244353;
int f[N][M],w[M],l[M],r[M],ifac[M],inv[M];
ll qq;
int main()
{
	register int n,m,i,j,k,tq,q,ans=0;
	scanf("%lld%d",&qq,&m);
	n=m<<1;tq=qq%p;tq+=p;
	for (i=1;i<=n;i++) f[i][1]=1;
	for (i=2;i<=n;i++)
	{
		k=i;if (k>m) k=m;
		for (j=1;j<=k;j++)
		{
			if ((f[i][j]=f[i-1][j]+f[i][j-1])>=p) f[i][j]-=p;
			if ((f[i][j]=f[i][j]+f[i-1][j-1])>=p) f[i][j]-=p;
		}
	}
	ifac[0]=ifac[1]=inv[1]=1;
	for (i=2;i<=m;i++) ifac[i]=(ll)ifac[i-1]*(inv[i]=p-(ll)p/i*inv[p%i]%p)%p;
	for (i=1;i<=m;i++)
	{
		k=(i<<1)-1;q=tq-i;
		for (j=i;j<=k;j++) w[j-i]=f[j][i];k-=i;
		for (j=0;j<=k;j++)
		{
			w[j]=(ll)w[j]*ifac[j]%p*ifac[k-j]%p;
			if ((j^k)&1) w[j]=p-w[j];
		}
		l[0]=q;
		for (j=1;j<=k;j++) l[j]=(ll)l[j-1]*(q-j)%p;
		r[k]=q-k;
		for (j=k-1;~j;j--) r[j]=(ll)r[j+1]*(q-j)%p;
		ans=(ans+(ll)r[1]*w[0]+(ll)l[k-1]*w[k])%p;
		for (j=1;j<k;j++) ans=(ans+(ll)l[j-1]*r[j+1]%p*w[j])%p;
	}
	printf("%d",(ans+1)%p);
}