ToB企服应用市场:ToB评测及商务社交产业平台

标题: 10 月 3 日解题报告 [打印本页]

作者: 灌篮少年 时间: 2024-10-3 20:14
标题: 10 月 3 日解题报告
10 月 3 日题解

Tasklist

[T1] ARC_134_C
[T2] ARC_108_D
[T3] ARC_137_C
[T4] ARC_064_E
[T1] ARC_134_C The Majority

标题

由于原翻译有些重点并没有点出来，以是这里给出原题直译而不是带有《原神》游戏专业术语的转译版本。
有编号为 $1$ 到 $K$ 的 $K$ 个盒子。最初，所有的盒子都是空的。
Snuke 有一些球，上面写着从 $1$ 到 $N$ 的整数。此中 $a_i$ 个球的编号为 $i$ 。写有雷同整数的球不能被区分。
Snuke 决定把他所有的球都放进盒子里。他希望数字为 $1$ 的球在每个盒子中都占多数。换句话说，在每个盒子中，编号为 $1$ 的球的数目应该大于其他球的数目。
求使用这种方式将所有球放入箱子的方案数。
答案对 $998244353$ 取模。
思路

直接按照上面的翻译写了
咋一看肯定是分列组合的题。
最直接的想法就是我枚举每个箱子放多少哪种球，但这样显然会超时。
反过来想，如果没有 $1$ 号球必须比别的球多的限定，这题直接挨个隔板就行。
现在有这条限定了。如果我直接把 $1$ 球和后面每个球配对就可以了，这样就可以不消考虑这条限定了…………吗？
显然，原题是大于不是大于等于。
以是我们再把剩下的 $1$ 种类球放到每个盒子里各一个。
此时如果 $1$ 种类球不够了，则不存在答案，方案数是 $0$，它对答案就没有影响，无视就行。
如果还剩 $1$ 种类球，直接用隔板法隔就行。
考虑完剩下的 $1$ 种类球后，我们考虑剩下的所有球。
由于此时每个盒子里都有 1 个 $1$ 球，以是剩下每种球都单独考虑怎么放就行。
由于前面已经把每种球匹配起来了，可以直接使用隔板法计算答案。
最终公式为 $ C^{K - 1}{K + a^n - 1} \times \prod^{N} C^{K - 1}_{K + a_i - 1} $。
由于有除法，以是需要写个逆元。
Code

MD 又没调出来就不写了
[code]#include using namespace std;const int N=1e5+5;const int mod=998244353;int n,k;long long a[N];long long fac[N],inv[N];long long ans;long long modpow(int x,int y){ long long sum=1; for(;y!=0;y>>=1){ if(y&1) sum=sum*x%mod; x=x*x%mod; } return sum%mod;}long long C(long long n,long long m){ long long reu=1; for(int i=m+1;in>>k; for(int i=1;i>a,sum+=a; sum-=a[1]; a[1]-=sum+k; if(a[1]1||(a[n]-n)%2==0) coutsx>>sy>>ex>>ey>>n; for(int i=1;i>c.x>>c.y>>c.r; double tmpdis; long long deltax; long long deltay; for(int i=1;i

欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/) Powered by Discuz! X3.4