pku1349.cpp

这是ACM 方面的资料 是PKU的 北京大学的出来的

#include <stdio.h>
#include <string.h>
#define MOD 100000

char s[1000];
int v1[1000], v2[1000];
int L1, L2;
int x[51], use[51], cnt[51];
int N;

void v2mul(int x)
{
	int i;
	for (i = 0; i < L2; i++)
		v2[i] *= x;
	for (i = 0; i < L2; i++)
		if (v2[i] >= MOD)
		{
			v2[i + 1] += v2[i] / MOD;
			v2[i] %= MOD;
		}
	if (v2[L2])
		L2++;
}

void addv1()
{
	int i;
	int L;
	L = L1 > L2 ? L1 : L2;
	for (i = 0; i < L; i++)
		v1[i] += v2[i];
	for (i = 0; i < L; i++)
	{
		if (v1[i] >= MOD)
		{
			v1[i + 1] += v1[i] / MOD;
			v1[i] %= MOD;
		}
	}
	L1 = L;
	if (v1[L1])
		L1++;
}

void getans()
{
	int i, j;
	memset(v1, 0, sizeof(v1));
	L1 = 0;
	memset(v2, 0, sizeof(v2));
	L2 = 0;
	v2[0] = 1;
	L2 = 1;
	v1[0] = 1;
	L1 = 1;
	for (i = 2; i <= N; i++)
	{
		v2mul(i - 1);
		for (j = 0; j < cnt[N - i]; j++)
			addv1();
	}
	printf("%d", v1[L1-1]);
	for (i = L1 - 2; i >= 0; i--)
		printf("%05d", v1[i]);
}

void solve()
{
	int i, j;
	char *p;
	sscanf(s, "(%d,", &N);
	p = s + 1;
	while (*p != '(')
		p++;
	p++;
	for (i = 0; i < N; i++)
	{
		sscanf(p, "%d", &x[i]);
		p++;
		while (*p != ',' && *p != ')')
			p++;
		p++;
	}
	memset(use, 0, sizeof(use));
	memset(cnt, 0, sizeof(cnt));
	for (i = 0; i < N; i++)
	{
		use[x[i]] = 1;
		for (j = 1; j < x[i]; j++)
			if (!use[j]) cnt[i]++;
	}
	getans();
}

int main()
{
	int t = 0;
	while (-1 != scanf("%s", s))
	{
		if (strcmp(s, "-1") == 0)
			break;
		if (t)
			printf(",");
		t++;
		solve();
	}
}