题解：AT_abc458_e [ABC458E] Count 123

fish_love_cat · 2026-05-19 13:37:53 · 题解

简单数数。

把 2 看成隔板，1 和 3 看成异色球，于是变成有 n 个有标号盒子 a 个无标号蓝球 b 个无标号红球，求不存在一个盒子同时装有红球蓝球，盒子可以为空的分配方案数。

假设我们现在没有「不存在一个盒子同时装有红球蓝球」的要求，显然可以直接分别对每一种球做一遍插板。

加上限制感觉比较困难，考虑容斥。

所以我们计算至少有 i 个盒子装了异色球的方案数。

这个的计算直接强行划定 i 个盒子，然后往里面预先放入一个红球和一个蓝球，最后一样插板即可。

时间复杂度于是做到了线性。

inline void solve(){
    int na,n,nb;
    cin>>na>>n>>nb;
    n++;
    int ans=0,op=1;
    for(int i=0;i<=min({na,n,nb});i++)
    ans=(ans+op*C(n,i)%mod*C(n-1+na-i,na-i)%mod*C(n-1+nb-i,nb-i)%mod)%mod,ans+=mod,ans%=mod,op*=-1;
    cout<<ans;
}
// 科里拿第尔契市！

// 历史汇集之地！苍空的宝石箱！浪漫与传说的大杂烩！