车的放置

一本通·提高篇 · 代码 · cpp · 难度 4/5 · 共 2035 字
在一个Γ形棋盘上放k个互不攻击的车的方案数，
一本通
练习
正文

/*
原题：T1654「一本通 6.6 练习 3」车的放置
题意：在一个 Γ 形棋盘上放 k 个互不攻击的车（不同行不同列）的方案数，模 100003。
棋盘形状：共 a+c 行，其中 a 行有 b+d 列，其余 c 行只有 d 列（左侧对齐）。
思路：枚举在"窄行"（c 行 × d 列）里放 s 个车：选行列并配对是 C(c,s)·C(d,s)·s!。
窄行占用了 s 列后，宽行还剩 b+d-s 列可用，于是宽行再放 k-s 个车有
C(a,k-s)·C(b+d-s,k-s)·(k-s)! 种。对 s 求和即为答案。
复杂度：时间 O(k)，空间 O(1)（组合数用 Lucas，模数 100003 为素数）
易错点：1) 两步不是独立的：宽行可用列数要减去窄行已占用的 s 列；
2) C(b+d-s, k-s) 在区间过窄时为 0，组合数函数里要判 m>n；
3) 模数是 100003 而不是常见的 1e5+7。
*/
#include <bits/stdc++.h>
using namespace std;
const long long MOD=100003;
long long qpow(long long a,long long n){
    long long r=1;
    a%=MOD;
    while(n>0){
        if(n&1){
            r=r*a%MOD;
        }
        a=a*a%MOD;
        n>>=1;
    }
    return r;
}
vector<long long> fact,ifact;
long long maxFact=-1;
void ensure(long long upto){
    if(upto<=maxFact){
        return;
    }
    long long old=maxFact+1;
    fact.resize(upto+1);
    ifact.resize(upto+1);
    if(old==0){
        fact[0]=1;
        old=1;
    }
    for(long long i=old;i<=upto;i++){
        fact[i]=fact[i-1]*i%MOD;
    }
    ifact[upto]=qpow(fact[upto],MOD-2);
    for(long long i=upto-1;i>=old-1;i--){
        ifact[i]=ifact[i+1]*(i+1)%MOD;
    }
    maxFact=upto;
}
long long combSmall(long long n,long long m){
    if(m<0 || m>n){
        return 0;
    }
    return fact[n]*ifact[m]%MOD*ifact[n-m]%MOD;
}
long long lucas(long long n,long long m){
    if(m<0 || m>n){
        return 0;
    }
    long long lim=max(n,MOD-1);
    ensure(min(lim,MOD-1));
    long long res=1;
    while(n>0 || m>0){
        res=res*combSmall(n%MOD,m%MOD)%MOD;
        n/=MOD;
        m/=MOD;
    }
    return res;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    long long a,b,c,d;
    int k;
    cin>>a>>b>>c>>d>>k;
    ensure(0);
    // 保证阶乘表至少覆盖到 k 以内
    ensure(k);
    long long ans=0;
    for(int s=0;s<=k;s++){
        long long narrow=lucas(c,s)*lucas(d,s)%MOD*fact[s]%MOD;
        long long wide=lucas(a,k-s)*lucas(b+d-s,k-s)%MOD*fact[k-s]%MOD;
        ans=(ans+narrow*wide)%MOD;
    }
    cout<<ans<<"\n";
    return 0;
}
车的放置

正文

一本通·提高篇的其它内容
