Atcoder | 316 高橋君、24歳 | 数论 | 组合计数 / 容斥原理


Description

高桥君, 24 岁,是个学生,过生日辣!
他要给他的 $N$ 个朋友们发请帖,但是手贱发错了 $K$ 个人的请帖。
他现在十分橘促,问他的朋友们拿到的请帖组合一共有多少种可能。


Input Format

一行,输入 $N,K$。


Output Format

一行,输出答案 mod 1,777,777,777 的值。


Input Sample

Sample 01

3 2

Sample 02

5 3

Sample 03

4 4

Sample 04

8 4

Sample 05

777 77


Output Sample

Sample 01

3

Sample 02

20

Sample 03

9

Sample 04

630

Sample 05

1084428318


Data Range

$2 \le N \le 777777777777777777$,$2 \le K \le 777777$。


Solution

假设正确的请帖为升序的排列 $1 \dots N$。

那么考虑在序列中选择 $N-K$ 个位置放正确的请帖,共有 $\binom{N}{N-K}$ 种放法,即 $\frac{N!}{K!(N-K!)}$。可以线性算出 $\frac{N!}{(N-K)!}$ ,复杂度为 $\Theta(K)$。

接下来可以把剩下的 $K$ 个位置拿出来视为一个独立的排列,考虑计算它的完全错排数量。根据容斥原理,完全错排数 = 全排列 – 有 1 个位置放对的排列 + 有 2 个位置放对的排列 … 依此类推。有 $x$ 个位置放对的放置方案有 $\binom{K}{x}$ 种,其他的位置可以是一个长度为 $K-x$ 的全排列,故可以化出长度为 $K$ 的完全错排数为 $\sum_{x=0}^{K}(K-x)! \times \binom{K}{x} \times (-1)^x \Rightarrow \sum_{x=0}^{K} (K-x)! \times \frac{K!}{x!(K-x)!} \times(-1)^x \Rightarrow \sum_{x=0}^{K} (-1)^x \prod_{i=x+1}^{K} i$。可以从 $K$ 到 $1$ 倒序算一遍阶乘在 $\Theta(K)$ 之内得到。

最后,将 $\frac{N!}{(N-K)!}$ 与错排数相乘,再乘上 $K!$ 在 mod 1777777777 意义下的逆元(费马小定理,快速幂)即为答案。


Code

#include<cstdio>
#include<cstdlib>
#include<cstring>

#define min(x,y) ((x)<(y)?(x):(y))
#define max(x,y) ((x)>(y)?(x):(y))
#define swap(x,y) {int t=x; x=y,y=t;}
#define wipe(x,y) memset(x,y,sizeof(x))
#define dbgIn(x) freopen(x".in","r+",stdin)
#define rep(x,y,z) for(int x=y,I=z;x<=I;++x)
#define dbgOut(x) freopen(x".out","w+",stdout)
#define file(x) freopen(x".in","r+",stdin); freopen(x".out","w+",stdout)

#define mod 1777777777

typedef long long ll;

inline void Read(int &x){
    x=0; char ch=0; while(ch<'0'||ch>'9') ch=getchar();
    while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar(); return;
}

ll N;
ll K;
ll ans;

ll fact[1000005];

ll qkpow(ll tp,int up){
    if(up==1) return tp;
    ll ret=qkpow(tp,up>>1);
    if(up&1) return ret*ret%mod*tp%mod;
    return ret*ret%mod;
}

int main(){
    scanf("%lld%lld",&N,&K);
    fact[K+1]=1;
    for(ll i=K;i>=1;i--)
        fact[i]=fact[i+1]*i%mod;
    rep(i,1,K+1)
        ans=(ans+fact[i]*(i&1?1:-1))%mod;
    ans=(ans%mod+mod)%mod;
    for(ll s=N-K+1;s<=N;s++)
        ans=ans*(s%mod)%mod;
    ans=ans*qkpow(fact[1],1777777775)%mod;
    printf("%lld\n",ans);
    return 0;
}