BZOJ3907 網格

題目：BZOJ3907: 網格

思路：

顯然，這道題是卡特蘭數經典模型的變式。

假設不考慮越界限制，從(0,0)到(n,m)的總方案數為\(C_{n+m}^n\)，如果能計算出其中有哪些是不合法的，二者相減即可。

我們可以用一個1和-1的串記錄行走的路徑，記向右走為+1，向上走為-1，則一條合法路徑滿足串中任意位置的字首和均不小于0。串長為n+m，其中有n個1，m個-1，是以串的總數有\(C_{n+m}^n\)種

對于一條不合法路徑，我們找到第一個字首和小于0的位置pos，把串從1到pos位置翻轉（1->-1，-1->1），那麼最後串長不變，pos位之後的串不變，1~pos位中1的個數多了1，-1的個數少了1，最後總串長不變。是以每個不合法方案均能唯一映射到這種串，不合法方案總數：\(C_{n+m}^{n+1}\)。

幾何意義：在網格圖中，對于不合法的方案，一定經過直線y=x+1。把起點到第一個觸碰到直線y=x+1的點之間走過的路徑沿y=x+1對稱，第一次觸碰之後的路徑不變。是以每條不合法方案都對應一條從(-1,1)到(n,m)的路徑。

最後答案為：\(C_{n+m}^n-C_{n+m}^{n+1}\)。

注意到沒有模數，是以需要高精度。組合數計算時需要用到除法，直接寫高精除高精效率比較低，隻能得60pts。可以對分子分母同時分解質因數之後計算，省去除法。

Code：

#include <bits/stdc++.h>
using namespace std;
const int N=10000,base=10000,power=4;
int n,m,cnt[N],mindiv[N],p[N],tot;
struct bigint{
    int d[N],len;
    inline void clean() {while(len>1&&!d[len]) --len;} 
    inline bigint(){memset(d,0,sizeof(d)),len=1;}
    inline bigint(int num) {len=1;d[1]=num;}
    bigint operator - (const bigint &b)const{
        bigint c=*this;
        for(int i=1;i<=b.len;++i){
            c.d[i]-=b.d[i];
            if(c.d[i]<0) c.d[i]+=base,--c.d[i+1];
        }
        c.clean();
        return c;
    }
    bigint operator * (const bigint &b)const{
        bigint c;
        for(int i=1;i<=len;++i) for(int j=1;j<=b.len;++j)
            c.d[i+j-1]+=d[i]*b.d[j],c.d[i+j]+=c.d[i+j-1]/base,c.d[i+j-1]%=base;
        c.len=len+b.len;
        c.clean();
        return c;	
    }
    void print(){
        clean();
        printf("%d",d[len]);
        for(int i=len-1;i>=1;--i) printf("%0*d",power,d[i]);
    }
};
void Prime(){
	for(int i=2;i<=n+m;++i){
		if(!mindiv[i]) mindiv[i]=p[++tot]=i;
		for(int j=1;j<=tot;++j){
			if(i*p[j]>m+n||p[j]>mindiv[i]) break;
			mindiv[i*p[j]]=p[j];
		}
	}
}
void add(int num){
	while(num^1){
		++cnt[mindiv[num]];
		num/=mindiv[num];
	}
}
void del(int num){
	while(num^1){
		--cnt[mindiv[num]];
		num/=mindiv[num];
	}
}
bigint quickpow(int a,int b){
	bigint res=1,c=a;
	while(b){
		if(b&1) res=res*c;
		c=c*c;
		b>>=1;
	}
	return res;
}
bigint C(int n,int m){
	bigint ans=1;
	for(int i=1;i<=tot;++i) cnt[p[i]]=0;
	for(int i=n-m+1;i<=n;++i) add(i);
	for(int i=1;i<=m;++i) del(i);
	for(int i=1;i<=tot;++i) ans=ans*quickpow(p[i],cnt[p[i]]);
	return ans;
}
int main(){
	scanf("%d%d",&n,&m);
	Prime();
	(C(n+m,m)-C(n+m,m-1)).print();
	return 0;
}