洛谷P1999 高维正方体

zrzring 2020-04-11 PM 213℃ 0条

求n维下m维的数量:

$$ ans=C_n^m\times 2^{n-m} $$

因为这是我学OI以来写的的第一篇题解,原文中这里的解释实在太超模了,我不太想拿出来放到博客里

#include <iostream>
#include <cstdio>
#include <cmath>
typedef long long ll;
ll ans,a,b,inv[10000001];
const ll MOD=1000000007;
using namespace std;
int q_pow(ll a,ll b){
    ll an=1;
    while (b>0){
        if (b&1)an*=a,an%=MOD;
        a*=a;a%=MOD;
        b>>=1;
    }
    return an;
}
int main(){
    cin>>a>>b;
    if(a<b){
        printf("0");
        return 0;    
    }
    ans=q_pow(2,a-b);
    inv[1]=1;
    for(ll i=2;i<=100000;i++){  
        inv[i]=(MOD-(MOD/i))*inv[MOD%i]%MOD;
    }
    for(int i=1;i<=b;i++)
    {
        ans*=(a-i+1);ans%=MOD;
        ans*=inv[i];ans%=MOD;
    }
    printf("%d",ans);
} 
Title - Artist
0:00