Codeforces401D Roman and Numbers

http://codeforces.com/problemset/problem/401/D

Roman is a young mathematician, very famous in Uzhland. Unfortunately, Sereja doesn't think so. To make Sereja change his mind, Roman is ready to solve any mathematical problem. After some thought, Sereja asked Roma to find, how many numbers are close to number n, modulo m.

Number x is considered close to number n modulo m, if:

• it can be obtained by rearranging the digits of number n,
• it doesn't have any leading zeroes,
• the remainder after dividing number x by m equals 0.

Roman is a good mathematician, but the number of such numbers is too huge for him. So he asks you to help him.

Input

The first line contains two integers: n (1 ≤ n < 1018) and m (1 ≤ m ≤ 100).

Output

In a single line print a single integer — the number of numbers close to number n modulo m.

题意：将n的各位数字重排的所有情况中，模m为0的有多少种？不能有前导0。

思路：很神奇！其实就是TSP模型。

把n的每一位数字看作一个点，题目不就等价于“遍历一遍图中所有的结点，使满足...”吗？n个点，不同的遍历顺序有影响，和经典的TSP模型如出一辙！

设f(s,j):遍历s表示的集合，模m为j的方案数。

f(s)的转移很简单，由s中现在为1的点原来为0的状态转移来。

·如何控制不能有前导0呢？把各位排个序，0在最前面几个，使得这一部分方案数f()均为0就行了，从第一个非0处开始转移。

·相同的数字会有重复，对于任意含有k个相同数字i的状态，由于枚举i，重复了k!次，故需要将最后答案除以每个数字的重复数字阶乘。对于任意状态f(s,j)且存在重复数字i有k个，要么不合法，为0；要么合法，一定是k!的倍数。

#include<bits/stdc++.h>
using namespace std;
#define ll long long

ll n,m,f[(1<<18)+10][105],fac[20];
int c[20],cnt[10],tot;

void init()
{
	while(n)
	{
		int x=n%10;
		c[tot++]=x;
		cnt[x]++;
		n/=10;
	}
	sort(c,c+tot);
	fac[0]=1;
	for(int i=1;i<20;i++)fac[i]=fac[i-1]*i;
}

int main()
{
//	freopen("input.in","r",stdin);
	cin>>n>>m;
	init();
	int start=0;
	for(int i=0;i<tot;i++)
		if(c[i]==0)start=i+1; 
		else f[1<<i][c[i]%m]=1;
	for(int s=(1<<start);s<(1<<tot);s++)
	{
		for(int j=0;j<tot;j++)if((1<<j)&s)
		{
			for(int k=0;k<=m;k++)f[s][(k*10+c[j])%m]+=f[s^(1<<j)][k];
		}
	}
	ll ans=f[(1<<tot)-1][0];
	for(int i=0;i<=9;i++)ans/=fac[cnt[i]];
	cout<<ans<<endl;
	return 0;
}