【日常小测】最长路径

相关链接

题目传送门:https://oi.qizy.tech/wp-content/uploads/2017/06/claris_contest_4_day2-statements.pdf
官方题解:https://oi.qizy.tech/wp-content/uploads/2017/06/claris_contest_4_day2-solutions.pdf

解题报告

首先我们要熟悉竞赛图的两个结论:

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

现在考虑把强连通分量缩成一个点,并把新点按照哈密尔顿路径排列
那么$1$号点可以到达的点数就是$1$号点所在的$SCC$的点数加上$1$号点可以到达的其他$SCC$点数和

设$f_i$为$i$个点带标号竞赛图的个数
设$g_i$为$i$个点带标号强连通竞赛图的个数
有$f_i = 2^{\frac{n(n-1)}{2}}$
又有$g_i = f_i – \sum\limits_{j = 1}^{i – 1}{{{i}\choose{j}} g_j f_{i – j}}$

于是我们枚举$1$号点所在$SCC$的点数$i$和$1$号点可到达的其他$SCC$的点数和$j$
$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);
	n = read(); MOD = read();
	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. 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?

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

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

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

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

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

  9. 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
    RSS feed to my Google account. I look forward to new updates and will talk about this blog with my Facebook group.
    Chat soon!

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

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

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

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

发表评论

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