6.27 冲刺国赛模拟 25
T1 简单计数
不是古典概型所以不能方案数相除。
考虑枚举第一个选择的位置 \(i\)，这样分成两个独立的区间，只关心 \(k\) 所在的一个，转移方程：
\[f_{n,k}=\dfrac{1}{n-1}\left([k<n]+[k>1]+\sum_{i>k}f_{i-1,k}+\sum_{i<k-1}f_{n-(i+1),k-(i+1)}\right) \]前缀和优化可以做到 \(O(T+n^2)\)。
注意到 \(k\) 的限制可以看作两个区间拼起来，具体是 \([1,k]\) 和 \([k,n]\)，\(k\) 没有被选择的概率就是在两个中都没有被选择的概率乘积，这两个事件显然独立。
再注意到此时 \(k\) 就是边界位置了，而 \(f_{n,1}=f_{n,n}\) 所以只需要求出 \(f_{i,1}\) 就行了，答案就是 \(f_{n,k}=1-(1-f_{k,1})(1-f_{n-k+1,1})\)，复杂度 \(O(T+n)\)。
点击查看代码
inline int q_pow(int A,int B,int P){
int res=1;
while(B){
if(B&1) res=1ll*res*A%P;
A=1ll*A*A%P;
B>>=1;
}
return res;
}
int t;
int n,k;
int inv[maxn];
int f[maxn],g[maxn];
int main(){
freopen("count.in","r",stdin);
freopen("count.out","w",stdout);
inv[1]=1;
for(int i=2;i<=lim;++i) inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;
f[1]=0,f[2]=1;
int sum=0;
for(int i=3;i<=lim;++i){
sum=(sum+f[i-2])%mod;
f[i]=1ll*inv[i-1]*(1+sum)%mod;
}
t=read();
while(t--){
int n=read(),k=read();
printf("%lld\n",(1ll-1ll*(1-f[k]+mod)*(1-f[n-k+1]+mod)%mod+mod)%mod);
}
return 0;
}