首页 > ACM题库 > HDU-杭电 > HDU 4623-Crime[解题报告]HOJ
2015
09-17

HDU 4623-Crime[解题报告]HOJ

Crime

问题描述 :

You kill a person and will be executed by shooting tomorrow,but you have a program contest to do today,after several hours’ hard work,you solved all problems except this one.You died with the pity that didn’t solved it.But now you have second chance.
Count the number of permutation of number 1 to n that every adjacent number are coprime.To avoid large number,output the result mod a number M.

输入:

The first line contains integer T(1<=T<=5).Denoting the number of the test cases.
Then T lines follows,each line contains two integers n,M (1<=n<=28, 1<=M<=30000).
The n for each test cases will not be the same.

输出:

The first line contains integer T(1<=T<=5).Denoting the number of the test cases.
Then T lines follows,each line contains two integers n,M (1<=n<=28, 1<=M<=30000).
The n for each test cases will not be the same.

样例输入:

5
1 10000
2 10000
3 10000
4 10000
5 10000

样例输出:

1
2
6
12
72
Hint
There is a solution without making table. Two integers are coprime if their greatest common divisor is 1.

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>

using namespace std;
vector <int> vec[20];
void _addedge(int i, int j) { vec[i].push_back(j); }
int num[20][5]={{}, { 4, 1,17,19,23}, { 4, 2, 4, 8,16}, { 3, 3, 9,27}, { 2, 5,25}, { 4, 6,12,18,24}, { 1, 7}, { 2,10,20}, { 1,11}, { 1,13}, { 2,14,28}, { 1,15}, { 1,21}, { 1,22}, { 1,26}};
int sta[20], cnt[20], n, mod, ST;
int F[15][1800005];
int GCD(int a, int b) { for (int t; a%b; t=a%b, a=b, b=t) ; return b ; }
int dfs(int m, int st)
{
	if (F[m][st]!=-1) return F[m][st];
	if (st==ST) return F[m][st]=1, 1;
	int i, j, res=0, siz=vec[m].size();
	cnt[m]--;
	for (i=0; i<siz; i++)
		if (j=vec[m][i], cnt[j])
			res=(res+dfs(j, st+sta[j]))%mod;
	cnt[m]++;
	return F[m][st]=res, F[m][st];
}
int main()
{
	//freopen("1.txt", "r", stdin);
	int cas, T, i, j;
	int A[5]={1,1,2,6,24};
	
	for (i=1; i<=14; i++)
		for (j=1; j<=14; j++)
			if (i==1 || GCD(num[i][1], num[j][1])==1) _addedge(i, j);
	for (i=sta[1]=1; i<=14; i++) _addedge(0, i), sta[i+1]=sta[i]*(num[i][0]+1);
	
	for (cas=scanf("%d", &T); cas<=T; cas++)
	{
		scanf("%d %d", &n, &mod);
		memset(cnt, 0, sizeof(cnt));
		memset(F, 0xff, sizeof(F));
		for (i=1; i<=14; i++)
			for (j=1; j<=num[i][0] && num[i][j]<=n; j++)
				cnt[i]++;
				
		for (ST=0, i=1; i<=14; i++) ST+=sta[i]*cnt[i];
			 
		int ans=dfs(0, 0);
		for (i=1; i<=14; i++)
			ans=(ans*A[cnt[i]])%mod;
		printf("%d\n", ans);
	}
	
	return 0;
}

  1. 至于金三所谓“时刻准备发射核武器”的叫嚣,更是吓唬人的纸老虎。其实朝鲜的核武器是否已经小型化足以用于实战,还有很大疑问。即使能用于实战,其运载及投放能力也极其有限。核武器不是一般的常规武器,没有可靠的运载工具等于没有,总不能在两军对垒的前线引爆原子弹,那

  2. 至于金三所谓“时刻准备发射核武器”的叫嚣,更是吓唬人的纸老虎。其实朝鲜的核武器是否已经小型化足以用于实战,还有很大疑问。即使能用于实战,其运载及投放能力也极其有限。核武器不是一般的常规武器,没有可靠的运载工具等于没有,总不能在两军对垒的前线引爆原子弹,那

  3. 至于金三所谓“时刻准备发射核武器”的叫嚣,更是吓唬人的纸老虎。其实朝鲜的核武器是否已经小型化足以用于实战,还有很大疑问。即使能用于实战,其运载及投放能力也极其有限。核武器不是一般的常规武器,没有可靠的运载工具等于没有,总不能在两军对垒的前线引爆原子弹,那

  4. 至于金三所谓“时刻准备发射核武器”的叫嚣,更是吓唬人的纸老虎。其实朝鲜的核武器是否已经小型化足以用于实战,还有很大疑问。即使能用于实战,其运载及投放能力也极其有限。核武器不是一般的常规武器,没有可靠的运载工具等于没有,总不能在两军对垒的前线引爆原子弹,那