[Acwing] 1309. 车的放置 排列组合+费马小定理

前言

传送门 :

思路

我们将这个图,分成两个矩形

设我们在上面放了 i i i个车

我们考虑先选择行再选择列,因此对于行有 C b i C_{b}^i Cbi​

对于列有 A a i A_a^i Aai​ , 因此上面的选择的总方案数就是 C b i ∗ A a i C_b^i*A_a^i Cbi​∗Aai​

因此对于下半我们还需要选择 k − i k-i k−i 个车

同理对于行有 C d k − i C_d^{k-i} Cdk−i​

对于列考虑,因为上面已经选择了列,所以列的考虑就是 A a + c − i k − i A_{a+c-i}^{k-i} Aa+c−ik−i​

所以下面的总方案数就是 C d k − i ∗ A a + c − i k − i C_d^{k-i}*A_{a+c-i}^{k-i} Cdk−i​∗Aa+c−ik−i​

Mycode

map mp;
const int N = 2010,mod = 1e5+3;
int fact[N],infact[N];

int qmi(int a,int k){
	int res  = 1;
	while(k){
		if(k&1) res = 1ll*res*a%mod;
		a = 1ll*a*a%mod;
		k>>=1;
	}
	return res;
}

int C(int a,int b){
	if(a>b>>c>>d>>k;
	
	int res = 0 ;
	for(int i =0  ; i