H

H - 扑克牌

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 128000/64000 KB (Java/Others)

Submit Status

Problem Description

一副不含王的扑克牌由52张牌组成，由红桃、黑桃、梅花、方块4组牌组成，每组13张不同的面值。现在给定52张牌中的若干张，请计算将它们排成一列，相邻的牌面值不同的方案数。

牌的表示方法为XY，其中X为面值，为2、3、4、5、6、7、8、9、T、J、Q、K、A中的一个。Y为花色，为S、H、D、C中的一个。如2S、2H、TD等。

Input

第一行为一个整数T，为数据组数。

之后每组数据占一行。这一行首先包含一个整数N，表示给定的牌的张数，接下来N个由空格分隔的字符串，每个字符串长度为2，表示一张牌。每组数据中的扑克牌各不相同。

1 ≤ T ≤ 2000

1 ≤ N ≤ 52

Output

对于每组数据输出一行，形如"Case #X: Y"。X为数据组数，从1开始。Y为可能的方案数，由于答案可能很大，请输出模264之后的值。

Sample Input

5
1 TC
2 TC TS
5 2C AD AC JC JH
4 AC KC QC JC
6 AC AD AS JC JD KD

Sample Output

Case #1: 1
Case #2: 0
Case #3: 48
Case #4: 24
Case #5: 120

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 typedef long long LL;
 4 const int N=110;
 5 const int INF=0x3f3f3f3f;
 6 const int mod=1e9+7;
 7 int cas=1,T;
 8 LL dp[14][55],C[N][N],fac[N];
 9 int a[N],n;
10 void init()
11 {
12     for(int i=0;i<N;i++)
13     {
14         C[i][0]=C[i][i]=1;
15         for(int j=1;j<i;j++) C[i][j]=C[i-1][j]+C[i-1][j-1];
16     }
17     fac[0]=1;
18     for(int i=1;i<N;i++) fac[i]=fac[i-1]*i;
19 }
20 LL Cnm(int n,int m)
21 {
22     if(m>n || n<0 || m<0) return 0;
23     return C[n][m];
24 }
25 char s[N][3];
26 int cmp(const int &a,const int &b)
27 {
28     return a>b;
29 }
30 int main()
31 {
32     //freopen("1.in","w",stdout);
33     //freopen("1.in","r",stdin);
34     //freopen("1.out","w",stdout);
35     init();
36     scanf("%d",&T);
37     while(T--)
38     {
39         scanf("%d",&n);
40         for(int i=1;i<=n;i++) scanf("%s",s[i]); 
41         memset(a,0,sizeof(a));
42         for(int i=1;i<=n;i++)
43         {
44             switch(s[i][0])
45             {
46                 case 'T':a[10]++;break;
47                 case 'J':a[11]++;break;
48                 case 'Q':a[12]++;break;
49                 case 'K':a[13]++;break;
50                 case 'A':a[1]++;break;
51                 default:a[s[i][0]-'0']++;break;
52             }
53         }
54         sort(a,a+14,cmp);
55 //        for(int i=0;a[i];i++) printf("%d %d
",i,a[i]);
56         memset(dp,0,sizeof(dp));
57         dp[0][a[0]-1]=1;
58         int sum=a[0];
59         LL ans=dp[0][0];
60         //dp第二维记录有多少个同花色相邻的
61         for(int i=1;a[i];i++)
62         {
63             for(int j=0;j<sum;j++)//多少个相邻
64             {
65                 for(int k=1;k<=a[i];k++)//a[i]分成多少部分
66                 {
67                     for(int l=0;l<=k;l++)//多少部分放到相邻的中间
68                     {
69                         LL x=j+a[i]-k-l;
70                         if(x<0) continue;
71                         dp[i][x]+=Cnm(j,l) * Cnm(sum+1-j,k-l)* Cnm(a[i]-1,k-1) * dp[i-1][j] ;
72                     }
73                 }
74             }
75             sum+=a[i];
76             ans=dp[i][0];
77         }
78         for(int i=0;a[i];i++) ans=ans*fac[a[i]];
79         printf("Case #%d: %llu
",cas++,ans);
80     }
81     //printf("time=%.3lf
",(double)clock()/CLOCKS_PER_SEC);
82     return 0;
83 }

solve.cpp

题解：

本题数据加强版：http://acm.hdu.edu.cn/showproblem.php?pid=4532.
这题是一道组合数学dp.
dp数组有两维，对于dp[i][j],i表示放到第几种花色，j记录有多少个同花色相邻的出现,dp[i][j]表示方案数.
dp时，对于a[i]个同一种花色，可以将其划分为k组（将相同的a[i]个球放到k个盒子,盒子不能为空),有C(a[i]-1,k-1)种分法.
然后将k组花色按原来的顺序塞到前面已经排好的方案中,这里又有两种情况：
1.放到普通的位置
2.放到原来同花色相邻的中间，这样j就减小了
假设放l组到相邻花色中间
这里的方案数是从j个同花色相邻的位置中选l个位置出来，则有C(j,l)种方案。
假设前面有sum张牌，则有sum+1个位置，除去j个相邻位置，将剩下的k-l组放进来，有C(sum+1-j,k-l)种放法
所以最终的状态转移为
设x为放完后的同花色相邻，则x=j+a[i]-k-l;
dp[i][x]+=Cnm(j,l) * Cnm(sum+1-j,k-l)* Cnm(a[i]-1,k-1) * dp[i-1][j]