chocolate Counting(牛客)

chocolate Counting(牛客)
分析:
p为大于3素数就很巧妙,1+2+3+...+p-1+p一定是p的倍数
开始我想按照k<p和k>=p两种情况来考虑
对于k<p,一定是在1+2+3+...+p-1+p上的变种
chocolate Counting(牛客)
很容易化简为kn
但是对于k>=p的情况就非常复杂,因为不一定是上式的变种
放弃这种想法
先给出答案吧
((C(pk,p)-k)/p)+k
除去1+2+3+...+p和p+1+p+2+...+2
p这k组
将其他组每p个分为一组,每组就会有一个合法的

#include <bits/stdc++.h>
using namespace std;
const int mod=998244353;
inline int dec(int a,int b){return (a-b<0)?a-b+mod:a-b;}
inline int quick_pow(int a,int b){
	int ret=1;for(;b;b>>=1,a=1ll*a*a%mod)if(b&1)ret=1ll*ret*a%mod;
	return ret;
}
inline int Inv(int a){
	return quick_pow(a,mod-2);
}
#define ll long long
int T,p,k;
inline int C(ll n,ll m){
	ll fz=1,fm=1;
	for(int i=0;i<m;++i)fz=fz*((n-i)%mod)%mod,fm=fm*(i+1)%mod;
	return 1ll*fz*Inv(fm)%mod;
}
int main(){
	scanf("%d",&T);
	while(T--){
		scanf("%d %d",&p,&k);
		printf("%d\n",(1ll*dec(C(1ll*p*k,p),k)*Inv(p)+k)%mod);
	}
	return 0;
}
上一篇:Effective Python 第7条:enumerate取代range


下一篇:logstash filter mutate output