[hiho1159] Poker

题意：给你一副扑克中的几张牌，要你将这些牌进行排列，并且相邻的牌数字不能相同

题解：

dp（组合数）

dp[i][j]表示放到第i种数字，有j个数字相同且相邻的方案数

1、对于同一种数字，可以将其划分为k组，有C(cnt[i]-1,k-1)种分法

2、考虑将这k组中的l组放到数字相同的中间，其余放置任意位置，则分别有：

C(j,l)和C(tot+1-j,k-l)种放法（tot表示前面有多少张牌）

那么就可已转移了

设x为放完后的同花色相邻，则x=j+a[i]-k-l

dp[i][x]+=C(j,l) * C(tot+1-j,k-l)* C(cnt[i]-1,k-1) * dp[i-1][j]

/*
  Poker
  组合dp
*/
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cmath>
#define ull unsigned long long 
using namespace std;

int num[310],cnt[15];
ull c[55][55],dp[15][55],fac[10];
char alph[15]={"0A23456789TJQK"};

int gi() {
  int x=0,o=1; char ch=getchar();
  while(ch!='-' && (ch<'0' || ch>'9')) ch=getchar();
  if(ch=='-') o=-1,ch=getchar();
  while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();
  return o*x;
}

void pre() {
  c[0][0]=1;
  for(int i=1; i<=52; i++) {
    c[i][0]=c[i][i]=1;
    for(int j=1; j<i; j++) {
      c[i][j]=c[i-1][j-1]+c[i-1][j];
    }
  }
  for(int i=1; i<=13; i++) num[alph[i]]=i;
  fac[0]=1;
  for(int i=1; i<=4; i++) fac[i]=fac[i-1]*i;
}

int main() {
  pre();
  int T=gi(),tot,n,t=0;
  while(T--) {
    n=gi(),tot=0;
    memset(cnt,0,sizeof(cnt));
    for(int i=1; i<=n; i++) {
      char s[3];
      scanf("%s", s);
      cnt[num[s[0]]]++;
    }
    memset(dp,0,sizeof(dp));
    dp[0][0]=1;
    for(int i=1; i<=13; i++) {
      if(cnt[i]==0) {
    for(int j=0; j<=max(0,tot-1); j++)
      dp[i][j]=dp[i-1][j];
    continue;
      }
      for(int j=0; j<=max(0,tot-1); j++) 
    for(int k=1; k<=cnt[i]; k++) 
      for(int l=0; l<=k; l++) 
        if(j+cnt[i]-k-l>=0)
          dp[i][j+cnt[i]-k-l]+=dp[i-1][j]*c[cnt[i]-1][k-1]*c[j][l]*c[tot+1-j][k-l];
      tot+=cnt[i];
    }
    ull ans=dp[13][0];
    for(int i=1; i<=13; i++) {
      ans=ans*fac[cnt[i]];
    }
    printf("Case #%d: %llu
", ++t,ans);
  }
}