BZOJ5219: [Lydsy2017省队十连测]最长路径

Description

在Byteland一共有n个城市，编号依次为1到n，它们之间计划修建n(n-1)/2条单向道路，对于任意两个不同的点i和

j，在它们之间有且仅有一条单向道路，方向要么是i到j，要么是j到i。换句话说，这是一个n个点的竞赛图。Byte

asar居住在1号城市，他希望从1号城市出发，沿着单向道路不重复地访问一些城市，使得访问的城市数尽可能多。

请写一个程序，帮助Byteasar计算有多少种道路修建方式，使得从1号点出发的最长简单路径经过点数恰好为k，由

于答案可能很大，请对P取模输出

Input

第一行包含两个正整数n,P，表示点数和模数。

2≤P≤1e9,N<=2000

Output

输出n行，第i行输出从1出发的最长简单路径经过点数恰好为i的竞赛图个数模P。

Sample Input

2 233

Sample Output

1
1

HINT

Source

我们先回忆两个性质：

竞赛图缩点后拓扑序一定是链状的
竞赛图一定有哈密尔顿路

我们先算出强连通竞赛图的个数，跟连通图计数一样。然后总的点数加起来是n，由性质可以知道1可以到达它所在连通块所有的点以及它拓扑序以下的所有点，枚举1所在的连通块和它下面的点的分布是O(n^2)的。

#include<cstdio>
#define For(i, a, b) for(register int i = a; i <= b; ++i)
#define LL long long
#define int long long
using namespace std;
const int maxn = 2e3 + 5;
int C[maxn][maxn], g[maxn], ans[maxn];
int n, mod, pow2[4000005], k;

LL fpow(LL a, int b) {
	LL ans = 1;
	while(b) {
		if(b & 1) ans = ans * a % mod;
		a = a * a % mod, b >>= 1;
	}
	return ans;
}

void pre() {
	C[0][0] = 1, pow2[0] = 1;
	For(i, 1, n * n) pow2[i] = pow2[i - 1] * 2 % mod;
	For(i, 1, n) {
		C[i][0] = 1;
		For(j, 1, i)
			C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % mod;
	}
}

void Add(int & x, const int &a) {
	x += a; if(x >= mod) x -= mod;
}


signed main() {
	scanf("%lld%lld", &n, &mod);
	g[0] = g[1] = 1, pre();
	For(i, 2, n) {
		For(j, 1, i - 1)
			Add(g[i], (1ll * pow2[(i - j) * (i - j - 1) / 2] * g[j] % mod) * C[i][j] % mod);
		g[i] = (pow2[i * (i - 1) / 2] - g[i]) % mod;
	}
	For(i, 1, n) {
		For(j, 0, n - i) {
			k = n - i - j;
			ans[j + i - 1] += (((1ll * g[i] * pow2[(j - 1) * j / 2] % mod) * pow2[(k - 1) * k / 2] % mod) * C[n - 1][i - 1] % mod) * C[n - i][j] % mod;
			ans[j + i - 1] %= mod;
		}
	} 
	For(i, 0, n - 1) {
		printf("%lld\n", (ans[i] + mod) % mod);
	}
	return 0;
}

Rockdu's Blog