记录编号	617769	评测结果	AAAAA
题目名称	十二重计数法(第一关)	最终得分	100
用户昵称	这是一个假名	是否通过	通过
代码语言	C++	运行时间	6.542 s
提交时间	2026-07-28 20:28:43	内存使用	18.56 MiB

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

#ifdef ONLINE_JUDGE
#define inline __attribute__((always_inline))
#define debug(x)
#else
#define debug(x) cerr<<#x<<" = "<<x<<"\n";
#endif
#define int long long

const int N=400010,MOD=998244353;

int n,m,fac[N],inv[N],invf[N],p[N],H[N],dp[N];

int qpow(int a,int b,int mod)
{
	int ans=1;
	while(b)
	{
		if(b&1)
		{
			ans=ans*a%mod;
		}
		a=a*a%mod;
		b>>=1;
	}
	return ans;
}

int getinv(int x)
{
	x%=MOD;
	if(x<N)
	{
		return inv[x];
	}
	return qpow(x,MOD-2,MOD);
}

int C(int n,int m)
{
	if(m<0||m>n)
	{
		return 0;
	}
	return fac[n]*getinv(fac[m]*fac[n-m]%MOD)%MOD;
}

int s2(int n,int m)
{
	int res=0;
	for(int i=0;i<=m;i++)
	{
		int t=qpow(i,n,MOD)*getinv(fac[i]*fac[m-i]%MOD)%MOD;
		if((m-i)&1)
		{
			res=(res-t+MOD)%MOD;
		}
		else
		{
			res=(res+t)%MOD;
		}
	}
	return res;
}

void init()
{
	inv[0]=inv[1]=fac[0]=invf[0]=1;
	for(int i=2;i<N;i++)
	{
		inv[i]=(MOD-MOD/i)*inv[MOD%i]%MOD;
	}
	for(int i=1;i<N;i++)
	{
		fac[i]=fac[i-1]*i%MOD;
	}
	invf[N-1]=qpow(fac[N-1],MOD-2,MOD);
	for(int i=N-2;i>=1;i--)
	{
		invf[i]=invf[i+1]*(i+1)%MOD;
	}
	H[0]=1;
	for(int i=1;i<N;i++)
	{
		if(i&1)
		{
			H[i]=(H[i-1]-invf[i]+MOD)%MOD;
		}
		else
		{
			H[i]=(H[i-1]+invf[i])%MOD;
		}
	}
	p[0]=1;
	for(int i=1;i<N;i++)
	{
		int res=0;
		for(int k=1;;k++)
		{
			int g1=k*(3*k-1)/2;
			if(g1>i)
			{
				break;
			}
			if(k&1)
			{
				res=(res+p[i-g1])%MOD;
			}
			else
			{
				res=(res-p[i-g1]+MOD)%MOD;
			}
			int g2=k*(3*k+1)/2;
			if(g2>i)
			{
				break;
			}
			if(k&1)
			{
				res=(res+p[i-g2])%MOD;
			}
			else
			{
				res=(res-p[i-g2]+MOD)%MOD;
			}
		}
		p[i]=res;
	}
}

int dp1(int n,int lim)
{
	dp[0]=1;
	for(int i=1;i<=lim;i++)
	{
		for(int j=i;j<=n;j++)
		{
			dp[j]=(dp[j]+dp[j-i])%MOD;
		}
	}
	return dp[n];
}

int dfs2(int st,int sum,int par,int n)
{
	int res=0;
	int sgn=(par&1)?MOD-1:1;
	res=(res+sgn*p[n-sum])%MOD;
	for(int i=st;sum+i<=n;i++)
	{
		res=(res+dfs2(i+1,sum+i,par^1,n))%MOD;
	}
	return res;
}

int solve1(int n,int m)
{
	return qpow(m,n,MOD);
}

int solve2(int n,int m)
{
	if(n>m)
	{
		return 0;
	}
	return fac[m]*getinv(fac[m-n])%MOD;
}

int solve3(int n,int m)
{
	if(n<m)
	{
		return 0;
	}
	int ans=0;
	for(int i=0;i<=m;i++)
	{
		ans+=(i&1?-1:1)*C(m,i)%MOD*qpow(m-i,n,MOD)%MOD;
		ans%=MOD;
	}
	return (ans%MOD+MOD)%MOD;
}

int solve4(int n,int m)
{
	int res=0;
	for(int i=0;i<=m;i++)
	{
		int t=qpow(i,n,MOD)*invf[i]%MOD;
		int val=H[m-i];
		if(i==0)
		{
			val=(val-1+MOD)%MOD;
		}
		res=(res+t*val)%MOD;
	}
	return res;
}

int solve5(int n,int m)
{
	return n<=m;
}

int solve6(int n,int m)
{
	return s2(n,m);
}

int solve7(int n,int m)
{
	return C(n+m-1,m-1);
}

int solve8(int n,int m)
{
	return C(m,n);
}

int solve9(int n,int m)
{
	return C(n-1,m-1);
}

int solve10(int n,int m)
{
	if(m>=n)
	{
		return p[n];
	}
	int B=0;
	if(m<=B)
	{
		return dp1(n,m);
	}
	return dfs2(m+1,0,0,n);
}

int solve11(int n,int m)
{
	return n<=m;
}

int solve12(int n,int m)
{
	if(n<m)
	{
		return 0;
	}
	return solve10(n-m,m);
}

signed main()
{
	init();
	cin>>n>>m;
	cout<<solve1(n,m)<<"\n"<<solve2(n,m)<<"\n"<<solve3(n,m)<<"\n"<<solve4(n,m)<<"\n"
		<<solve5(n,m)<<"\n"<<solve6(n,m)<<"\n"<<solve7(n,m)<<"\n"<<solve8(n,m)<<"\n"
		<<solve9(n,m)<<"\n"<<solve10(n,m)<<"\n"<<solve11(n,m)<<"\n"<<solve12(n,m)<<"\n";
	return 0;
}