hack某一篇题解的数据
查看原帖
hack某一篇题解的数据
531223
gbk002SNake楼主2021/9/27 22:02

105768 532165

倒数第三篇(手动艾特AWDD)

主程序中的for循环应该从n开始,否则i有可能小于n却计入答案,就跟你前面特判的一样,只不过你特判的不够。

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<algorithm>
#include<math.h>
using namespace std;

const int N=3e6;
const int mod=998244353;
int n,k,ans,fac[N+5],inv[N+5],infac[N+5];

void init()
{
	int i;scanf("%d%d",&n,&k);
	fac[0]=1;for(i=1;i<=N;++i) fac[i]=1LL*fac[i-1]*i%mod;
	inv[1]=1;for(i=2;i<=N;++i) inv[i]=1LL*inv[mod%i]*(mod-mod/i)%mod;
	infac[0]=1;for(i=1;i<=N;++i) infac[i]=1LL*infac[i-1]*inv[i]%mod;
}

int C(int x,int y)
{
	if(y>x) return 0;
	return 1LL*fac[x]*infac[y]%mod*infac[x-y]%mod;
}

void calc(int x,int y,int T)
{
	if(T<=0) return;
	int ret=C(x+y,x);
	if(T<=y) ret-=C(x+y,y-T);
	if(ret<0) ret+=mod;
	ans+=ret;if(ans>=mod) ans-=mod;
}

void work()
{
	int i,j;
	for(i=0,j=k;i<=k;++i,--j)
	{
		if(i<j) continue;
		else if(i==j) calc(i,j-1,i-n+1);
		else calc(i,j,i-n+1);
	}
	printf("%d\n",ans);
}

int main()
{
	init();
	work();
	return 0;
}
2021/9/27 22:02
加载中...