BZOJ5219: [Lydsy2017省队十连测]最长路径
? 解题记录 ? ? BZOJ ? ? 动态规划 ? ? 组合数 ?    2018-09-25 08:31:27    843    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)的。

  1. #include<cstdio>
  2. #define For(i, a, b) for(register int i = a; i <= b; ++i)
  3. #define LL long long
  4. #define int long long
  5. using namespace std;
  6. const int maxn = 2e3 + 5;
  7. int C[maxn][maxn], g[maxn], ans[maxn];
  8. int n, mod, pow2[4000005], k;
  9.  
  10. LL fpow(LL a, int b) {
  11. LL ans = 1;
  12. while(b) {
  13. if(& 1) ans = ans * a % mod;
  14. = a * a % mod, b >>= 1;
  15. }
  16. return ans;
  17. }
  18.  
  19. void pre() {
  20. C[0][0] = 1, pow2[0] = 1;
  21. For(i, 1, n * n) pow2[i] = pow2[- 1] * 2 % mod;
  22. For(i, 1, n) {
  23. C[i][0] = 1;
  24. For(j, 1, i)
  25. C[i][j] = (C[- 1][j] + C[- 1][- 1]) % mod;
  26. }
  27. }
  28.  
  29. void Add(int & x, const int &a) {
  30. += a; if(>= mod) x -= mod;
  31. }
  32.  
  33.  
  34. signed main() {
  35. scanf("%lld%lld", &n, &mod);
  36. g[0] = g[1] = 1, pre();
  37. For(i, 2, n) {
  38. For(j, 1, i - 1)
  39. Add(g[i], (1ll * pow2[(- j) * (- j - 1) / 2] * g[j] % mod) * C[i][j] % mod);
  40. g[i] = (pow2[* (- 1) / 2] - g[i]) % mod;
  41. }
  42. For(i, 1, n) {
  43. For(j, 0, n - i) {
  44. = n - i - j;
  45. ans[+ i - 1] += (((1ll * g[i] * pow2[(- 1) * j / 2] % mod) * pow2[(- 1) * k / 2] % mod) * C[- 1][- 1] % mod) * C[- i][j] % mod;
  46. ans[+ i - 1] %= mod;
  47. }
  48. } 
  49. For(i, 0, n - 1) {
  50. printf("%lld\n", (ans[i] + mod) % mod);
  51. }
  52. return 0;
  53. }

 

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

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

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