相关链接
题目传送门: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$合法当且仅当:
- 对于$\forall i \in [1,n]$ 都有$a_i \ne i$
- 存在一个长度为$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; }
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.
Thanks very nice blog!
bookmarked!!, I like your website!
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
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.
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 =)
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!
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?
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.
Wow, this piece of writing is nice, my younger sister is analyzing such things, so I am going to convey her.
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!
Thanks very nice blog!
Hello everyone, it’s my first visit at this site, and piece of writing is actually fruitful designed for me, keep up posting such articles.
Useful info. Lucky me I found your web site unintentionally, and I am surprised why this twist of fate didn’t came about in advance! I bookmarked it.
Someone essentially help to make critically articles I might state.
This is the first time I frequented your website page and so
far? I amazed with the research you made to create this particular put up amazing.
Excellent job!
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!
Thanks very interesting blog!
This is my first time go to see at here and i am really pleassant
to read everthing at single place.
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!
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.
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.
Thanks very interesting blog!
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!
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
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!
I have read so many articles or reviews about
the blogger lovers however this article
is actually a nice paragraph, keep it up.
Excellent website. Plenty of useful info here. I am sending it to several buddies ans also sharing in delicious. And of course, thanks to your sweat!