【HDU 4623】Crime

相关链接

题目传送门:http://acm.hdu.edu.cn/showproblem.php?pid=4623
神犇题解:http://blog.csdn.net/keshuai19940722/article/details/49455357

解题报告

脑袋里一直想着去年$ZJOI$的小星星
然后就各种优化,最后还是$T$成狗 QwQ

然后正解就是把每个数按照因数种类不同分组
最后搞下来只有$14$种不同的,然后暴力状压$DP$就可以了

Code

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

const int N = 3000000;
const int M = 16;

int n,mx,MX,MOD,f[N][M],cnt[M],bit[M],cur[M],sym[M],suf[M],leg[M][M];
int ty[]={0,1,2,3,2,4,5,6,2,3,7,8,5,9,10,11,2,1,5,1,7,12,13,1,5,4,14,3,10};

inline int read() {
	char c=getchar(); int f=1,ret=0;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret * f;
}

int gcd(int a, int b) {
	return b? gcd(b, a%b): a;
}

inline void decode(int w, int *arr) {
	for (int i=mx;i;i--) {
		arr[i] = w % bit[i];
		w /= bit[i];
	}
}

inline int solve() {
	memset(cnt,0,sizeof(cnt));
	mx = MX = 0;
	for (int i=1;i<=n;i++) {
		cnt[ty[i]]++;
		mx = max(mx, ty[i]);
	}
	for (int i=1;i<=mx;i++) {
		bit[i] = cnt[i] + 1;
		MX = MX * bit[i] + cnt[i];
	}
	suf[mx] = 1;
	for (int i=mx-1;i;i--) {
		suf[i] = suf[i+1] * bit[i+1];
	}
	memset(f,0,sizeof(f));
	f[0][0] = 1;
	for (int i=0;i<MX;i++) {
		decode(i, cur);
		for (int j=0;j<=mx;j++) {
			if (!f[i][j]) continue;
			for (int k=1;k<=mx;k++) {
				if ((leg[k][j] || !j) && cur[k] < cnt[k]) {
					int to = i + suf[k];
					f[to][k] = (f[to][k] + (LL)f[i][j] * (cnt[k] - cur[k])) % MOD;
				}
			}
		}
	}
	int ret = 0;
	for (int i=1;i<=mx;i++) {
		ret = (ret + f[MX][i]) % MOD;
	}
	return ret;
}

int main() {
	for (int i=1;i<=28;i++) {
		if (sym[ty[i]]) continue;
		sym[ty[i]] = i;
	}
	for (int i=1;i<=14;i++) {
		for (int j=1;j<=14;j++) {
			if (gcd(sym[i], sym[j]) == 1) {
				leg[i][j] = 1;
			}
		} 
	}
	for (int T=read();T;T--) {
		n = read(); MOD = read();
		printf("%d\n",solve());
	}
	return 0;
}

14 thoughts to “【HDU 4623】Crime”

  1. 55632 937196Wow, incredible blog format! How lengthy have you been blogging for? you make running a blog glance simple. The full glance of your web site is great, as smartly the content material material! 323661

  2. 104955 22427My spouse and I stumbled more than here from a different website and thought I may as nicely check things out. I like what I see so now im following you. Appear forward to going over your internet page repeatedly. 977546

  3. 981232 632516I need to admit that that is one wonderful insight. It surely gives a company the opportunity to have in around the ground floor and genuinely take part in generating a thing particular and tailored to their needs. 823735

  4. 214452 415211I love the appear of your internet site. I lately built mine and I was looking for some style ideas and you gave me several. May possibly I ask you whether you developed the internet site by youself? 172575

  5. 958967 917498Hi my loved 1! I wish to say that this post is wonderful, excellent written and come with almost all critical infos. I would like to see far more posts like this . 502348

发表评论

电子邮件地址不会被公开。 必填项已用*标注