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

1 #include
      
        2 #include
       
         3 #define N (1000009) 4 using namespace std; 5  6 int n,m,cnt,prime[N],Keg[N],d[N]; 7  8 struct bign 9 {10     int a[55];11     bign operator * (const int &b) const12     {13         bign c;14         for (int i=1; i<=50; ++i) c.a[i]=0;15         for (int i=1; i<=50; ++i)16         {17             c.a[i]+=a[i]*b;18             c.a[i+1]+=c.a[i]/10;19             c.a[i]%=10;20         }21         return c;22     }23 }ans;24 25 void Euler()26 {27     for (int i=2; i<=n; ++i)28     {29         if (!d[i]){d[i]=i; prime[++cnt]=i;}30         for (int j=1; j<=cnt && i*prime[j]<=n; ++j)31         {32             d[i*prime[j]]=prime[j];33             if (i%prime[j]==0) break;34         }35     }36 }37 38 void Divide(int x,int opt)39 {40     while (x!=1) Keg[d[x]]+=opt, x/=d[x];41 }42 43 int main()44 {45     scanf("%d%d",&n,&m);46     if (n
        
         =1; --i)59         printf("%d",ans.a[i]);60 }