相关链接
题目传送门：http://oi.cyo.ng/wp-content/uploads/2017/07/NOI2017-matthew99.pdf
解题报告
从$i$向$a_i$连边
不难发现这题就是求一个基环树森林与自身同构的情况
这个我们可以用$Hash$来搞一搞
Code
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 1000009;
const int MOD = 1000000007;
const int INF = 2e9;
int n, E, ans, head[N], nxt[N], to[N];
int inv[N], pw[N], ipw[N], pw23[N], R1[N], R2[N];
int pre[N], dep[N], in[N], deg[N], vis[N];
inline int read() {
char c = getchar();
int ret = 0, f = 1;
for (; c < '0' || c > '9'; c = getchar()) {
f = c == '-'? -1: 1;
}
for (; '0' <= c && c <= '9'; c = getchar()) {
ret = ret * 10 + c - '0';
}
return ret * f;
}
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;
}
inline void AddEdge(int u, int v) {
in[v]++; deg[v]++; pre[u] = v;
to[++E] = u; nxt[E] = head[v]; head[v] = E;
}
inline void mrk(int w) {
vis[w] = 1;
if (--in[pre[w]] == 0) {
mrk(pre[w]);
}
}
inline int cal_node(int w) {
int ret = R2[deg[w]];
vector<int> arr;
for (int i = head[w]; i; i = nxt[i]) {
if (!in[to[i]]) {
dep[to[i]] = dep[w] + 1;
int tmp = cal_node(to[i]);
arr.push_back(tmp);
ret = (ret + (LL)R1[dep[w]] * tmp) % MOD;
}
}
sort(arr.begin(), arr.end());
for (int i = 0, j = 0; i < (int)arr.size(); i = j + 1) {
for (; j + 1 < (int)arr.size() && arr[i] == arr[j + 1]; ++j);
ans = (LL)ans * ipw[j - i + 1] % MOD;
}
return (LL)ret * ret % MOD;
}
inline int cal_cir(int w) {
vector<int> node, arr;
while (!vis[w]) {
vis[w] = 1;
node.push_back(w);
for (int i = head[w]; i; i = nxt[i]) {
if (in[to[i]]) {
w = to[i];
break;
}
}
}
for (int i = 0; i < (int)node.size(); i++) {
dep[node[i]] = 6;
arr.push_back(cal_node(node[i]));
}
int sta = 0, cnt = 1;
for (int i = 0; i < (int)node.size(); i++) {
sta = (sta + (LL)pw23[i] * arr[i]) % MOD;
}
int ret = (LL)sta * pw23[n] % MOD;
for (int i = 1, cur = sta; i < (int)node.size(); i++) {
cur = (cur + (LL)arr[i - 1] * (pw23[i - 1 + node.size()] - pw23[i - 1])) % MOD;
ret = min(ret, int((LL)cur * pw23[n - i] % MOD));
cnt += ((cur = (cur + MOD) % MOD) == (LL)sta * pw23[i] % MOD);
}
ans = (LL)ans * inv[cnt] % MOD;
return ret;
}
int main() {
srand(19991216);
inv[0] = pw[0] = ipw[0] = pw23[0] = 1;
R1[0] = rand(); R2[0] = rand();
for (int i = 1; i < N; i++) {
pw[i] = (LL)pw[i - 1] * i % MOD;
pw23[i] = pw23[i - 1] * 131ll % MOD;
inv[i] = Pow(i, MOD - 2);
ipw[i] = Pow(pw[i], MOD - 2);
R1[i] = rand(); R2[i] = rand();
}
for (int T = read(); T; T--) {
memset(head, 0, sizeof(head));
memset(deg, 0, sizeof(deg));
memset(vis, 0, sizeof(vis));
memset(in, 0, sizeof(in));
E = 0; ans = 1;
n = read();
for (int i = 1; i <= n; i++) {
AddEdge(i, read());
}
for (int i = 1; i <= n; i++) {
if (!in[i] && !vis[i]) {
mrk(i);
}
}
vector<int> arr;
for (int i = 1; i <= n; i++) {
if (in[i] && !vis[i]) {
arr.push_back(cal_cir(i));
}
}
sort(arr.begin(), arr.end());
for (int i = 0, j = 0; i < (int)arr.size(); i = j + 1) {
for (; j + 1 < (int)arr.size() && arr[i] == arr[j + 1]; ++j);
ans = (LL)ans * ipw[j - i + 1] % MOD;
}
ans = ((LL)ans * pw[n] - 1) % MOD;
printf("%d\n", (ans + MOD) % MOD);
}
return 0;
}
I’m gone to say to my little brother, that he should also visit this blog on regular basis to
take updated from most up-to-date news update.
What’s up, this weekend is pleasant in support of me, as
this occasion i am reading this wonderful informative paragraph here at
my residence.
I like the helpful info you supply for your articles.
I’ll bookmark your weblog and check again here regularly.
I am rather certain I’ll learn lots of new stuff proper right here!
Best of luck for the following!
I was able to find good advice from your blog posts.
Thanks for one’s marvelous posting! I definitely enjoyed reading it, you are a great author.I will always bookmark your blog and definitely
will come back very soon. I want to encourage yourself to continue your great work, have a nice weekend!
My spouse and I stumbled over here from 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 looking
into your web page yet again.
Hello very cool website!! Guy .. Excellent ..
Wonderful .. I’ll bookmark your site and take the feeds also?
I’m satisfied to search out numerous helpful info right here in the submit,
we need develop extra techniques on this regard, thanks for sharing.
. . . . .
Hello to every body, it’s my first go to see of this
website; this webpage consists of remarkable and genuinely fine information designed for readers.
It’s actually a great and helpful piece of information. I’m happy that you simply shared this useful info with us.
Please stay us informed like this. Thank you for sharing.
Hey There. I found your weblog using msn. That is a really smartly written article.
I will be sure to bookmark it and return to learn more of your useful info.
Thanks for the post. I will definitely comeback.
Thanks for the auspicious writeup. It in fact used to be a leisure account it.
Glance advanced to far introduced agreeable from you! By the way, how can we keep up a correspondence?
Excellent blog you have here but I was wanting to
know if you knew of any forums that cover the same topics talked about in this article?
I’d really like to be a part of community where I can get
feed-back from other experienced people that share
the same interest. If you have any recommendations, please let me know.
Thanks a lot!
Post writing is also a fun, if you be familiar with after that you can write otherwise it is complicated to write.
I’ve been exploring for a little for any high-quality articles or blog posts on this sort of area . Exploring in Yahoo I at last stumbled upon this site. Reading this information So i am happy to convey that I have a very good uncanny feeling I discovered exactly what I needed. I most certainly will make certain to do not forget this web site and give it a look on a constant basis.
It is not my first time to go to see this web site, i
am visiting this website dailly and get pleasant data from here every day.
Does your blog have a contact page? I’m having a tough time locating it but, I’d
like to send you an email. I’ve got some suggestions for your blog
you might be interested in hearing. Either
way, great site and I look forward to seeing it expand over time.
It’s actually a nice and helpful piece of info.
I’m glad that you simply shared this helpful
info with us. Please keep us informed like this. Thanks for sharing.
Thanks for finally writing about >【日常小测】学外语 – Qizy’s Database <Liked it!
What’s up, every time i used to check webpage posts here in the early hours in the morning, as i enjoy to find
out more and more.
These are in fact enormous ideas in concerning blogging.
You have touched some good things here. Any way keep up
wrinting.
The info is very fascinating.|
Hi there colleagues, its enormous paragraph about cultureand entirely defined,
keep it up all the time.
At this time I am ready to do my breakfast, afterward having my
breakfast coming again to read additional news.
Very rapidly this website will be famous among all blog visitors, due to it’s pleasant articles or reviews
Hey there! I just want to offer you a big thumbs up for your excellent information you’ve got right here on this post.
I’ll be returning to your website for more soon.
You actually make it appear so easy along with your presentation however I to find this topic to be really something which I think I might by no means understand. It kind of feels too complicated and extremely broad for me. I am having a look forward for your subsequent publish, I will attempt to get the hang of it!