10 月 3 日解题报告
10 月 3 日题解Tasklist
ARC_134_C
ARC_108_D
ARC_137_C
ARC_064_E
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_{i = 2}^{N} C^{K - 1}_{K + a_i - 1}\)。
因为有除法，所以需要写个逆元。
Code
MD 又没调出来就不写了
#include using namespace std;const int N=1e5+5;const int mod=998244353;int n,k;long long a;long long fac,inv;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; a-=sum+k; if(aa; if(a-a>1||(a-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
页:
[1]