Uva11538 排列组合水题

画个图就很容易推出公式：

设mn=min(m,n)，mx=max(m,n)

对角线上：

横向：m*C(n,2)

纵向：n*C(m,2)

因为所有的C函数都是只拿了两个，所以可以优化下。不过不优化也过了= =

 1 #include <iostream>
 2 using namespace std;
 3 #define LL long long
 4 int n,m;
 5 
 6 LL P(long n,long m)
 7 {
 8   long p=1;
 9   while(m!=0)
10   {
11     p*=n;
12     n--;
13     m--;
14   }
15   return p;
16 }
17 
18 LL C(long n,long m)
19 {
20   long i,c=1;
21   i=m;
22   while(i!=0)
23   {
24     c*=n;
25     n--;
26     i--;
27   }
28   while(m!=0)
29   {
30     c/=m;
31     m--;
32   }
33   return c;
34 }
35 
36 
37 int main()
38 {
39     while (cin>>n>>m)
40     {
41         if ((n==0)&&(m==0))     break;
42         int mn=min(n,m),mx=max(n,m);
43         LL sum=0;
44         for (int i=2;i<=mn;i++)
45             sum+=C(i,2);
46         if (mx>2) sum=sum*2;
47         if (mx-mn-1>0) sum+=(mx-mn-1)*C(mn,2);
48         sum=sum*2;
49 
50         sum+=m*C(n,2)+n*C(m,2);
51 
52         sum=sum*2;
53         cout<<sum<<endl;
54     }
55     return 0;
56 }

View Code