题目
Description
【问题描述】
笨笨当了很久的道路调度员，笨笨也开始想体验生活，从生活中发现数学问题，锻炼自己思维。最近《变形金刚3》，《哈利波特7》同步放映，明显是决战雌雄，已知王府井中一共有n人买了《变形金刚3》的票，m人买了《哈利波特7》的票，并且n>=m，并且电影院中现在只有两种票，每次只有一个人买，(共有n+m次)，这n+m次组成一个排列，为了保证每一个人买票时，《变形金刚3》票房都不少于《哈利波特7》，(n个买《变形金刚3》的人之间没区别，m个买《哈利波特7》的人也没区别),笨笨想着到这样的购票方案有多少种。笨笨想了好久都没想出来，所以笨笨找到了你。
【输入格式】
一行两个数n,m ( 0<=m<=n<=5000)
Input
【输入格式】
一行两个数n,m ( 0<=m<=n<=5000)
Output
【输出格式】
输出方案种数
Sample Input
1 1
Sample Output
1
Data Constraint
Hint
0<=m<=n<=5000
分析
假设将买《变形金刚3》票的人记为s 。买《哈利波特7》的人记为x,
则n个买《变形金刚3》的与m个买《哈利波特7》的人的队伍就可以用一个具有n个s和m个x的字符串，
显然这样的字符串共有C(n+m,n）个，其中不满足问题要求的串一定存在一个最靠左的位置p，
使得从第一个字符到第p个字符为止的子串中x的个数比s的个数大1.如sxsxx就是一个不满足条件的串，其中p=5。我们将从头到p为止的子串中的字
符 s换成x则得到一个具有n+1个s，m-1个x的串，可以证明这种转换是一一对应的，
即任意一个n+1个s，m-1个x的串都可以按照逆规则转换成一个不满足题目条件的串，
转换规则为在任意一个n+1个s，m-1个x中找到最靠左的p，
使得从头到p的子串中s的个数比x个数大1，将到p为止的子串中的s与x互换则得到n个s和m个x的串，
且此串一定不能满足条件，而具有n+1个s，m-1个x的串只有C(n+m,n+1）。那么ans=C(n+m,n)-C(n+m,n+1)=(n+1-m)*(m+n)!/(m!*(n+1)!)种方案可满足条件。
由于问题的规模很大，结果远远超出longint，要用高精度算法，虽然结果表达式中有分母，但实际结果一定是整数，所以不需要除法运算，具体运算 时只要求出(n+1-m)*(m+n)!/(m!*(n+1)!的质因子分解式，然后做高精度即可，而任意一个质因子r在n！中出现次数为[n/r]+[n/(r^2)]+[n/(r^3)]+...[n/(r^k)]，[]为取整。
代码
1 #include<cstdio>
2 #include<algorithm>
3 #define N 501
4 #define mod 100000000
5 using namespace std;
long long ans[N];
6 int n,m,a[
50001],b[
50001],lena,lenb,x,p,q;
7 void push(
int *a,
int x,
int &
len)
8 {
9 for(register
int j=
2;j*j<=x;j++
)
10 while(x%j==
0) x/=j,a[++len]=
j;
11 if(x!=
1) a[++len]=
x;
12 return;
13 }
14 long long ksm(
long long x,
int y)
15 {
16 long long ans=
1;
17 for(;y;y>>=
1,x*=x)
if(y&
1) ans*=
x;
18 return ans;
19 }
20 void mul(
long long x)
21 {
22 int t=
0;
23 for(register
int j=N-
1;j>
0;j--
)
24 {
25 (ans[j]*=x)+=
t;
26 if(ans[j]>=mod) t=ans[j]/
mod;
27 else t=
0;
28 ans[j]%=
mod;
29 }
30 return;
31 }
32 signed main()
33 {
34 scanf(
"%d%d",&n,&
m);
35 for(register
int i=n+m;i>m;i--
) push(a,i,lena);
36 for(register
int i=
1;i<=n;i++
) push(b,i,lenb);
37 push(a,n-m+
1,lena);push(b,n+
1,lenb);
38 sort(a+
1,a+
1+lena);sort(b+
1,b+
1+
lenb);
39 p=
1;q=
1;
40 while(q<=
lena)
41 {
42 if(a[p]==
b[q])
43 {
44 a[p]=
1;b[q]=
1;
45 p++;q++
;
46 continue;
47 }
48 if(a[p]<b[q]) p++
;
49 else q++
;
50 }
51 ans[N-
1]=
1;
52 for(register
int i=
1;i<=
lena;)
53 if(a[i]!=
1)
54 {
55 int j=
0;
56 while(a[i]==a[i+j]) j++
;
57 mul(ksm((
long long)a[i],j));
58 i+=
j;
59 }
60 else i++
;
61 int j=
1;
62 while(!ans[j]) j++
;
63 printf(
"%lld",ans[j]);
64 for(register
int i=j+
1;i<N;i++
)
65 {
66 if(ans[i]<1e7) putchar(
48);
67 if(ans[i]<1e6) putchar(
48);
68 if(ans[i]<1e5) putchar(
48);
69 if(ans[i]<1e4) putchar(
48);
70 if(ans[i]<1e3) putchar(
48);
71 if(ans[i]<1e2) putchar(
48);
72 printf(
"%lld",ans[i]);
73 }
74 }
转载于:https://www.cnblogs.com/zjzjzj/p/11178238.html
