题目链接：

option=com_onlinejudge&Itemid=8&page=show_problem&problem=4540">点击打开链接

题意：

给定一个数，又一次排列这个数的各个位置使得

1、无前导0

2、能被11整除

问：

有多少种组合方法

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

typedef long long ll;

const int mod = 1000000000 + 7;

const int N = 100+2;

const int L = 50+2;

const int M = L*9;

char s[N];

int x, sum, len, app[10];

int C[N][N], d[10][L][M], g[N][N], tot[12];

int c(int x, int y) {

	if (~C[x][y])

		return C[x][y];

	if (x == 1 || y==0)

		return C[x][y] = 1;

	C[x][y] = 0;

	for (int i = 0; i <= y; ++i)

		C[x][y] = (C[x][y] + c(x-1, y-i))%mod;

	return C[x][y];

}

void work() {

	int v;

	len = strlen(s);

	sum = 0;

	memset(app, 0, sizeof app);

	for (int i = 0; i < len; ++i) {

		++ app[s[i]-'0'];

		sum += s[i]-'0';

	}

	tot[0] = 0;

	for (int i = 1; i <= 9; ++i)

		tot[i] = tot[i-1] + app[i];

	x = (len+1)/2;

	memset(d, 0, sizeof d);

	d[0][0][0] = 1;

	for (int i = 0; i <= 8; ++i)

		for (int j = 0; j <= x && j <= tot[i]; ++j)

			for (int s = 0; s <= j*9; ++s)

				if (d[i][j][s] > 0)

					for (int k = 0; k <= app[i+1] && k+j <= x; ++k) {

						v = (ll)d[i][j][s] * c(j+1,k) % mod;

						v = (ll)v*g[len-x-tot[i]+j][app[i+1]-k]%mod;

						d[i+1][j+k][s+k*(i+1)] = (d[i+1][j+k][s+k*(i+1)] + v)%mod;

					}

	int ans = 0;

	for (int j = 1; j <= x; ++j)

		for (int s = 0; s <= j*9; ++s)

			if (d[9][j][s] > 0 && abs(sum-s-s) % 11 == 0) {

				int k = x - j;

				if (k > app[0])

					continue;

				ans += (ll)d[9][j][s] * c(j,k) % mod;

				ans %= mod;

			}

	printf("%d\n", ans);

}

int main() {

	memset(C, -1, sizeof C);

	memset(g, 0, sizeof g);

	for (int i = 0; i < N; ++i) {

		g[i][0] = g[i][i] = 1;

		for (int j = 1 ; j < i; ++j)

			g[i][j] = (g[i-1][j] + g[i-1][j-1])%mod;

	}

	while (~scanf("%s", s))

		work();

	return 0;

}