影视网站wordpress/如何做公司网站推广

链接：https://ac.nowcoder.com/acm/contest/30825/B

题目描述
一个箱子里有n个黑球，m个白球，小王想要连续q次从箱子里随机的取出k个球（每次取出k个后立即放回），连续q次取球k个都为黑球的概率是多少，结果对1e9+7取模。

输入描述:
第一行给出一个t，代表t组测试数据。（1<=t<=100000）

每组测试数据给出n，m，k，q。（1<=n,m,k<=1e5，k<=n+m，1<=q<=1e12）

输出描述:
对于每组测试数据输出一个结果代表概率。

示例1
输入

2
2 2 1 2
3 3 2 1

输出

250000002
400000003

说明
第一个样例结果为1/4,取模为1*4^(mod-2)%mod=250000002。

前置知识

一、快速求组合数（非必要，可以跳过）

需要用到乘法逆元、费马小定理

ll qpow(ll a,ll b,ll mod){//快速幂ll ans=1,base=a;while(b){if(b&1) ans=ans*base%mod;base=base*base%mod;b>>=1;}return ans;
}ll C(ll n,ll m,ll p){//求组合数if(n<m) return 0;if(m>n-m) m=n-m;ll a=1,b=1;FOR(i,0,m-1){a=(a*(n-i))%p;b=(b*(i+1))%p;}return a*qpow(b,p-2,p)%p;//乘法逆元
}

二、乘法逆元

定义：如果一个线性同余方程 $ax\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}p)$，则 $x$ 称为 $a\mathrm{m}\mathrm{o}\mathrm{d}p$ 的逆元，记作 $a^{-1}$。

下面给出一种求法：（ $p$ 必须是素数）

因为 $ax\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}p)$；
所以 $ax\equiv a^{p-1}(\mathrm{m}\mathrm{o}\mathrm{d}p)$（费马小定理）；
所以 $x\equiv a^{p-2}(\mathrm{m}\mathrm{o}\mathrm{d}p)$。

于是可以用快速幂来求。

a_reverse=qpow(a,p-2,p);

思路

通过加乘原理可以推算出答案：
$$ans={[\frac{n!(n+m-k)!}{(n-k)!(n+m)!}]}^q$$
或通过排列组合知识推算出：
$$ans={[\frac{{\mathrm{C}}_k^n}{{\mathrm{C}}_k^{n+m}}]}^q$$
第一种答案可以通过第二种答案化简得出。

分母转换成逆元，与分子相乘，再一起快速幂即可。

但是这道题不能直接算组合数，会超时。

TLE 代码

#include<bits/stdc++.h>
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
using namespace std;
#define ll long longconst int mod=1e9+7;ll qpow(ll a,ll b,ll mod){//a^bll ans=1,base=a;while(b){if(b&1) ans=ans*base%mod;base=base*base%mod;b>>=1;}return ans;
}ll C(ll n,ll m,ll p){if(n<m) return 0;if(m>n-m) m=n-m;ll a=1,b=1;FOR(i,0,m-1){a=(a*(n-i))%p;b=(b*(i+1))%p;}return a*qpow(b,p-2,p)%p;
}int main(){cin.tie(0)->sync_with_stdio(0);int T;cin>>T;while(T--){ll n,m,k,q;cin>>n>>m>>k>>q;ll A=C(n,k,mod);ll B=C(n+m,k,mod);B=qpow(B,mod-2,mod);ll ans=qpow(A*B%mod,q,mod);cout<<ans<<'\n';}return 0;
}

应该预处理阶乘数组，由于模数不大，不用高精度

由于 1<=n,m,k<=1e5, k<=n+m ，数组开 2e5 大小即可

AC 代码

#include<bits/stdc++.h>
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
using namespace std;
#define ll long longconst int mod=1e9+7;
const int maxn=2e5+7;ll fa[maxn];ll qpow(ll a,ll b,ll mod){//a^bll ans=1,base=a;while(b){if(b&1) ans=ans*base%mod;base=base*base%mod;b>>=1;}return ans;
}void init(){fa[0]=fa[1]=1;//f[0]也要赋值FOR(i,2,maxn-1)fa[i]=fa[i-1]*i%mod;
}int main(){cin.tie(0)->sync_with_stdio(0);init();int T;cin>>T;while(T--){ll n,m,k,q;cin>>n>>m>>k>>q;if(n-k<0){cout<<"0\n";continue;}ll A=fa[n]*fa[n+m-k]%mod;ll B=fa[n-k]*fa[n+m]%mod;B=qpow(B,mod-2,mod);//B转换为逆元ll ans=qpow(A*B%mod,q,mod);cout<<ans<<'\n';}return 0;
}