# 【日常小测】最长路径

### 解题报告

1. 任意一个竞赛图一定存在哈密尔顿路径
2. 一个竞赛图存在哈密尔顿回路当且仅当这个竞赛图强连通

$ans_{x} = \sum\limits_{i = 1}^{x}{{{n – 1}\choose{i – 1}} g_i {{n – i}\choose{x – i}} f_{x – i} f_{n – x}}$

### Code

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

const int N = 2009;

int n, MOD, f[N], g[N], pw[N * N], C[N][N];

inline int read() {
char c = getchar();
int ret = 0, f = 1;
while (c < '0' || c > '9') {
f = c == '-'? -1: 1;
c = getchar();
}
while ('0' <= c && c <= '9') {
ret = ret * 10 + c - '0';
c = getchar();
}
return ret * f;
}

int main() {
freopen("path.in", "r", stdin);
freopen("path.out", "w", stdout);
pw[0] = 1;
for (int i = 1; i < n * n; i++) {
pw[i] = (pw[i - 1] << 1) % MOD;
}
C[0][0] = 1;
for (int i = 1; i <= n; ++i) {
C[i][0] = 1;
for (int j = 1; j <= n; j++) {
C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % MOD;
}
}
f[0] = g[0] = 1;
for (int i = 1; i <= n; i++) {
f[i] = g[i] = pw[i * (i - 1) >> 1];
for (int j = 1; j < i; j++) {
g[i] = (g[i] - (LL)C[i][j] * g[j] % MOD * f[i - j]) % MOD;
}
}
for (int x = 1; x <= n; x++) {
int ans = 0;
for (int i = 1; i <= x; i++) {
ans = (ans + (LL)C[n - 1][i - 1] * g[i] % MOD * C[n - i][x - i] % MOD * f[x - i] % MOD * f[n - x]) % MOD;
}
printf("%d\n", ans > 0? ans: ans + MOD);
}
return 0;
}


## 21 thoughts to “【日常小测】最长路径”

1. whoah this weblog is magnificent i like reading your articles.
Keep up the great work! You understand, many persons are looking round for this information, you could help
them greatly.

2. Woah! I’m really loving the template/theme of this website.
It’s simple, yet effective. A lot of times it’s hard to get that “perfect balance” between superb usability and visual appearance.
I must say you’ve done a very good job with this. Also, the blog loads extremely quick for me on Internet explorer.
Exceptional Blog!

3. What’s up, its good piece of writing about media print, we all understand media
is a wonderful source of facts.

4. I needed to thank you for this excellent read!!

I certainly loved every bit of it. I have got you
book-marked to look at new stuff you post…

5. Thank you for the good writeup. It in fact was a amusement account it.
Look advanced to far added agreeable from you! By the way, how could we communicate?

6. Greetings, I believe your web site could be having web browser compatibility problems.
Whenever I take a look at your blog in Safari,
it looks fine however when opening in I.E., it has some overlapping issues.
I simply wanted to provide you with a quick heads up!

Besides that, excellent site!

7. Its like you read my mind! You seem to know so much about this, like you wrote the book in it or something. I think that you could do with a few pics to drive the message home a little bit, but instead of that, this is excellent blog. A fantastic read. I will certainly be back.

8. Outstanding quest there. What happened after?
Thanks!

9. Hello, i think that i saw you visited my weblog so i came to “return the favor”.I
am trying to find things to improve my web site!I suppose its ok to use a few of your
ideas!!

10. Attractive section of content. I just stumbled upon your weblog and in accession capital to assert that
I acquire in fact enjoyed account your blog posts. Anyway I’ll be subscribing to your feeds
and even I achievement you access consistently rapidly.

11. I was recommended this blog by my cousin. I’m no longer certain whether or not this
publish is written by way of him as no one
else know such certain about my trouble. You’re incredible!
Thanks!

12. Great post. I was checking continuously this weblog and I’m inspired!
Extremely helpful information specially the ultimate part :
) I handle such information much. I used to be looking for this particular info for a long time.
Thank you and best of luck.

13. We are a group of volunteers and starting a new scheme in our community.
Your web site provided us with valuable information to work
on. You’ve done an impressive job and our entire community will be thankful to you.

14. It’s a pity you don’t have a donate button! I’d most certainly donate to this fantastic blog!
I suppose for now i’ll settle for book-marking and adding your
Chat soon!

15. Quality posts is the key to be a focus for the visitors to visit
the site, that’s what this site is providing.

16. First of all I would like to say fantastic blog! I had a quick question that I’d like to ask
if you do not mind. I was interested to find out how you
center yourself and clear your thoughts prior to writing.
I have had a hard time clearing my thoughts in getting my thoughts out there.
I truly do enjoy writing but it just seems like the first 10 to 15
minutes tend to be lost simply just trying to figure out how to begin. Any ideas or tips?
Appreciate it!

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

18. This post is invaluable. Where can I find out more?

19. Howdy, i read your blog occasionally and i own a similar one and i was just curious if you get a lot of
spam responses? If so how do you protect against it, any plugin or anything you can suggest?
I get so much lately it’s driving me crazy so any support is very much appreciated.

20. Woah! I’m really digging the template/theme of this website.
It’s simple, yet effective. A lot of times it’s hard
to get that “perfect balance” between usability and visual appearance.
I must say you have done a excellent job with this.
In addition, the blog loads very fast for me on Chrome. Excellent Blog!

21. Perfect work you have done, this internet site is really cool with fantastic information.