【BZOJ 1004】[HNOI2008] Cards

Qizy 数论, 群论, 解题报告

题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=1004
数据传送门：http://pan.baidu.com/s/1jIc0r5s

这个题目，最开始无脑暴力，结果T到死 QAQ
总之就是Polya上不了，就只能上Burnside
然后直接求不动点也要T，于是只能搞三维背包
详见：hzwer.com/3222.html

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

const int MAXN = 21;
const int N = 61;
const int SGZ = 3;

int f[MAXN][MAXN][MAXN],p,col[MAXN],n,m,vout,tot,cnt[N],to[N],vis[N];

inline void Get_CIR(){
	tot = 0; memset(vis,0,sizeof(vis));
	for (int i=1;i<=n;i++) scanf("%d",&to[i]);
	for (int i=1;i<=n;i++) if (!vis[i]) { cnt[++tot] = 0;
		for (int w=i;!vis[w];w=to[w]) cnt[tot]++, vis[w] = 1;
	} 
}

inline void DP(){
	memset(f,0,sizeof(f)); f[0][0][0] = 1;
	for (int t=1,w=cnt[1];t<=tot;w=cnt[++t]) for (int i=col[1];~i;i--) 
		for (int j=col[2];~j;j--) for (int k=col[3];~k;k--) if (f[i][j][k]){
			if (i + w <= col[1]) f[i+w][j][k] += f[i][j][k], f[i+w][j][k] %= p;
			if (j + w <= col[2]) f[i][j+w][k] += f[i][j][k], f[i][j+w][k] %= p;
			if (k + w <= col[3]) f[i][j][k+w] += f[i][j][k], f[i][j][k+w] %= p;
	}
	vout += f[col[1]][col[2]][col[3]]; vout %= p;
}

inline int pow(int w, int t){
	int ret = 1;
	while (t) {
		if (t & 1) ret = ret*w % p;
		t >>= 1; w = w*w % p;
	}
	return ret;
}

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

int main(){
	for (int i=1;i<=SGZ;i++) n += (col[i] = read()); m = read(), p = read();
	for (tot=1;tot<=n;tot++) cnt[tot] = 1; tot--; DP(); 
	for (int i=1;i<=m;i++) Get_CIR(), DP();
	printf("%d\n",vout*pow(m+1,p-2)%p);
	return 0;
}

85 thoughts to “【BZOJ 1004】[HNOI2008] Cards”

  8. Hello There. I discovered your blog the usage of msn. This is a
    very smartly written article. I’ll make sure to bookmark it
    and return to read extra of your useful information.
    Thanks for the post. I will definitely comeback.

    Reply

  9. Hi! Someone in my Facebook group shared this site with us so I came to take a look.
    I’m definitely loving the information. I’m bookmarking and will be tweeting this to my followers!
    Terrific blog and superb style and design.

    Reply

  10. Great beat ! I wish to apprentice while you amend your site, how can i subscribe for a blog web site?
    The account aided me a acceptable deal. I had been a little bit acquainted of
    this your broadcast provided bright clear concept

    Reply

  15. Nice post. I was checking continuously this blog and I’m impressed!
    Very helpful info specially the last part :
    ) I care for such info a lot. I was seeking this certain information for a very long time.

    Thank you and good luck.

    Reply

  17. Thanks for ones marvelous posting! I genuinely enjoyed reading
    it, you can be a great author.I will remember to bookmark your blog and definitely will come
    back later on. I want to encourage yourself to continue
    your great job, have a nice morning!

    Reply

  24. Amazing! This blog looks exactly like my old one!
    It’s on a completely different topic but it has pretty much the same
    layout and design. Excellent choice of colors!

    Reply

  26. Have you ever thought about adding a little bit more than just
    your articles? I mean, what you say is valuable and all. But
    think of if you added some great visuals or videos to give your posts more, “pop”!
    Your content is excellent but with pics and videos, this website could definitely be one of the most beneficial in its niche.
    Fantastic blog!

    Reply

  31. Link exchange is nothing else but it is simply placing the other person’s webpage link on your page at appropriate place and
    other person will also do same in support of
    you.

    Reply

  34. Thanks for sharing excellent informations. Your website is very cool. I’m impressed by the details that you have on this website. It reveals how nicely you perceive this subject. Bookmarked this website page, will come back for extra articles. You, my friend, ROCK! I found just the info I already searched all over the place and simply could not come across. What a perfect website.

    Reply

  54. It is the best time to make some plans for the future and it’s
    time to be happy. I’ve read this post and if I could I wish to suggest you some interesting things or tips.
    Perhaps you could write next articles referring to this article.
    I desire to read even more things about it!

    Reply

  60. Wonderful blog! I found it while surfing around on Yahoo News.
    Do you have any suggestions on how to get listed in Yahoo News?
    I’ve been trying for a while but I never seem to get there!
    Thanks

    Reply

  66. Hello There. I discovered your weblog the usage of msn. That
    is a really neatly written article. I will make sure to bookmark it and return to learn extra of your useful information. Thank you for the post.

    I will certainly return.

    Reply

  71. naturally like your website however you need to take a look at
    the spelling on several of your posts. Several
    of them are rife with spelling issues and I find it very bothersome to tell
    the truth however I’ll definitely come again again.

    Reply

  74. Good blog you’ve got here.. It’s difficult to find
    high-quality writing like yours nowadays. I honestly appreciate people like you!
    Take care!!

    Reply

Leave a Reply

Your email address will not be published. Required fields are marked *