BZOJ5219: [Lydsy2017省队十连测]最长路径
? 解题记录 ? ? BZOJ ? ? 动态规划 ? ? 组合数 ?    2018-09-25 08:31:27    835    0    0

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

Claris原创,本站版权所有

我们先回忆两个性质:

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

我们先算出强连通竞赛图的个数,跟连通图计数一样。然后总的点数加起来是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;
}

 

上一篇: BZOJ5228: [Lydsy2017省队十连测]Bounce

下一篇: BZOJ5218: [Lydsy2017省队十连测]友好城市

835 人读过
立即登录, 发表评论.
没有帐号? 立即注册
0 条评论
文档导航