题解 SS221112B【Y】

problem

\(2n\) 个有顺序的整数，每个数在 \([0,m]\) 内随机独立均匀生成，求前一半的和大于后一半的和的方案数。\(T,n,m\leq 2000\)。

solution 0

总方案数是明晰的：\(S=(m+1)^{2n}\)。

我们可以认为，在这些方案中，有 \(p\) 种方案使得前一半大于后一半，全部反过来就有 \(p\) 种方案使得后一半大于前一半，剩下的是前一半和后一半相等的 \(q\)。

前一半和后一半相等，由于它们是独立的，所以对两边进行背包，令 \(f_i\) 为取到总和为 \(i\) 的方案数，那么 \(q=\sum_i f_i^2\)。

考虑求出 \(f\)，我们发现是多项式快速幂，还是任意模数卷积，这时你已经 TLE 了。

solution 1

两种推法殊途同归：

1. \(f_i=f_{nm-i}\Rightarrow \sum_{i\leq nm}f_i^2=\sum_{i\leq nm}f_if_{nm-i}=[x^{nm}]f^2\)。
2. 考虑相当于左边的取值范围是 \([0,m]\)，右边的取值范围是 \([-m,0]\)，然后总和是零。神来之笔：右边整体加上 \(m\)，那么就是整个数列 \([0,m]\) 且和为 \(nm\)。

容斥部分：我们先讲做法，

1. 钦定 \(i\) 个数超过上界，将它们减掉 \((m+1)\)，然后插一次板。\(f(i)=\binom{t+2n-1}{2n-1},\text{where }t=nm-i(m+1)\)。
2. \(ans=\sum_{0\leq i\leq 2n}(-1)^i\binom{2n}{i}f(i)\)。

这里减掉 \((m+1)\) 是因为我们知道这一部分肯定 \(>m\)，减掉之后它的下界就和其它的一样可以正常算。

详解：神秘的容斥系数

补课，膜拜 sshwy。

题面转换

假如我们搞一个很抽象的 \(B,J,M,P\) 分别表示强制 \(a_1\) 不合法的方案，\(a_2\) 不合法的方案，\(a_3\) 不合法的方案，\(a_4\) 不合法的方案。

求所有合法的方案，答案是 \(|U|-|B\cup J\cup M\cup P|\) 对吧？

容斥原理的系数

容斥原理的式子我们先看一下：

好的我们证一下：以一个方案 \(f\not\in A,f\in B,f\in C,f\in D\) 举例，在第一行算了 \(\binom{3}{1}\) 次，第二行减掉 \(\binom{3}{2}\) 次，第三行加上 \(\binom{3}{3}\) 次。从组合数学的角度，一个方案如果恰好有 \(k\) 个不合法的值那么它会被算：

这意味着如果 \(k=0\) 即合法方案会被算 \(0\) 次，非法方案会被算 \(1\) 次，拿全集去减，就是我们心心念念的答案啦。

我们归纳一下：

容斥系数已经在外面的减号那里搞掉了。

回到原题

醒醒，这是在枚举 \(|S|=i\)，然后因为我们的变量没有本质区别，所以我直接数有多少个 \(|S|=i\)，有 \(\binom{2n}{i}\) 个对吧。

这些集合的答案都是一样的，\(f(i)\)，容斥系数也是一样的，相当于运用了乘法的定义将指数优化成线性。

实际上“钦定方案 \(f\) 中 \(a_1\) 顶过上界”就和“定义 \(A\) 是 \(a_1\) 不合法的方案，则 \(f\in A\)”是一模一样的。我们应该对于每个变量都看作一个集合，就会好理解很多。

code

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#ifdef LOCAL
#define debug(...) fprintf(stderr,##__VA_ARGS__)
#else
#define debug(...) void(0)
#endif
typedef long long LL;
int P;
void red(LL&x){x=(x%P+P)%P;}
LL qpow(LL a,LL b,int p){LL r=1;for(a%=p;b;b>>=1,a=a*a%p) if(b&1) r=r*a%p; return r;}
template<int N> struct C_prime{
	LL fac[N+10],ifac[N+10]; int P;
	C_prime(int P=2):P(P){
		for(int i=fac[0]=ifac[0]=1;i<=N;i++) fac[i]=fac[i-1]*i%P;
		ifac[N]=qpow(fac[N],P-2,P);
		for(int i=N-1;i>=1;i--) ifac[i]=ifac[i+1]*(i+1)%P;
	}
	LL operator()(int n,int m){return n>=m?fac[n]*ifac[n-m]%P*ifac[m]%P:0;}
};
int n,m;
C_prime<4000010> C;
int mian(){
	LL ans=0,S=n*m;
	for(int i=0;i<=2*n;i++) debug("i=%d\n",i),red(ans+=(i&1?P-1:1)*C(n*2,i)%P*C(S-i*(m+1)+n*2-1,n*2-1)%P);
	debug("ans=%lld\n",ans);
	red(ans*=qpow(qpow(m+1,n*2,P),P-2,P));
	printf("%lld\n",(1-ans+P)*qpow(2,P-2,P)%P); 
	return 0;
}
void reset(){
	
}
int main(){
freopen("y.out","w",stdout);
//	#ifdef LOCAL
 	freopen("y.in","r",stdin);
//	#endif
	for(scanf("%d%*d",&P),C=C_prime<4000010>(P);~scanf("%d%d",&n,&m);reset(),mian());
	return 0;
}

general

着力解决 \(h(n,m,k)\)：将 \(n\) 个相同的小球放入 \(m\) 个互不相同的盒子里，要求每个盒子最少 \(0\) 个最多 \(k\) 个的方案数（变量名换了哦）

• 辅助 \(g(n,m)\)：将 \(n\) 个相同的小球放入 \(m\) 个互不相同的盒子里，要求每个盒子最少 \(0\) 个最多 \(k\) 个的方案数，明显 \(g(n,m)=\binom{n+m-1}{m-1}\)。
• 容斥。考虑钦定 \(i\) 个盒子溢出了，将这些盒子的球数减去 \((k+1)\)。现在数一下：\(\Delta=i(k+1),ans=g(n-\Delta,m)\)。
• 盲猜容斥系数为 \((-1)^i\binom{m}{i}\)，所以 \(h(n,m,k)=\sum_{0\leq i} (-1)^i\binom{m}{i}g(n-\Delta,m)\)。

扩展：\(H(n,m,[L,R])\) 表示将 \(n\) 个相同的小球放入 \(m\) 个互不相同的盒子里，要求每个盒子最少 \(L\) 个最多 \(R\) 个的方案数，很不幸它是 \(h(n-mL,m,R-L)\)。