BZOJ4807:車(组合数学,高精度)

Description

众所周知，車是中国象棋中最厉害的一子之一，它能吃到同一行或同一列中的其他棋子。車跟車显然不能在一起打起来，于是rly一天又借来了许多许多的車在棋盘上摆了起来……他想知道，在N×M的矩形方格中摆最多个数的車使其互不吃到的情况下方案数有几种。

但是，由于上次摆炮摆得实在太累，他为了偷懒，打算增加一个条件：对于任何一个車A，如果有其他一个車B在它的上面（車B行号小于車A），那么車A必须在車B的右边（車A列号大于車B）。棋子都是相同的。

Input

一行，两个正整数N和M。

N<=1000000，M<=1000000

Output

一行，输出方案数的末尾50位（不足则直接输出）。

Sample Input

2 2

Sample Output

1

Solution

用我的生日对BZOJ总题数取模然后找到了这个题……

显然答案就是$C(max(n,m),min(n,m))$。用欧拉筛加速质因数分解就可以了。

一开始没算复杂度裸上了一个高精然后T成狗……

Code

 #include<iostream>

 #include<cstdio>

 #define N (1000009)

 using namespace std;

 int n,m,cnt,prime[N],Keg[N],d[N];

 struct bign

 {

     int a[];

     bign operator * (const int &b) const

     {

         bign c;

         for (int i=; i<=; ++i) c.a[i]=;

         for (int i=; i<=; ++i)

         {

             c.a[i]+=a[i]*b;

             c.a[i+]+=c.a[i]/;

             c.a[i]%=;

         }

         return c;

     }

 }ans;

 void Euler()

 {

     for (int i=; i<=n; ++i)

     {

         if (!d[i]){d[i]=i; prime[++cnt]=i;}

         for (int j=; j<=cnt && i*prime[j]<=n; ++j)

         {

             d[i*prime[j]]=prime[j];

             if (i%prime[j]==) break;

         }

     }

 }

 void Divide(int x,int opt)

 {

     while (x!=) Keg[d[x]]+=opt, x/=d[x];

 }

 int main()

 {

     scanf("%d%d",&n,&m);

     if (n<m) swap(n,m);

     Euler();

     for (int i=; i<=n-m; ++i) Divide(i,-);

     for (int i=m+; i<=n; ++i) Divide(i,);

     ans.a[]=;

     for(int i=;i<=n;i++)

         for(int j=;j<=Keg[i];j++)

             ans=ans*i;

     int len=;

     while (ans.a[len]==) --len;

     for (int i=len; i>=; --i)

         printf("%d",ans.a[i]);

 }