Submission #67787497

---

Source Code Expand

// created:  2025-07-20 20:44:52
#include<cstdio>
#include<cctype>
#include<algorithm>
#include<atcoder/convolution>
#define F(i,l,r) for(int i=l,i##_end=r;i<i##_end;++i)
#define I128 //||is_same<T,__int128_t>::value||is_same<T,__uint128_t>::value
using namespace std;
template<typename T>enable_if_t<is_integral<T>::value I128,void> readmain(T &x)
{
	bool neg=false;int c=getchar();
	for(;!isdigit(c);c=getchar())if(c=='-')neg=true;
	for(x=0;isdigit(c);c=getchar())x=(T)(10*x+(c-'0'));
	if(neg)x=-x;
}
template<typename T>T& read(T &x){readmain(x);return x;}
template<typename T,typename ...Tr>void read(T &x,Tr&... r){readmain(x);read(r...);}
typedef atcoder::modint998244353 mint;
constexpr int N=3e5+5,B=1000;
mint fac[N],ifac[N];
mint bn(int n,int m){return fac[n]*ifac[m]*ifac[n-m];}
vector<mint> solve(int n,int m,int vs,int vt)
{
	vector<mint> ans(m+1);--vs;--vt;
	if(n<=B)
	{
		vector<mint> f(n),g(n);
		f[vs]=1;
		F(i,0,m+1)
		{
			if(i)
			{
				F(j,1,n-1)g[j]=f[j-1]+f[j+1];
				g[0]=0;
				F(j,1,min(n,2))g[0]+=f[j];
				g[n-1]=0;
				F(j,max(0,n-2),n-1)g[n-1]+=f[j];
				swap(f,g);
			}
			ans[i]=f[vt];
		}
	}
	else
	{
		F(i,0,m+1)
		{
			if((i^vs^vt)&1)continue;
			mint sgn=1;
			for(int is=vs,ax=n;;is=2*ax-is,ax+=n+1,sgn=-sgn)
			{
				if(abs(vt-is)>i)break;
				ans[i]+=sgn*bn(i,(vt-is+i)>>1);
			}
			sgn=1;
			for(int is=vs,ax=-1;is=2*ax-is,ax-=n+1,sgn=-sgn,1;)
			{
				if(abs(vt-is)>i)break;
				ans[i]+=sgn*bn(i,(vt-is+i)>>1);
			}
		}
	}
	return ans;
}
vector<mint> trans(vector<mint> a,bool sgn)
{
	int n=(int)a.size();
	vector<mint> b(n);
	F(i,0,n)a[i]*=ifac[i],b[i]=sgn&&(i&1)?-ifac[i]:ifac[i];
	a=atcoder::convolution(a,b);
	a.resize(n);
	F(i,0,n)a[i]*=fac[i];
	return a;
}
int main()
{
	fac[0]=1;
	F(i,1,N)fac[i]=fac[i-1]*mint::raw(i);
	ifac[N-1]=fac[N-1].inv();
	for(int i=N;--i;)ifac[i-1]=ifac[i]*mint::raw(i);
	int h,w,t,a,b,c,d;read(h,w,t,a,b,c,d);
	vector<mint> v1=solve(h,t,a,c);
	vector<mint> v2=solve(w,t,b,d);
	v1=trans(v1,false);
	v2=trans(v2,false);
	F(i,0,t+1)v1[i]*=v2[i];
	v1=trans(v1,true);
	printf("%d\n",v1[t].val());
	return 0;
}

Submission Info

Judge Result