QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#283687#7677. Easy Diameter ProblemA_programmerWA 16ms40396kbC++143.7kb2023-12-15 10:07:542023-12-15 10:07:55

Judging History

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

  • [2023-12-15 10:07:55]
  • 评测
  • 测评结果:WA
  • 用时:16ms
  • 内存:40396kb
  • [2023-12-15 10:07:54]
  • 提交

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 || !cnt[tmp.second][r]) 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;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 3ms
memory: 36948kb

input:

3
1 2
3 2

output:

4

result:

ok 1 number(s): "4"

Test #2:

score: 0
Accepted
time: 0ms
memory: 40336kb

input:

5
4 1
4 5
1 2
1 3

output:

28

result:

ok 1 number(s): "28"

Test #3:

score: 0
Accepted
time: 0ms
memory: 39544kb

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: 16ms
memory: 40396kb

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'