【BZOJ 4714】旋转排列

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4714
神犇题解:http://www.cnblogs.com/clrs97/p/6358603.html

题目大意

定义集合$A=\{1,2,\cdots,n\}$
对于$A$的任意一个排列$P$,其对于自然数$k$合法当且仅当:

  1. 对于$\forall i \in [1,n]$ 都有$a_i \ne i$
  2. 存在一个长度为$k$的序列$B$,使得$P_{B_i}=B_{i+1}$且$P_{B_k} = B_1$

定义$k=x$时$A$的合法排列数为$ans_x$,询问$\sum\limits_{i=1}^{n}{ans_i}$
由于答案可能很大,输出答案对$10^9 + 7$取模得到的结果

解题报告

我们发现,要求合法的第二个限制实际就是要求置换存在一个等于$k$的循环
于是我们对于每一个$k$,我们容斥一发,根据调和级数,这个复杂度是:$O(n \log n)$的

至于容斥的具体细节,假设我们当前钦定有$t$个长度为$k$的循环
设把$tk$个数分成$k$个循环的方案数为$g_{k,t}$
设$i$个数的错排的方案数为$d_i$
设$i$个数的环排列的方案数为$q_i$
那么这一部分的总方案数为:$g_{k,t} \cdot d_{n-kt} \cdot {{n} \choose {kt}}$

至于$q_i$怎么算?$q_i = (i-1)!$
至于$d_i$怎么算?我们可以$O(n)$预处理
至于$g_{k,t}$怎么算?我们考虑$1$所在的那个循环有哪些数,可以得到:$g_{k,t}=g_{k,t-1} \cdot d_k \cdot {{tk-1} \choose {k-1}}$

Code

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

const int N = 500009;
const int MOD = 1000000007;

int n,ans,fac[N],rev[N],q[N];

inline int C(int a, int b) {
	if (a > b || a < 0) return 0;
	else return ((LL)fac[b] * rev[a] % MOD) * rev[b-a] % MOD;
}

inline int Pow(int w, int t) {
	int ret = 1;
	for (;t;t>>=1,w=(LL)w*w%MOD)
		if (t&1) ret=(LL)ret*w%MOD;
	return ret;
}

int main() {
	fac[0] = fac[1] = q[2] = q[0] = 1; 
	for (int i=2;i<N;i++) fac[i] = (LL)fac[i-1] * i % MOD;
	rev[N-1] = Pow(fac[N-1], MOD - 2);
	for (int i=N-2;~i;i--) rev[i] = rev[i+1] * (i + 1ll) % MOD; 
	for (int i=3;i<N;i++) q[i] = (i - 1ll) * (q[i-1] + q[i-2]) % MOD;
	cin>>n;
	for (int k=2,g;g=1,k<=n;k++) {
		for (int t=1;t*k<=n;t++) {
			g = ((LL)g * C(k-1, t*k-1) % MOD) * fac[k-1] % MOD;
			ans = (ans + ((t&1)?1:-1) * ((LL)g * C(k*t, n) % MOD) * q[n - k*t]) % MOD;
		} 
	}
	printf("%d\n",(ans+MOD)%MOD);
	return 0;
}

27 thoughts to “【BZOJ 4714】旋转排列”

  1. Hey there, You’ve done a fantastic job. I’ll definitely digg it
    and personally recommend to my friends. I am sure they will be benefited from this website.

  2. Hey! This is kind of off topic but I need some help from an established blog.

    Is it hard to set up your own blog? I’m not very techincal but I can figure things out pretty
    quick. I’m thinking about creating my own but I’m not sure where
    to begin. Do you have any points or suggestions? Cheers

  3. Hello to every one, for the reason that I am genuinely eager of reading this blog’s post to be
    updated on a regular basis. It carries pleasant stuff.

  4. Terrific article! This is the kind of information that should be
    shared across the internet. Shame on Google for now not positioning this submit higher!
    Come on over and talk over with my website . Thanks =)

  5. It’s appropriate time to make some plans for the future
    and it’s time to be happy. I have read this post and if I could I wish to suggest you few interesting things or tips.

    Perhaps you could write next articles referring
    to this article. I want to read more things about it!

  6. Thank you for the auspicious writeup. It in fact was a amusement account it.
    Look advanced to more added agreeable from you! However, how could we communicate?

  7. I loved as much as you’ll receive carried out right here.

    The sketch is attractive, your authored material stylish. nonetheless, you command get bought
    an nervousness over that you wish be delivering the following.
    unwell unquestionably come more formerly again since exactly the same nearly a lot often inside case you
    shield this hike.

  8. Hello this is kinda of off topic but I was wondering if blogs
    use WYSIWYG editors or if you have to manually code with HTML.

    I’m starting a blog soon but have no coding know-how so
    I wanted to get advice from someone with experience. Any help would be enormously appreciated!

  9. Hi there would you mind sharing which blog platform you’re working with?

    I’m planning to start my own blog in the near future but
    I’m having a difficult time deciding between BlogEngine/Wordpress/B2evolution and Drupal.
    The reason I ask is because your design and style seems different then most
    blogs and I’m looking for something unique.
    P.S Sorry for getting off-topic but I had to ask!

  10. Magnificent website. A lot of helpful information here.
    I am sending it to some buddies ans additionally sharing
    in delicious. And certainly, thank you on your effort!

  11. Hi to every one, for the reason that I am genuinely keen of reading this blog’s post
    to be updated regularly. It consists of good information.

  12. I think everything said made a great deal of sense.
    However, what about this? what if you composed a catchier post title?
    I mean, I don’t wish to tell you how to run your website, however
    suppose you added a post title to maybe get folk’s attention? I mean 【BZOJ 4714】旋转排列
    – Qizy's Database is kinda vanilla.
    You should peek at Yahoo’s home page and note how they create article titles to get viewers to click.
    You might add a related video or a related pic or two to get readers interested about what you’ve written. Just my
    opinion, it could bring your blog a little livelier.

  13. Hi! Quick question that’s totally off topic. Do you know how to make your site mobile
    friendly? My site looks weird when viewing from my iphone.

    I’m trying to find a template or plugin that might be able to fix this issue.
    If you have any suggestions, please share. Appreciate it!

  14. Undeniably believe that which you said. Your favorite justification seemed to be
    on the net the easiest thing to be aware of. I say to you, I definitely get
    irked while people think about worries that they plainly
    do not know about. You managed to hit the nail upon the top as well as defined out the whole thing without having side effect ,
    people can take a signal. Will likely be back
    to get more. Thanks

  15. You really make it seem so easy with your presentation but I
    find this matter to be really something that I think I would never understand.
    It seems too complex and very broad for me.
    I’m looking forward for your next post, I will try to get the hang of it!

发表评论

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