Blog

Lucas定理

Lucas Theorem

Posted by BY on June 17, 2019

前言

新的一年，好好学习。

正文

问题来源

本问题来自看到某高中生的算法博客。

问题描述

在n维空间中，一个单位立方体由2^n个点组成。
他们的坐标形如(x1,x2，…,xn),{其中xi属于0或1}。
定义n维空间中的两个点距离为其曼哈顿距离，点p(p1,p2,…pn)和q(q1,q2,…,qn)的距离为|p1-q1|+|p2-q2|+…+|pn-qn|。
现在给你单位立方体上的一点p以及一个整数k，请问你点p距离为k的单位立方体上点的数量。因为这样的点可能很多，所以请对10^9+7取模。原文地址

分析：

经过分析可知，在n维空间中选取k个维度的分距离为1，剩下的维度的分距离为0。这和n个互不相同的球取k个的取法总数是一样的。
所以答案就是C(n,k)
但是如何用算法去求？

当n,m都很小

当n,m都很小的时候可以利用杨辉三角直接求。 C(n,m)=C(n-1,m)+C(n-1,m-1)；

n和m较大，并且p为素数的时候

Lucas定理是用来求 c(n,m) mod p，p为素数的值。

C(n,m)%p=C(n/p,m/p)*C(n%p,m%p)%p   
也就是Lucas(n,m)%p=Lucas(n/p,m/p)*C(n%p,m%p)%p
求上式的时候，Lucas递归出口为m=0时返回1

求C(n%p, m%p)%p的时候，此处写成C(n, m)%p(p是素数，n和m均小于p)

C(n, m)%p = n! / (m ! * (n - m )!) % p = n! * mod_inverse[m! * (n - m)!, p] % p

由于p是素数，有费马小定理可知，m! * (n - m)! 关于p的逆元就是m! * (n - m)!的p-2次方。

p较小的时候预处理出1-p内所有阶乘%p的值，然后用快速幂求出逆元，就可以求出解。p较大的时候只能逐项求出分母和分子模上p的值，然后通过快速幂求逆元求解。

P较大，不打表：

ll pow(ll a, ll b, ll m)
{
    ll ans = 1;
    a %= m;
    while(b)
    {
        if(b & 1)ans = (ans % m) * (a % m) % m;
        b /= 2;
        a = (a % m) * (a % m) % m;
    }
    ans %= m;
    return ans;
}
ll inv(ll x, ll p)//x关于p的逆元，p为素数
{
    return pow(x, p - 2, p);
}
ll C(ll n, ll m, ll p)//组合数C(n, m) % p
{
    if(m > n)return 0;
    ll up = 1, down = 1;//分子分母;
    for(int i = n - m + 1; i <= n; i++)up = up * i % p;
    for(int i = 1; i <= m; i++)down = down * i % p;
    return up * inv(down, p) % p;
}
ll Lucas(ll n, ll m, ll p)
{
    if(m == 0)return 1;
    return C(n % p, m % p, p) * Lucas(n / p, m / p, p) % p;
}

P较小，打表：

const int maxn = 1e5 + 10;
ll fac[maxn];//阶乘打表
void init(ll p)//此处的p应该小于1e5，这样Lucas定理才适用
{
    fac[0] = 1;
    for(int i = 1; i <= p; i++)
        fac[i] = fac[i - 1] * i % p;
}
ll pow(ll a, ll b, ll m)
{
    ll ans = 1;
    a %= m;
    while(b)
    {
        if(b & 1)ans = (ans % m) * (a % m) % m;
        b /= 2;
        a = (a % m) * (a % m) % m;
    }
    ans %= m;
    return ans;
}
ll inv(ll x, ll p)//x关于p的逆元，p为素数
{
    return pow(x, p - 2, p);
}
ll C(ll n, ll m, ll p)//组合数C(n, m) % p
{
    if(m > n)return 0;
    return fac[n] * inv(fac[m] * fac[n - m], p) % p;
}
ll Lucas(ll n, ll m, ll p)
{
    if(m == 0)return 1;
    return C(n % p, m % p, p) * Lucas(n / p, m / p, p) % p;
}

回到这个道题，原作者给出的答案是：

#include<cstdio>
#include<iostream>

using namespace std;

const int mod=1e9+7;

void read(int &x)
{
    x=0; char c=getchar();
    while(!isdigit(c)) c=getchar();
    while(isdigit(c)) { x=x*10+c-'0'; c=getchar(); }
}

int Pow(int a,int b)
{
    int res=1;
    for(;b;a=1LL*a*a%mod,b>>=1)
        if(b&1) res=1LL*res*a%mod;
    return res;
}

int main()
{
        freopen("cube.in","r",stdin);
    freopen("cube.out","w",stdout);
    int n,k;
    read(n); read(k);
    int ans=1;
    for(int i=1;i<=k;i++) 
        ans=1LL*ans*Pow(i,mod-2)%mod*(n-i+1)%mod;
    cout<<ans;
}

原作者并没有用Lucas定理，仅用了费马小定理。

总结：

勤思考。

结语

不管怎么样好好加油。

CATALOG
    FEATURED TAGS
    Blog