Problem #3006 - ECNU Online Judge

5 年前

由于$k$达到了$1 \times 10^6$的量级，因此预处理打表递推不现实。

一个可行的方法是Lucas定理：
$$C_q^r \bmod p \equiv q!{(r!(q - r)!\bmod p)^{p - 2}}\bmod p$$

代码如下：

#include <string>
#include <vector>
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <sstream>
#include <queue>

using namespace std;

typedef long long ll;

const ll ceil=1000000007;
ll factors[1000001];

void genlist()
{
    for(ll i=0;i<1000001;i++){
        if(i==0)
            factors[i]=1;
        else if(i==1)
            factors[i]=1;
        else
            factors[i]=((factors[i-1]%ceil)*(i%ceil))%ceil;
    }
}

ll fastmod(ll a,ll b)
{
    ll ret=1;
    while(b){
        if(b&1)
            ret=((ret%ceil)*(a%ceil))%ceil;
        a=((a%ceil)*(a%ceil))%ceil;
        b>>=1;
    }
    return ret;
}

ll comp(ll n, ll m)
{
    ll res=factors[n]*fastmod((factors[m]*factors[n-m])%ceil,ceil-2)%ceil;
    return res;
}

int main()
{
    genlist();
    int t;
    cin>>t;

    for(int i=0;i<t;i++){
        ll a,b,k,n,m;
        cin>>a>>b>>k>>n>>m;

        ll comb=comp(k,m);
        ll coef_a=fastmod(a,n);
        ll coef_b=fastmod(b,m);
        ll res=((coef_a%ceil)*(coef_b%ceil))%ceil;
        res=((res%ceil)*(comb%ceil))%ceil;

        cout<<"case #"<<i<<":"<<endl;
        cout<<res<<endl;
    }
}

回复 10 0

10192100415

3 年，8 月前

由二项式定理知系数为$\binom{k}{m} a^n b^m$，但由于$k$的数量级是$1 \times 10^6$，组合数打表需要的空间为$O(k^2)$，超过能开的数组大小，需要另辟蹊径。此时把组合数展开：
$$
\binom{k}{m} = \frac{k!}{m!(k-m)!} = \frac{k!}{m!n!} \equiv k! (m!n!)^{-1} \pmod{p} // p = 1000000007
$$
由于$p$是素数（一般让你模的都是素数啦），由费马小定理：若$p$是素数，$a$不是$p$的倍数，则
$$
a^{p - 1} \equiv 1 \pmod{p} \Rightarrow a \cdot a^{p - 2} \equiv 1 \pmod{p}
$$
即$a$的逆元是$a ^ {p - 2}$，因此有$(m!n!)^{-1} \mod p = (m!n!)^{p - 2} \mod p$，于是得到
$$
\binom{k}{m}
\equiv k!(m!n!)^{-1}
\equiv k!(m!n!)^{p - 2} \pmod{p}
$$
$$
\text{ans} \equiv k!(m!n!)^{p - 2} a^n b^m \pmod{p}
$$
阶乘可以通过一维数组打表，至于$(m!n!)^{p - 2}, a^n, b^m$对$p$的模可以通过快速幂计算

回复 3 0

师大马桶质检员

3 年，8 月前

组合数开一维数组dp，a^m*b^n用快速幂，但还是超时了（落泪）

回复 1 0

10205101465

3 年，8 月前

回复 0 0

10192100415

3 年，8 月前

#include <iostream>
using namespace std;
using ULLONG = unsigned long long;

constexpr ULLONG P = 1000000007;
constexpr int MAX = 1000001;
ULLONG factorial[MAX];

ULLONG fast_pow(ULLONG _base, ULLONG _pow)
{
    ULLONG result = 1;
    while (_pow > 0) {
        if (_pow & 1)
            result = result * _base % P;
        _base = _base * _base % P;
        _pow >>= 1;
    }
    return result;
}

void initialize()
{
    factorial[0] = 1;
    for (int i = 1; i < MAX; ++i)
        factorial[i] = factorial[i - 1] * i % P;
}
void solve()
{
    int a, b, k, n, m;
    cin >> a >> b >> k >> n >> m;
    ULLONG inv_binom = fast_pow(factorial[n] * factorial[m] % P, P - 2);
    ULLONG apow = fast_pow(a, n);
    ULLONG bpow = fast_pow(b, m);

    ULLONG ans = factorial[k] * inv_binom % P;
    ans = ans * apow % P;
    ans = ans * bpow % P;
    cout << ans << endl;
}

int main()
{
#ifndef ONLINE_JUDGE
#pragma warning(push)
#pragma warning(disable: 6031)
    freopen("D:\\input.txt", "r", stdin);
#pragma warning(pop)
#endif
    initialize();
#ifndef SINGLE_CASE
    int T;
    cin >> T;
    cin.get();
    for (int t = 0; t < T; ++t) {
        cout << "case #" << t << ':' << endl;
        solve();
    }
#else
    solve();
#endif
    return 0;
}

回复 0 0

3006. 计算多项式的系数 II

服务

开源

关于我们