济南学习 Day 5 T2 am

車（Rook）

【题目描述】

众所周知，車是中国象棋最厉害的棋子之一，他能吃到同一行或者同一列的其他棋子。車显然不能和車在一打起来，于是rly有借来了许多许多車在棋盘上摆了起来......

他想知道，在n*m的棋盘上摆放最多个数的車并且使它们不能相互吃到的情况下方案数有几种。但是，由于上次摆炮摆的太累了，这次他又增加了条件，对于任何一个車A，

如果有其他的車B在它上面，（車B行号小于車A），那么車A必须在車B的右边（車A的列号大于車B）。棋子都是相同的。

【输入说明】

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

【输出说明】

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

【样例输入】

2 2

【样例输出】

【数据范围】

对于20%的数据，N<=10,M<=10。

对于40%的数据，N<=40,M<=40。

对于70%的数据，N<=10000,M<=10000。

对于100%的数据，N<=1000000,M<=1000000。

我们再来科普一下：

排列组合是组合学最基本的概念。所谓排列，就是指从给定个数的元素中取出指定个数的元素进行排序。组合则是指从给定个数的元素中仅仅取出指定个数的元素，不考虑排序。排列组合的中心问题是研究给定要求的排列和组合可能出现的情况总数。排列组合与古典概率论关系密切。

C（n，m）=A（n，m）/m!=n!/（（n-m）！*m!）（假设n>=M）（从n个数字中选取m个不考虑顺序他的选择方案）

 1 #include<iostream>
 2 #include<cstring>
 3 #include<cstdio>
 4 #define N 1000010
 5 #define M 101
 6 using namespace std;
 7 int n,m,num,f[N],c[N],p[N],prime[N];
 8 int a1[M],b1[M],c1[N];
 9 struct node{
10     node()
11     {
12         memset(q,0,sizeof q );len=0;
13     }
14     int q[M],len;
15 };node ans;
16 void prepare()
17 {
18     for(int i=2;i<=n;i++)
19     {
20         if(!f[i])
21         {
22             prime[++num]=i;p[i]=num;
23             for(int j=2;i*j<=m;j++)
24               f[i*j]=1;
25         }
26     }
27 }
28 void work1(int x)
29 {
30     for(int i=1;i<=num;i++)
31     {
32         while(x%prime[i]==0) c[i]++,x/=prime[i];
33         if(!f[x]){ c[p[x]]++;break; }
34         if(x==1) break;
35     }
36 }
37 void work2(int x)
38 {
39     for(int i=1;i<=num;i++)
40     {
41         while(x%prime[i]==0) c[i]--,x%=prime[i];
42         if(!f[x]){ c[p[x]]--;break; }
43         if(x==1) break;
44     }
45 }
46 node cheng(node a,int b)
47 {
48     memset(a1,0,sizeof a1 );
49     memset(b1,0,sizeof b1 );
50     node c;
51     int len=a.len;
52     for(int i=1;i<=a.len;i++) a1[i]=a.q[len-i]+1;
53     for(int i=1;i<=len;i++)
54     {
55         b1[i]+=a1[i]*b;
56         b1[i+1]+=b1[i]/10;
57         b1[i]%=10;
58     }
59     if(b1[len+1]) len++;
60     c.len=min(50,len);
61     for(int i=1;i<=c.len;i++)
62       c.q[i]=b1[c.len-i+1];
63     return c;
64 }
65 int main()
66 {
67     scanf("%d%d",&n,&m);
68     if(n>m) swap(n,m);
69     prepare();
70     for(int i=m;i>=m-n+1;i--)
71       work1(i);
72     for(int i=1;i<=n;i++)
73       work2(i);
74     ans.len=1;ans.q[1]=1;
75     for(int i=1;i<=num;i++)
76       for(int j=1;j<=c[i];j++)
77         ans=cheng(ans,prime[i]);
78     for(int i=max(1,ans.len-49);i<=ans.len;i++)
79       printf("%d",ans.q[i]);
80     
81     
82     
83     return 0;
84 }