【BZOJ 4197】[NOI2015] 寿司晚宴

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4197

解题报告

考虑把小于$\sqrt{n}$的因数状压起来
然后将所有数按照大于$\sqrt{n}$的因数分组
最后分组$DP$即可
总时间复杂度:$O(500 \cdot 3^8)$

Code

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

const int N = 509;
const int M = 6561;

int pri[] = {2, 3, 5, 7, 11, 13, 17, 19};
int n, gpri[N], spri[N], sta1[M], sta2[M], tt[M][N][3];
LL MOD, *f, *g, *h, arr1[M], arr2[M], arr3[M], ori[M];
vector<int> sta[N];

inline void relax(LL &a, LL b) {
	a = (a + b) % MOD;
}

inline int num(int x, int t) {
	for (; t; x /= 3, t--);
	return x % 3;
}

inline int SET(int w, int t, int v) {
	static int buf[] = {1, 3, 9, 27, 81, 243, 729, 2187};
	int ret = 0;
	for (int i = 0; i < 8; i++, w /= 3, t >>= 1) {
		if (t & 1) {
			ret += buf[i] * v;
		} else {
			ret += buf[i] * (w % 3);
		}
	}
	return ret;
}

int main() {
	freopen("dinner.in", "r", stdin);
	freopen("dinner.out", "w", stdout);
	cin>>n>>MOD; 
	for (int i = 0; i < M; i++) {
		for (int j = 0; j < 8; j++) {
			int t = num(i, j);
			if (t == 1) {
				sta1[i] |= 1 << j;
			} else if (t == 2) {
				sta2[i] |= 1 << j;
			}
		}
	}
	for (int i = 0; i < M; i++) {
		for (int j = 0; j < (1 << 8); j++) {
			for (int k = 1; k <= 2; k++) {
				tt[i][j][k] = SET(i, j, k);
			}
		}
	}
	for (int i = 2; i <= n; i++) {
		gpri[i] = i;
		for (int j = 0; j < 8; j++) {
			if (gpri[i] % pri[j] == 0) {
				spri[i] |= (1 << j);
				while (gpri[i] % pri[j] == 0) {
					gpri[i] /= pri[j];
				}
			}
		}
	}
	f = arr1, g = arr2, h = arr3;
	g[0] = f[0] = 1;
	for (int i = 2; i <= n; i++) {
		if (gpri[i] == 1) {
			for (int j = M - 1; ~j; j--) {
				if (g[j]) {
					int sta = 0;
					for (int k = 0; k < 8; k++) {
						if (spri[i] >> k & 1) {
							sta |= num(j, k);
						}
					}
					if (sta == 0) {
						relax(f[tt[j][spri[i]][1]], g[j]);
						relax(f[tt[j][spri[i]][2]], g[j]);
					} else if (sta < 3) {
						relax(f[tt[j][spri[i]][sta]], g[j]);
					}
				}
			}
			memcpy(g, f, sizeof(arr1));
			swap(f, g);
		} else {
			sta[gpri[i]].push_back(spri[i]);
		}
	}
	for (int i = 2; i <= n; i++) {
		if (!sta[i].empty()) {
			memcpy(h, g, sizeof(arr1));
			memcpy(ori, g, sizeof(arr1));
			for (int j = 0; j < (int)sta[i].size(); j++) {
				int vv = sta[i][j];
				for (int k = M - 1; ~k; k--) {
					if (g[k]) {
						int s1 = vv & sta1[k];
						if (!s1) {
							relax(f[tt[k][vv][2]], g[k]);
						} 
					}
				}
				memcpy(g, f, sizeof(arr1));
				swap(f, g);
			}
			memcpy(f, h, sizeof(arr1));
			for (int j = 0; j < (int)sta[i].size(); j++) {
				int vv = sta[i][j];
				for (int k = M - 1; ~k; k--) {
					if (h[k]) {
						int s2 = vv & sta2[k];
						if (!s2) {
							relax(f[tt[k][vv][1]], h[k]);
						}
					}
				}
				memcpy(h, f, sizeof(arr1));
				swap(f, h);
			}
			for (int k = 0; k < M; k++) {
				f[k] = g[k] = (f[k] + g[k] - ori[k]) % MOD + MOD;
			}
		}
	}
	LL ans = 0;
	for (int i = 0; i < M; i++) {
		relax(ans, f[i]);
	}
	printf("%lld\n", ans);
	return 0;
}

93 thoughts to “【BZOJ 4197】[NOI2015] 寿司晚宴”

  1. The other day, while I was at work, my cousin stole my iphone and tested
    to see if it can survive a thirty foot drop, just so she can be
    a youtube sensation. My iPad is now broken and she has 83 views.
    I know this is completely off topic but I had to share it with
    someone!

  2. I blog quite often and I really thank you for your information.
    This great article has truly peaked my interest.
    I’m going to take a note of your website and keep checking for new information about once per week.
    I opted in for your Feed as well.

  3. magnificent submit, very informative. I’m wondering why the other
    specialists of this sector don’t realize this. You must proceed your writing.
    I’m sure, you’ve a huge readers’ base already!

  4. Hello there, I discovered your website via Google whilst
    looking for a related topic, your web site got
    here up, it looks good. I have bookmarked it in my google bookmarks.

    Hi there, just changed into alert to your blog via
    Google, and found that it’s truly informative.
    I am going to be careful for brussels. I’ll be grateful if you continue this in future.
    Numerous other people will likely be benefited from your writing.
    Cheers!

  5. I really love your site.. Excellent colors & theme.
    Did you build this website yourself? Please reply back as I’m planning to create my own site and would love to find out where you got this from or exactly what the theme is named.
    Thank you!

  6. hey there and thank you for your info – I have definitely picked up something new from right
    here. I did however expertise a few technical points using this
    website, since I experienced to reload the web site a lot
    of times previous to I could get it to load properly.
    I had been wondering if your hosting is OK? Not that I am complaining, but sluggish loading instances times will
    often affect your placement in google and can damage your high
    quality score if advertising and marketing with Adwords.

    Well I’m adding this RSS to my e-mail and could look out for a
    lot more of your respective intriguing content. Ensure
    that you update this again very soon.

  7. I have been browsing online more than three hours today, yet I never found any
    interesting article like yours. It is pretty worth enough for me.
    In my view, if all web owners and bloggers made good content
    as you did, the net will be much more useful than ever before.

  8. Excellent post. Keep posting such kind of info on your page.
    Im really impressed by your site.
    Hello there, You’ve performed an incredible job.
    I’ll definitely digg it and individually suggest
    to my friends. I’m sure they’ll be benefited from this site.

  9. Hey there! I understand this is sort of off-topic
    however I had to ask. Does building a well-established blog like yours take a massive amount work?
    I’m brand new to running a blog however I do write in my
    diary every day. I’d like to start a blog so I can share my own experience and thoughts online.
    Please let me know if you have any ideas or tips for new
    aspiring bloggers. Appreciate it! natalielise plenty of fish

  10. Greetings from Carolina! I’m bored to tears at work so I decided to browse your site on my iphone during lunch break.

    I love the info you present here and can’t wait to take a look when I get home.
    I’m amazed at how quick your blog loaded on my mobile ..
    I’m not even using WIFI, just 3G .. Anyhow, great site!

  11. Hey there I am so thrilled I found your web site, I really found you by accident, while I was looking on Google
    for something else, Nonetheless I am here now and would
    just like to say thanks for a tremendous post and a
    all round exciting blog (I also love the theme/design), I don’t have
    time to browse it all at the minute but I have book-marked
    it and also added your RSS feeds, so when I have time
    I will be back to read much more, Please do keep up the excellent work.

  12. Superb blog! Do you have any recommendations for aspiring writers?
    I’m planning to start my own site soon but I’m a little lost on everything.
    Would you recommend starting with a free platform
    like WordPress or go for a paid option? There are so many choices out there that I’m
    completely confused .. Any tips? Thanks a lot!

  13. An intriguing discussion is definitely worth comment. I do
    believe that you ought to write more about this subject, it might not be a taboo subject but usually people do not talk about these topics.
    To the next! Cheers!!

  14. whoah this weblog is wonderful i really like
    studying your articles. Keep up the good work! You recognize, lots of persons are
    looking round for this info, you can aid them greatly.

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

  16. You actually make it appear so easy with your presentation however I find this matter to
    be actually something that I feel I might never understand.

    It sort of feels too complicated and extremely huge for me.
    I am taking a look forward to your subsequent post, I will
    try to get the hold of it!

  17. Oh my goodness! Amazing article dude! Many thanks, However I am going through
    difficulties with your RSS. I don’t know why I am unable to join it.
    Is there anybody having identical RSS problems? Anyone who
    knows the answer can you kindly respond? Thanks!!

  18. I’m not sure where you’re getting your info, but good topic.
    I needs to spend some time learning more or understanding more.
    Thanks for magnificent info I was looking for this info for my mission.

  19. My partner and I stumbled over here by a different web page and thought I should check things out.

    I like what I see so now i am following you.
    Look forward to going over your web page for a second time.

  20. Hi! Someone in my Myspace group shared this site with us so I came to check
    it out. I’m definitely loving the information. I’m bookmarking and will be tweeting this
    to my followers! Wonderful blog and wonderful style and design.

  21. My spouse and I stumbled over here from a different web address and thought I might as
    well check things out. I like what I see so now i’m following
    you. Look forward to exploring your web page yet again.

  22. It’s a pity you don’t have a donate button! I’d
    definitely donate to this fantastic blog! I suppose for now i’ll settle for book-marking and adding your RSS
    feed to my Google account. I look forward to brand new updates and will talk about this blog
    with my Facebook group. Chat soon!

  23. Hello, i think that i saw you visited my weblog thus i came to “return the favor”.I’m attempting to find things to improve my web site!I suppose its ok to use
    a few of your ideas!!

  24. With havin so much content do you ever run into any problems
    of plagorism or copyright violation? My site has a lot
    of unique content I’ve either written myself or outsourced but
    it looks like a lot of it is popping it up all over the internet without my
    permission. Do you know any solutions to help reduce content from
    being ripped off? I’d genuinely appreciate it.

  25. Hi there very cool site!! Guy .. Beautiful .. Superb .. I’ll bookmark your site
    and take the feeds additionally? I am happy to seek
    out numerous useful information right here within the post, we want work out more strategies in this regard, thank you for sharing.
    . . . . .

  26. hey there and thank you for your info – I’ve definitely picked
    up anything new from right here. I did however expertise some technical issues using this website, since I experienced to reload the
    website a lot of times previous to I could get it to load correctly.

    I had been wondering if your web hosting is OK? Not that I am
    complaining, but sluggish loading instances times will sometimes affect your placement in google and can damage your high-quality score if advertising and
    marketing with Adwords. Anyway I am adding this
    RSS to my e-mail and could look out for much more of your
    respective exciting content. Make sure you update this
    again soon.

  27. Excellent article. Keep posting such kind of info on your site.
    Im really impressed by your blog.
    Hey there, You have performed an incredible job. I will certainly digg it and for
    my part suggest to my friends. I’m sure they will be benefited from this web site.

  28. My brother recommended I might like this website. He was totally right.
    This post actually made my day. You cann’t imagine
    just how much time I had spent for this information! Thanks!

  29. That is really attention-grabbing, You are an excessively professional blogger.

    I have joined your rss feed and look ahead to seeking extra of your magnificent post.
    Additionally, I have shared your site in my social networks

  30. My brother suggested I might like this website. He was entirely
    right. This post truly made my day. You can not imagine simply how much time I had spent for this information! Thanks!

  31. Nice post. I used to be checking constantly this blog and I am
    impressed! Extremely useful information specifically the remaining part :
    ) I take care of such info much. I used to be seeking this certain information for a long time.
    Thank you and good luck.

  32. I used to be suggested this web site by way of my cousin. I’m no
    longer positive whether this put up is written via him
    as nobody else realize such unique approximately my difficulty.

    You’re amazing! Thank you!

  33. I’m really loving the theme/design of your web site. Do you ever run into any browser compatibility problems?
    A small number of my blog readers have complained about my site not operating correctly in Explorer
    but looks great in Safari. Do you have any ideas to help
    fix this issue?

  34. I am really loving the theme/design of your website. Do you ever run into any browser compatibility issues?
    A small number of my blog readers have complained about my website not working
    correctly in Explorer but looks great in Chrome.
    Do you have any ideas to help fix this problem?

  35. Today, while I was at work, my sister stole my iPad and tested to see if
    it can survive a forty foot drop, just so she can be a youtube sensation. My
    iPad is now broken and she has 83 views. I know this is totally off topic but I had to share it with
    someone!

  36. I was suggested this website by means of my cousin. I am now not certain whether this publish is written by way of him as no one else understand such exact approximately my problem. You are incredible! Thanks!

  37. Thanx for the effort, keep up the good work Great work, I am going to start a small Blog Engine course work using your site I hope you enjoy blogging with the popular BlogEngine.net.Thethoughts you express are really awesome. Hope you will right some more posts.

  38. I seriously love your blog.. Great colors & theme.

    Did you develop this website yourself? Please reply back as I’m attempting to create my very own website
    and want to learn where you got this from or what the theme is
    called. Appreciate it!

  39. This is a really good tip especially to those fresh to the blogosphere.

    Short but very precise information… Many thanks for sharing
    this one. A must read post!

  40. Attractive part of content. I simply stumbled upon your blog and
    in accession capital to say that I acquire actually loved
    account your weblog posts. Any way I will be subscribing on your feeds or even I achievement you
    get entry to consistently quickly.

发表评论

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