暴力都打不出来,交也没交,光荣爆0
A Expectation (Unaccepted)
题目大意 :
- 咕咕
Code
Show Code
B Sequence (Unaccepted)
题目大意 :
- 咕咕
Code
Show Code
C Counting
题目大意 : 给出n个点,加E条不同的有向边,没加一条记录下强联通分量个数,组成一个序列,问有多少种这样的序列
- 考虑最优策略一定是 1,2,...,i 连一个大环,后面全是单独的强连通分量,那么可行的边数不超过 frac{n(n-1)+i(i-1)}{2}
Code
Show Code
#include <cstdio>
using namespace std;
const int N = 105, M = 998244353;
int f[N*N][N][N], s[N*N][N][N], n;
//f[e][i][j] : 用了e条边,1所在的scc大小为i,反向连了j条边的方案数
//s[e][i][j] : f[e][1][j] - f[e][i][j] 的和
int main() {
scanf("%d", &n); f[0][1][0] = 1;
for (int i = 1; i <= n; ++i) s[0][i][0] = 1;
int lim = n * (n - 1);
for (int e = 1; e <= lim; ++e) {
for (int i = 1; i <= n; ++i) {
for (int j = 0; j < i; ++j) {
if (e >= i + j - 1 && e <= i * (i - 1) + (n - i) * (n - i - 1) / 2 + i * (n - i))
f[e][i][j] = (f[e-1][i][j] + s[e-1][i-1][j-1]) % M;
s[e][i][j] = (s[e][i-1][j] + f[e][i][j]) % M;
}
}
}
for (int i = 1; i <= lim; ++i) {
int ans = 0;
for (int j = 0; j < n; ++j)
if ((ans += s[i][n][j]) >= M) ans -= M;
printf("%d ", ans);
}
return 0;
}