分析:
p为大于3素数就很巧妙,1+2+3+...+p-1+p一定是p的倍数
开始我想按照k<p和k>=p两种情况来考虑
对于k<p,一定是在1+2+3+...+p-1+p上的变种
很容易化简为kn
但是对于k>=p的情况就非常复杂,因为不一定是上式的变种
放弃这种想法
先给出答案吧
((C(pk,p)-k)/p)+k
除去1+2+3+...+p和p+1+p+2+...+2p这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;
}