# 【BZOJ 4714】旋转排列

### 题目大意

1. 对于$\forall i \in [1,n]$ 都有$a_i \ne i$
2. 存在一个长度为$k$的序列$B$，使得$P_{B_i}=B_{i+1}$且$P_{B_k} = B_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. Thanks very nice blog!

3. bookmarked!!, I like your website!

4. 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

5. 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.

6. 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 =)

7. 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

8. 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?

9. 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.

10. Wow, this piece of writing is nice, my younger sister is analyzing such things, so I am going to convey her.

11. 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!

12. 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.

13. 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.

14. 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!

15. 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.

16. This is my first time go to see at here and i am really pleassant
to read everthing at single place.

17. 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!

18. 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.

19. I think everything said made a great deal of sense.
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.

20. 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!

21. 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

22. 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!