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^{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(a1||(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]