Chosen by god

组合

一道组合数学题，链接
http://acm.fzu.edu.cn/problem.php?pid=2301

解析

题目的意思对方有两只怪物，一只血量为$m$m, 另一只血量为无穷。游戏共$n$n个回合，每个回合会随机地选择对方的一只怪物进行攻击，问在$n$n回合内打死那只血量为$m$m的概率为多大。 因为是$n$n回合，每次攻击都有两种可能性，所以总的方案数为$2^n$2n，因为怪物的血量为$m$m，所以至少需要$m$m次攻击才能打死这只怪物，那么总的可能方案为$C_{n}^{m}+C_{n}^{m+1}+\cdots+C_{n}^{n}$Cnm​+Cnm+1​+⋯+Cnn​, 因为$m,n\leq1000$m,n≤1000,所以预处理下阶乘和组合数就行了

AC代码

/*
 小学生一发的刷题之路;
 今天你刷题了吗？？？
 
*/

#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <algorithm>
#include <queue>
#include <cmath>
#include <set>
#include <map>
#include <deque>
#include <stack>
#include <vector>
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const double PI=acos(-1.0);
const int maxn=1e3+5;
const ll mod=1e9+7;
ll A[maxn],Amo[maxn],C[maxn][maxn],sum[maxn][maxn];
ll B[maxn];
ll poww(ll a,ll b){
    ll ans=1,base=a;
    while(b){
        if(b&1){
            ans*=base;
            ans%=mod;
        }
        b>>=1;
        base*=base;
        base%=mod;
    }
    return ans;
}

void init(){
    A[0]=1;     //计算阶乘;
    Amo[0]=1;
    for(int i=1;i<=1000;i++){
        A[i]=i*A[i-1];
        A[i]%=mod;
        Amo[i]=poww(A[i],mod-2);
    }
    
    memset(sum,0,sizeof(sum));
    for(int i=1;i<=1000;i++){
        for(int j=0;j<=i;j++){
            if(j==0){
                C[i][j]=1;
            }else{
                C[i][j]=((A[i]*Amo[j])%mod*Amo[i-j])%mod;
            }
            if(j==0){
                sum[i][j]=C[i][j];
            }else{
                sum[i][j]=sum[i][j-1]+C[i][j];
                sum[i][j]%=mod;
            }
        }
    }
    
    B[0]=1;     //计算2的阶乘;
    for(int i=1;i<=1000;i++){
        B[i]=B[i-1]*2;
        B[i]%=mod;
    }
    for(int i=1;i<=1000;i++){       //计算模逆;
        B[i]=poww(B[i],mod-2);
    }
}

int main(){
    init();     //预处理阶乘;
    int t,n,m;
    scanf("%d",&t);
    while(t--){
        scanf("%d %d",&n,&m);
        ll ans=(sum[n][n]-sum[n][m]+C[n][m]+mod)%mod;
        ans=(ans*B[n])%mod;
        printf("%lld\n",ans);
    }
    return 0;
}

新的开始，每天都要快乐哈!