QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#283686#7677. Easy Diameter ProblemA_programmerWA 19ms38496kbC++143.6kb2023-12-15 10:04:142023-12-15 10:04:14

Judging History

你现在查看的是最新测评结果

  • [2023-12-15 10:04:14]
  • 评测
  • 测评结果:WA
  • 用时:19ms
  • 内存:38496kb
  • [2023-12-15 10:04:14]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
const ll mod = 998244353;

int n, len, Mid;
int U[305], V[305], cnt[1205][305], dis[605][605];
ll dp[2][1205][305], fac[2005], C[2005][2005];
vector<pii> g[605];

void precalc(int x)
{
	fac[0] = C[0][0] = 1;
	for (int i = 1; i <= x; i++)
	{
		fac[i] = fac[i - 1] * i % mod;
		C[i][0] = C[i][i] = 1;
		for (int j = 1; j < i; j++) C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % mod;
	}
}
ll Ch(int n, int m) { return C[n + m - 1][n - 1]; } //n个盒子,填m个数,可空 

void calc(int u, int fu, int id)
{
	for (pii tmp : g[u])
	{
		int v = tmp.first;
		if (v == fu) continue;
		dis[id][v] = dis[id][u] + 1;
		calc(v, u, id);
	}
}

void travel(int st, int u, int fu, int dep)
{
	cnt[st][dep]++;
	for (pii tmp : g[u])
	{
		int v = tmp.first;
		if (v == fu) continue;
		travel(st, v, u, dep + 1);
	}
}

void init()
{
	for (int i = 1; i <= 2 * n - 1; i++) calc(i, 0, i);
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			if (dis[i][j] > len)
			{
				len = dis[i][j];
				for (int k = 1; k < 2 * n; k++)
					if (dis[i][j] == dis[i][k] + dis[k][j] && dis[i][k] == dis[k][j])
					{
						Mid = k;
						break;
					}
			}
	len >>= 1; 
	
	for (int i = 1; i <= n - 1; i++)
	{
		travel(4 * (i - 1), V[i], i + n, 0);
		travel(4 * (i - 1) + 1, U[i], i + n, 0);
		travel(4 * (i - 1) + 2, i + n, U[i], 0);
		travel(4 * (i - 1) + 3, i + n, V[i], 0);
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	cin >> n;
	for (int i = 1; i < n; i++)
	{
		int u, v;
		cin >> U[i] >> V[i], u = U[i], v = V[i];
		g[v].emplace_back(make_pair(i + n, 4 * (i - 1)));
		g[u].emplace_back(make_pair(i + n, 4 * (i - 1) + 1));
		g[i + n].emplace_back(make_pair(u, 4 * (i - 1) + 2));
		g[i + n].emplace_back(make_pair(v, 4 * (i - 1) + 3));
	}
	precalc(2000);
	init();
	
	int p = 0;
	for (pii tmp : g[Mid]) dp[p][tmp.second][cnt[tmp.second][len]] = fac[cnt[tmp.second][len]];
	for (int r = len - 1; r; r--, p ^= 1)
	{
		memset(dp[p ^ 1], 0, sizeof(dp[p ^ 1]));
		for (int st = 0; st < 4 * (n - 1); st++)
		{
			int id = st / 4 + 1, ls, nw, op;
			if (st % 4 == 0) nw = id + n, ls = V[id], op = 0;
			else if (st % 4 == 1) nw = id + n, ls = U[id], op = 0;
			else if (st % 4 == 2) nw = U[id], ls = id + n, op = 1;
			else nw = V[id], ls = id + n, op = 1;
			
			//转移1:反复横跳。此时枚举删去点数m作为新的可插入长度,剩下的直接插入前面即可。
			//组合数:(cnt排列) * (cnt-m个插入l) 
			int nst = 4 * (id - 1) + 3 - (st % 4);
			for (int l = 1; l <= n; l++)
				for (int m = 1; m <= cnt[nst][r]; m++)
					(dp[p ^ 1][nst][m] += dp[p][st][l] * Ch(l, cnt[nst][r] - m) % mod * fac[cnt[nst][r]] % mod) %= mod;
			
			//转移2:继续向前。此时之前的点数直接并入l,作为新的可插入长度。
			//组合数:(u点数排列) * (去u去v点数排列) * (去u去v点数插入l+1) 
			for (int l = 1; l <= n; l++)
				for (pii tmp : g[nw])
				{
					int v = tmp.first;
					if (v == ls) continue;
					int t1 = cnt[st][r - 1];
					int t2 = cnt[tmp.second][r] - cnt[st][r - 1];
					if (l + t1 + t2 > n) continue;
					(dp[p ^ 1][tmp.second][l + t1 + t2] += dp[p][st][l] * fac[t1] % mod * fac[t2] % mod * Ch(l + t1 + 1, t2) % mod) %= mod;
				}
		}
//		for (int st = 0; st < 4 * (n - 1); st++, cout << "\n")
//			for (int l = 1; l <= n; l++) cout << dp[p ^ 1][st][l] << " ";
//		cout << "\n";
	}
	
	ll ans = 0;
	for (int st = 0; st < 4 * (n - 1); st++)
		for (int l = 1; l <= n; l++) (ans += dp[p][st][l]) % mod;
	cout << ans;
	return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 4ms
memory: 36396kb

input:

3
1 2
3 2

output:

4

result:

ok 1 number(s): "4"

Test #2:

score: 0
Accepted
time: 6ms
memory: 37660kb

input:

5
4 1
4 5
1 2
1 3

output:

28

result:

ok 1 number(s): "28"

Test #3:

score: 0
Accepted
time: 3ms
memory: 37440kb

input:

7
5 7
2 5
2 1
1 6
3 6
4 1

output:

116

result:

ok 1 number(s): "116"

Test #4:

score: -100
Wrong Answer
time: 19ms
memory: 38496kb

input:

100
89 60
66 37
59 74
63 49
69 37
9 44
94 22
70 30
79 14
25 33
23 4
78 43
63 30
95 7
6 59
56 31
21 56
58 43
95 28
81 19
63 40
58 87
81 38
100 55
78 23
37 78
86 70
33 11
52 17
42 19
19 13
70 100
97 79
66 67
66 27
82 55
15 27
68 33
97 26
46 20
70 93
1 10
69 79
81 45
58 95
24 63
79 51
85 11
12 43
41 64...

output:

2795647739182

result:

wrong answer 1st numbers differ - expected: '748786623', found: '2795647739182'