网格

一本通·提高篇 · 代码 · cpp · 难度 4/5 · 共 2756 字
从走到，每步向右或向上，且途经点都要满足x≥
一本通
练习
正文

/*
原题：T1660「一本通 6.6 练习 9」网格
题意：从 (0,0) 走到 (n,m)（n≥m），每步向右或向上，且途经点都要满足 x≥y，求走法数。
思路：这是经典的 ballot 问题。不受限的走法共 C(n+m,m) 种，
其中越界（某处 y>x）的走法与"从 (-1,1) 出发的走法"一一对应（反射法），
数量为 C(n+m, m-1)，故答案为 C(n+m,m) - C(n+m,m-1)。
结果可能很大，用高精度整数输出。
复杂度：时间 O(m·精度位数)，空间 O(精度位数)
易错点：1) 反射法对应的非法路径数是 C(n+m, m-1) 而不是 C(n+m, m+1)；
2) m=0 时 C(n+m,m-1) 为 0，组合数函数要能正确处理 m-1<0；
3) 数值超出 64 位，必须用高精度保存。
*/
#include <bits/stdc++.h>
using namespace std;
const int BASE=10000;
struct Big{
    vector<int> d;
    Big(long long v=0){
        if(v==0){
            d.push_back(0);
        }else{
            while(v>0){
                d.push_back(v%BASE);
                v/=BASE;
            }
        }
    }
    void trim(){
        while(d.size()>1 && d.back()==0){
            d.pop_back();
        }
    }
};
Big mulSmall(const Big& x,long long m){
    Big r;
    size_t n=x.d.size()+40;
    vector<long long> tmp(n,0);
    for(size_t i=0;i<x.d.size();i++){
        long long cur=(long long)x.d[i]*m;
        size_t j=i;
        while(cur>0 && j<n){
            tmp[j]+=cur%BASE;
            cur/=BASE;
            j++;
        }
    }
    r.d.assign(n+2,0);
    long long carry=0;
    for(size_t i=0;i<n+2;i++){
        long long cur=(i<n?tmp[i]:0)+carry;
        r.d[i]=cur%BASE;
        carry=cur/BASE;
    }
    while(carry>0){
        r.d.push_back(carry%BASE);
        carry/=BASE;
    }
    r.trim();
    return r;
}
Big divSmall(const Big& x,long long m){
    Big r;
    r.d.assign(x.d.size(),0);
    long long rem=0;
    for(size_t i=x.d.size();i-- >0;){
        long long cur=rem*BASE+x.d[i];
        r.d[i]=cur/m;
        rem=cur%m;
    }
    r.trim();
    return r;
}
Big comb(long long n,long long k){
    if(k<0 || k>n){
        return Big(0);
    }
    if(k==0){
        return Big(1);
    }
    if(k>n-k){
        k=n-k;
    }
    Big res(1);
    for(long long i=1;i<=k;i++){
        res=mulSmall(res,n-k+i);
        res=divSmall(res,i);
    }
    return res;
}
Big subBig(const Big& x,const Big& y){
    Big r;
    r.d.assign(x.d.size(),0);
    for(size_t i=0;i<x.d.size();i++){
        r.d[i]=x.d[i];
    }
    for(size_t i=0;i<y.d.size();i++){
        r.d[i]-=y.d[i];
    }
    long long borrow=0;
    for(size_t i=0;i<r.d.size();i++){
        long long cur=(long long)r.d[i]-borrow;
        if(cur<0){
            cur+=BASE;
            borrow=1;
        }else{
            borrow=0;
        }
        r.d[i]=cur;
    }
    r.trim();
    return r;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    long long n,m;
    cin>>n>>m;
    Big a=comb(n+m,m);
    Big b=comb(n+m,m-1);
    Big ans=subBig(a,b);
    cout<<ans.d.back();
    for(int i=(int)ans.d.size()-2;i>=0;i--){
        cout<<setw(4)<<setfill('0')<<ans.d[i];
    }
    cout<<"\n";
    return 0;
}
网格

正文

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