G - Count Sequences

考虑差分.

$b_1=a_1,b_i=a_i-a_{i-1},b_{n+1}=m-a_{n}b\_1=a\_1,b\_i=a\_i-a\_\{i-1\},b\_\{n+1\}=m-a\_n$.

对于$b_{i}b\_i$%$33$来说.

显然除了第$11$项和第$n+1n+1$项可以是任意模$3\mathrm{为}0\mathrm{/}1\mathrm{/}23为0/1/2$中的一个外.其他只能是$1\mathrm{/}21/2$.

通过$b_{n+1}b\_\{n+1\}$调节最大值的大小.

然后可以通过枚举$b_1,b_{n+1}b\_1,b\_\{n+1\}$,枚举$1\mathrm{/}2\{1/2\}$的数量来确定另外一个的数量.

比方说我枚举$11$的数量为$cc$,那么$22$的数量就是$2\ast (n-c)2*(n-c)$,剩余分配数量为$num=m-b_1-b_{n+1}-c-2\ast (n-c)num=m-b\_1-\; b\_\{n+1\}-c-2*(n-c)$.

两种情况:

$1.1.$ $numnum$%$33$为$00$.可以分配. 那么就是相当于$num\mathrm{/}3+nnum/3+n$个空隙分配$nn$块板子.方案数就是$C(num\mathrm{/}3+n,n)C(num/3+n,n)$.

$2.2.$ $numnum$%$33$不为$00$. 不可以分配.直接退出.

code:

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N=2e7+5;
const int mod=998244353;

int f[N],ivf[N];

int qp(int a,int b)
{
	int res=1;
	while(b)
	{
		if(b&1)	res=1ll*res*a%mod;		
		a=1ll*a*a%mod;
		b>>=1;
	}
	return res;
}

int C(int a,int b)
{
	return 1ll*f[a]*ivf[b]%mod*ivf[a-b]%mod;
}

void run()
{
	f[0]=1;int m=2e7;
	for(int i=1;i<=m;i++)	f[i]=1ll*f[i-1]*i%mod;
	ivf[m]=qp(f[m],mod-2);
	for(int i=m-1;i>=0;i--)	ivf[i]=1ll*ivf[i+1]*(i+1)%mod;
	int ans=0;
	int n;
	scanf("%d%d",&n,&m);
	for(int i=0;i<3;i++)
	{
		for(int j=0;j<3;j++)
		{
			for(int c=0;c<n;c++)
			{
				int d=2*(n-1-c);
				int num=m-i-j-c-d;
				if(num<0||num%3!=0)	continue;
				ans+=1ll*C(n-1,c)*C(n+num/3,n)%mod;
				ans%=mod;
			}
		}
	}
	printf("%d\n",ans);
}

int main()
{
	int T=1;
//	scanf("%d",&T);
	while(T--)	run();
	return 0;
}