QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#226996#6736. Alice and BobBILLION_mengyi#TL 0ms0kbC++20989b2023-10-26 19:35:352023-10-26 19:35:35

Judging History

你现在查看的是最新测评结果

  • [2023-10-26 19:35:35]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:0kb
  • [2023-10-26 19:35:35]
  • 提交

answer

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
const int N=10000010,mod=998244353;

ll fact[N],infact[N],jc[N];//阶乘和阶乘的逆元 

ll qmi(ll a,ll k,ll p)
{
	ll res=1;
	while(k)
	{
		if(k&1)
		{
            if(res>=mod) res%=mod;
			res=res*a%p;
		}
        if(a>=mod) a%=mod;
		a=a*a%p;
		k>>=1;
	}
	return res;
}

ll C(ll a,ll b)
{
    if(b>a) return 0;
    return fact[a]*infact[b]%mod*infact[a-b]%mod;
}

void solve()
{	
	jc[1]=1;jc[0]=1;
	fact[0]=infact[0]=1;
	for(ll i=2;i<N;i++) (jc[i]=jc[i-1]*i)%=mod;
	for(ll i=1;i<N;i++)
	{
		fact[i]=fact[i-1]*i%mod;
		infact[i]=infact[i-1]*qmi(i,mod-2,mod)%mod;
	}
	ll x=C(9,0);
	ll n;cin>>n;
	ll ans=0;
	ll mx=(n+1)/2;
	for(int i=1;i<=mx;i++)
	{
		ll a=C(n-i,i-1),b=jc[i-1],c=jc[n-i];
		(ans+=a*b%mod*c)%=mod;
	}
	cout<<ans<<"\n";
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	ll T=1;
	while(T--)
	{
		solve();
	}
	return 0;
}

詳細信息

Test #1:

score: 0
Time Limit Exceeded

input:

1

output:

1

result: