牛客推组合数公式(树，小G的排列-加强版)

树

思路：

线性逆元知识($O\left(n\log n\right)\to O\left(n\right)$)：

有公式：
$$inv\left[x\right]\equiv \left(mod-\lfloor \frac{mod}{x}\rfloor \right)\ast inv\left[mod\%x\right]\%mod$$
（推导过程可看逆元详解）

这就意味着我们以一种DP的思路从小到大更新inv数组，可以以O(n)的复杂度更新出来

typedef long long LL;
inv[1]=1;
for(int i=2;i<=n;i++)
    inv[i]=((LL)(MOD-MOD/i)*inv[MOD%i])%MOD;

小技巧：

inv[2]=(mod+1)/2=mod-mod/2;

代码：

#include <iostream>
#include <cstdio>
#define ll long long
using namespace std;
const ll mod=1e9+7;
const ll maxn=310;
ll n,k,ans,inv[maxn],f[maxn];
ll C(ll x,ll y){
    return f[x]*inv[y]%mod*inv[x-y]%mod;
}
ll A(ll x,ll y){
    return f[x]*inv[x-y]%mod;
}
int main(){
    ios::sync_with_stdio(false);
    cin>>n>>k;
    inv[0]=f[0]=inv[1]=f[1]=1;
    for(ll i=2;i<maxn;i++)
        inv[i]=((mod-mod/i)*inv[mod%i])%mod,f[i]=i;
    for(ll i=2;i<maxn;i++)
        inv[i]=(inv[i]*inv[i-1])%mod,f[i]=(f[i]*f[i-1])%mod;
    for(ll i=1;i<=k&&i<=n;i++)
        ans=(ans+(C(n-1,i-1)*A(k,i)%mod))%mod;
    cout<<ans;
    return 0;
}

小G的排列-加强版

思路：

代码：

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
typedef long long ll;
const int N=10000005,mod=1e9+7;
ll f[N];
int n,m;
ll sol(int n,int m){
    if(m>n) return 0;
    return (n-m+1)*f[n-m+1]%mod*(m>1?2:1)%mod;
}
int main(){
    f[0]=f[1]=1;
    for(int i=2;i<N;i++) f[i]=f[i-1]*i%mod;
    int t;
    scanf("%d",&t);
    while(t--){
        scanf("%d%d",&n,&m);
        ll ans=f[n]-sol(n,m+1)+sol(n,m+2);
        ans=(ans%mod+mod)%mod;
        printf("%lld\n",ans);
    }
}