【HDU 4451 Dressing】水题，组合数

有衣服、裤子、鞋数量分别为n,m,k，给出p对不和谐的衣-裤或裤-鞋搭配，问一共有多少种和谐的衣裤鞋的搭配。

全部的组合有C_n¹C_m¹C_k¹种。

设p对中有p1对衣-裤，p2对裤-鞋，则不和谐的搭配共有p1*C_k¹+p2*C_n¹种，但有被重复计算两次的搭配共p3对，它们引用了同一裤。设裤 i 在p1被引用 li 次，在p2被引用 ri 次，则p3=∑(1*C_li¹C_ri¹)。所以答案为n*m*k-p1*k-p2*n+p3

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <set>
 4 using namespace std;
 5
 6 int n,m,k;
 7 typedef pair<int,int> P;
 8 P pants[1005];//i号pant被p1引用first次,被p2引用second次
 9 int p,p1,p2,p3;
10 int ans;
11
12 int main()
13 {
14     freopen("4451.txt","r",stdin);
15     while(scanf("%d%d%d",&n,&m,&k)!=EOF)
16     {
17         if(n==0&&m==0&&k==0) break;
18         ans=n*m*k;
19         memset(pants,0,sizeof(pants));
20         p1=p2=p3=0;
21         scanf("%d",&p);
22         char s1[10],s2[10];
23         int n1,n2;
24         for(int i=0;i<p;i++)
25         {
26             scanf("%s",s1);
27             scanf("%d",&n1);
28             scanf("%s",s2);
29             scanf("%d",&n2);
30             if(s1[0]=='c')
31             {
32                 p1++;
33                 pants[n2].first++;
34             }else if(s1[0]=='p')
35             {
36                 p2++;
37                 pants[n1].second++;
38             }
39         }
40         for(int i=1;i<=m;i++)
41         {
42             p3+=pants[i].first*pants[i].second;
43         }
44         ans-=p1*k+p2*n-p3;
45         printf("%d\n",ans);
46     }
47     return 0;
48 }