2270.cpp

这是哈尔滨工业大学acmOJ的源代码

/*  This Code is Submitted by wywcgs for Problem 2270 on 2006-07-23 at 15:12:48 */ 
#include <cstdio>
#include <algorithm>
using namespace std;

typedef long long int64;
const int DN = 15;
const int SN = 1 << DN;
const int M = 50;

int m, l, id[10][DN], n[10];
int64 have[SN][M];
bool vst[SN][M];
char d[DN+1];

int64 find(int, int);

int main()
{
	while(scanf("%s %d", d, &m) != EOF) {
		memset(vst, false, sizeof(vst)); memset(n, 0, sizeof(n));
		for(l = 0; d[l] != 0; l++) id[d[l]-'0'][n[d[l]-'0']++] = l;
		int st = 1<<l;
		if(m%10 == 0) have[st-1][0] = 0;
		printf("%lld\n", find(st-1, 0));
	}

	return 0;
}

int64 find(int st, int r)
{
	if(st == 0) return (r == 0);
	else if(!vst[st][r]) {
		int i; vst[st][r] = true; have[st][r] = 0;
		for(i = 1; i < 10; i++)
			if(n[i] > 0) { have[st][r] += find(st^(1<<id[i][--n[i]]), (r*10+i)%m); n[i]++; }
	}
	return have[st][r];
}