题解：P7950 [✗✓OI R1] 后方之水

· · 题解

从一个专门存以前看了半天不会做但结论很精简的题的题单里翻出来的题。诶不是以前为啥没想出来来着，再捡起来怎么秒了。

这个子问题看起来就像……

我们知道合并顺序无关结果，用分配律拆开可得答案为所有数对的乘积之和。

然后 \sum a_i=S 这个东西有个很常见的组合意义就是在 S 个东西间插 n-1 个板子，那么每种划分是对于每个盒子对，贡献其内元素的乘积。

这个玩意很容易想到是在两个盒子里各自选择一个球的方案数，于是就变成对于每个划分，其贡献为选出两个球且这两个球不在一个盒子里的方案数。

那你把板子和特殊选中的球单独拉出来考虑，你需要在已有的所有盒子中选出两个不同的盒子提前放入两个相同的球。

确定好这两个以后再放入普通球，容易发现这个时候特殊球和板子唯一的分别就是如果是板子与板子相邻那么必须得放一个球，球和板子相邻则不必。

考虑直接在剩下的 n-2 个盒子里各放一个球，然后特殊球和板子就没有分别了，统一当成可以相邻的板子，根据特殊球左右普通球数量的不同恰好可以得到所有球被选择的方案，于是正常插板即可。

注意 S 很大但 \sum n 很小，不用预处理阶乘暴力算组合数即可。

闲话，先做了篮球杯那题才看到了这题，然后这题就鸽了，结果后来 abc 考了个约等于双倍经验的东西（题号忘了），绷不住了。

#include<bits/stdc++.h>
#define int long long
using namespace std;
#define mod 998244353
int qpow(int a,int b=mod-2){
    int ans=1;
    while(b){
        if(b&1)ans=ans*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return ans;
}
int C(int n,int m){
    int ret=1;
    for(int i=0;i<m;i++)
    ret=ret*(n-i)%mod;
    for(int i=1;i<=m;i++)
    ret=ret*qpow(i)%mod;
    return ret;
}
void solve(){
    int n,s;
    cin>>n>>s;
    s-=n;
    cout<<C(n,2)*C(s+n+1,n+1)%mod<<'\n';
}
signed main(){
    int t;
    cin>>t;
    while(t--)solve();
    return 0;
}
// 高明程度排在可蓉后面的是菈琪旭。
// 该怎么说呢，她似乎非常习惯应付撒野成性的小孩。
// 至于理由嘛……为了她所有朋友的名誉著想，还是别深究太多。