转载自：http://blog.****.net/u013611908/article/details/44545955
题目大意：一副牌除掉大小王，然后有一些已经形成了序列，让你算剩下的牌能组合出多少种比给的序列小的组合。
思路：搜索，分这个位置相同或者小于，假如放一个小于的，则剩下的就是全排列
只不过这边的全排列是相同元素的全排列。
所采取的是位置的选择的排列方式。
比如1112233这个所有的情况就是c(7,3)*c(4,2)*c(2,2)
题目ｗａ了很多发。
题目需要注意，是严格小于，等于是不行的。
另外就是涉及到剩的张数比给的少的情况。
这边直接给数据让大家测试吧，ｐｓ：是抄别人的。
Input:KKKKQQQQJJJJ10101010999988887777666655554444
K
AA22334455667788991010JJKKK
KAA22334455667788991010JJQK
KKKKJJJJQQQQ1010101099998888777766665555444433332222AAAA
AA22334455667788991010JJKKQQ
KKKJJJJQQQQ1010101099998888777766665555444433332222AAAA Output:
34650
944696453
5
596617684
0
5
1
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
#define mod 1000000007
int a[15];
char str[60];
long long ans = 0;
long long c[60][60];
void init()
{
for (int i = 0; i < 60;i++)c[i][0] = c[i][i] = 1;
for (int i = 2; i < 60;i++)
for (int j = 1; j < i; j++)
c[i][j] = (c[i - 1][j] + c[i - 1][j - 1])%mod;
}
long long gao(int sum)
{
long long ans = 1;
for (int i = 1; i < 14; i++)
{
ans = (ans*c[sum][a[i]])%mod;
sum -= a[i];
}
return ans;
}
void dfs(int cur, int sum)
{
if (!str[cur])
{
return;
}
if (sum == 0)
{
ans++;
return;
}
int k = str[cur] - 48;
for (int i = 1; i<k; i++)
{
if (a[i]>0)
{
a[i]--;
ans = (ans + (gao(sum-1)) % mod) % mod;
a[i]++;
}
}
if (a[k]>0)
{
a[k]--;
dfs(cur + 1, sum - 1);
}
}
int main()
{
init();
while (~scanf("%s", str))
{
int len = strlen(str);
int j = 0;
for (int i = 1; i < 14; i++)
a[i] = 4;
for (int i = 0; i < len; i++)
{
if (str[i] == 'A')
{
str[j++] = 1 + 48;
a[1]--;
}
else
if (str[i] == '1')
{
str[j++] = 10 + 48;
a[10]--;
}
else
if (str[i] == 'J')
{
str[j++] = 11 + 48;
a[11]--;
}
else
if (str[i] == 'Q')
{
str[j++] = 12 + 48;
a[12]--;
}
else
if (str[i] == 'K')
{
str[j++] = 13 + 48;
a[13]--;
}
else
if (str[i] == '0')
continue;
else
{
str[j++] = str[i];
a[str[i] - 48]--;
}
}
str[j] = 0;
int sum = 0;
for (int i = 1; i < 14; i++)
sum += a[i];
ans = 0;
if (sum != 0)
dfs(0, sum);
printf("%lld\n", ans);
}
return 0;
}