[CF1912B] Blueprint for Seating

DoctorWang 模拟赛 T2。

把两边舷窗黏在一起，这样就变成 k 个对称块，方便看。

注意到分成若干个 \lfloor \frac{n}{k} \rfloor 和 \lfloor \frac{n}{k} \rfloor +1 就是答案，调整法随便调都不会更优，于是第一问做完了。

第二问需要手玩一下，发现可以把两个奇数重组为两个偶数，比如 5-5 和 4-6 答案是一样的。

不妨设 \lfloor \frac{n}{k} \rfloor 是奇数，否则跟 \lfloor \frac{n}{k} \rfloor+1 对称地换一下。能不能继续重组呢？手玩一下一奇一偶重组和两个偶数重组会变劣，所以枚举一下把多少组 2 \times \lfloor \frac{n}{k} \rfloor 拆成 \lfloor \frac{n}{k} \rfloor-1 和 \lfloor \frac{n}{k} \rfloor+1，然后多重排列算一下就莫名其妙地对了。

#include<iostream>
#include<cstdio>
#define int long long
using namespace std;
const int N=2e5;
const int mod=998244353;
int n,k;
inline int ksm(int a,int b){
    int res=1;
    for(;b;b>>=1){
        if(b&1)res=res*a%mod;
        a=a*a%mod;
    }
    return res;
}
inline int inv(int x){
    return ksm(x,mod-2);
}
int jc[N+5]={1},invjc[N+5];
inline void init(){
    for(int i=1;i<=N;i++)jc[i]=jc[i-1]*i%mod;
    for(int i=0;i<=N;i++)invjc[i]=inv(jc[i]);
}
inline int calc(int u){
    if(u<=1)return 0;
    return (u/2+u%2)*(u/2+1)-u;
}
inline int work1(int u,int kk){
    if(kk<=0||u<=0)return 0;
    int o=u/kk,h=u-o*kk;
    return (kk-h)*calc(o)+h*calc(o+1);
}
inline int work2(int u,int kk){
    if(kk<=0||u<=0)return 0;
    int o=u/kk,h=u-o*kk,g=kk-h;
    if(o==1)return jc[kk-1]*invjc[h-1]%mod*invjc[g]%mod;
    int ans=0;
    if(o%2==0)swap(h,g);
    for(int p=g;p>=0;p-=2){
        ans+=jc[kk]*invjc[p]%mod*invjc[(g-p)/2]%mod*invjc[h+(g-p)/2]%mod;
        if(p)ans+=jc[kk-1]*invjc[p-1]%mod*invjc[(g-p)/2]%mod*invjc[h+(g-p)/2]%mod;
        ans%=mod;
    }
    return ans;
}
signed main(){
    init();
    int T;
    cin>>T;
    while(T--){
        cin>>n>>k;
        cout<<work1(n,k)<<" "<<work2(n,k)<<endl;
    }
}