QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#283839 | #7677. Easy Diameter Problem | Max_s_xaM | TL | 280ms | 203604kb | C++14 | 6.3kb | 2023-12-15 16:22:43 | 2023-12-15 16:22:44 |
Judging History
answer
#include <iostream>
#include <vector>
typedef long long ll;
typedef double lf;
// #define DEBUG 1
struct IO
{
#define MAXSIZE (1 << 20)
#define isdigit(x) (x >= '0' && x <= '9')
char buf[MAXSIZE], *p1, *p2;
char pbuf[MAXSIZE], *pp;
#if DEBUG
#else
IO() : p1(buf), p2(buf), pp(pbuf) {}
~IO() {fwrite(pbuf, 1, pp - pbuf, stdout);}
#endif
#define gc() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, MAXSIZE, stdin), p1 == p2) ? ' ' : *p1++)
#define blank(x) (x == ' ' || x == '\n' || x == '\r' || x == '\t')
template <typename T>
void Read(T &x)
{
#if DEBUG
std::cin >> x;
#else
bool sign = 0; char ch = gc(); x = 0;
for (; !isdigit(ch); ch = gc())
if (ch == '-') sign = 1;
for (; isdigit(ch); ch = gc()) x = x * 10 + (ch ^ 48);
if (sign) x = -x;
#endif
}
void Read(char *s)
{
#if DEBUG
std::cin >> s;
#else
char ch = gc();
for (; blank(ch); ch = gc());
for (; !blank(ch); ch = gc()) *s++ = ch;
*s = 0;
#endif
}
void Read(char &c) {for (c = gc(); blank(c); c = gc());}
void Push(const char &c)
{
#if DEBUG
putchar(c);
#else
if (pp - pbuf == MAXSIZE) fwrite(pbuf, 1, MAXSIZE, stdout), pp = pbuf;
*pp++ = c;
#endif
}
template <typename T>
void Write(T x)
{
if (x < 0) x = -x, Push('-');
static T sta[35];
int top = 0;
do sta[top++] = x % 10, x /= 10; while (x);
while (top) Push(sta[--top] ^ 48);
}
template <typename T>
void Write(T x, char lst) {Write(x), Push(lst);}
} IO;
#define Read(x) IO.Read(x)
#define Write(x, y) IO.Write(x, y)
#define Put(x) IO.Push(x)
using namespace std;
const int MAXN = 310, MAXM = 610, mod = 1e9 + 7;
int n;
vector <int> e[MAXN];
ll fac[MAXM], inv[MAXM];
inline ll C(int n, int m) {return (n < m || m < 0 ? 0 : fac[n] * inv[m] % mod * inv[n - m] % mod);}
inline ll Calc(int n, int m) {return (n == 0 || m < 0 ? 1 : C(n + m, m));}
int ev[MAXN][2], eid[MAXN][MAXN];
int dis[2][MAXN][MAXN], cnt[2][MAXN][MAXN];
int len, Mid, Midt;
void DFS(int u, int fa, int rt, bool d)
{
cnt[d][rt][dis[d][rt][u]]++;
for (auto v : e[u])
if (v != fa)
{
dis[d][rt][v] = dis[d][rt][u] + 1;
DFS(v, u, rt, d);
}
}
inline void Init()
{
fac[0] = fac[1] = inv[0] = inv[1] = 1;
for (int i = 2; i < MAXM; i++) fac[i] = fac[i - 1] * i % mod, inv[i] = (mod - mod / i) * inv[mod % i] % mod;
for (int i = 2; i < MAXM; i++) inv[i] = inv[i - 1] * inv[i] % mod;
for (int i = 1; i < n; i++)
{
for (int j = 0; j < 2; j++)
DFS(ev[i][j], ev[i][j ^ 1], i, j);
int cur = 1;
for (int j = n; j >= 0; j--)
if (cnt[0][i][j]) {cur += j; break;}
for (int j = n; j >= 0; j--)
if (cnt[1][i][j]) {cur += j; break;}
if (len < cur || (len == cur && !Mid))
{
len = cur;
if (cnt[0][i][(len - 1) / 2] && cnt[1][i][len / 2])
Mid = i, Midt = 1;
else if (cnt[1][i][(len - 1) / 2] && cnt[0][i][len / 2])
Mid = i, Midt = 0;
}
}
}
int f[MAXN][2][MAXN << 1][MAXN];
int main()
{
// freopen("cpr.in", "r", stdin);
// freopen("cpr.out", "w", stdout);
#if DEBUG
#else
ios::sync_with_stdio(0), cin.tie(0);
#endif
Read(n);
for (int i = 1, u, v; i < n; i++)
{
Read(u), Read(v);
ev[i][0] = u, ev[i][1] = v;
eid[u][v] = eid[v][u] = i;
e[u].push_back(v), e[v].push_back(u);
}
Init();
// cout << len << " " << Mid << "\n";
// for (int i = 1; i < n; i++)
// {
// for (int j = 1; j <= n; j++) cout << dis[0][i][j] << ' ';
// cout << "\n";
// for (int j = 1; j <= n; j++) cout << dis[1][i][j] << " ";
// cout << "\n\n";
// }
for (int i = 1; i < n; i++)
for (int j = 0; j < 2; j++)
for (int k = 0; k < n - 1; k++)
f[i][j][1][k] = 2;
for (int r = 2; r <= len; r++)
{
for (int i = 1; i < n; i++)
for (int j = 0; j < 2; j++)
{
if (r == len && i != Mid) continue;
int u = ev[i][j], w = ev[i][j ^ 1], Eid, Vid;
int cntw, cntu;
for (int k = 0; k < n - r; k++)
{
// cout << i << " " << j << " " << r << " " << k << " #:\n";
if (r & 1)
{
cntw = cnt[j ^ 1][i][r - 1 >> 1];
f[i][j][r][k] = (f[i][j][r][k] + (ll)f[i][j][r - 1][k + cntw] * fac[cntw]) % mod;
}
else
{
cntw = cnt[j ^ 1][i][r - 2 >> 1];
for (auto v : e[u]) if (v != w)
{
Eid = eid[v][u], Vid = (ev[Eid][1] == v);
cntu = cnt[j][i][r >> 1] - cnt[Vid][Eid][r - 2 >> 1];
// cout << Eid << " " << Vid << " " << r - 1 << " " << k << " " << cntu << " " << cntw << "\n";
f[i][j][r][k] = (f[i][j][r][k] + (ll)f[Eid][Vid][r - 1][k + cntu + cntw] * fac[cntw] % mod * fac[cntu] % mod * Calc(cntu, k + cntw)) % mod;
// cout << f[i][j][r][k] << "\n";
}
}
cntu = cnt[j][i][r >> 1];
if (!k) f[i][j][r][k] = (f[i][j][r][k] + (ll)f[i][j ^ 1][r - 1][cntu] * fac[cntu]) % mod;
else for (int m = 1; m <= cntu; m++)
f[i][j][r][k] = (f[i][j][r][k] + (ll)f[i][j ^ 1][r - 1][m] * fac[cntu] % mod * Calc(cntu - m, k - 1)) % mod;
}
}
}
// for (int r = 1; r <= len; r++, cout << "\n")
// for (int i = 1; i < n; i++, cout << "\n")
// for (int j = 0; j < 2; j++)
// for (int k = 0; k < n; k++) cout << f[i][j][r][k] << " ";
ll ans = 0;
if (len & 1) ans = f[Mid][0][len][0];
else ans = f[Mid][Midt][len][0];
cout << ans << "\n";
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 7732kb
input:
3 1 2 3 2
output:
4
result:
ok 1 number(s): "4"
Test #2:
score: 0
Accepted
time: 2ms
memory: 11860kb
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: 17984kb
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: 0
Accepted
time: 7ms
memory: 98996kb
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:
748786623
result:
ok 1 number(s): "748786623"
Test #5:
score: 0
Accepted
time: 207ms
memory: 103096kb
input:
300 109 123 221 101 229 22 114 101 110 258 50 79 26 1 238 47 140 271 77 213 140 125 19 179 111 96 194 114 57 101 1 251 19 13 92 238 114 116 193 140 153 238 1 173 252 220 1 22 124 197 196 214 196 224 1 138 201 90 184 56 266 154 71 184 46 15 256 27 1 69 1 32 22 182 237 196 111 1 279 91 139 196 114 80 ...
output:
47013557
result:
ok 1 number(s): "47013557"
Test #6:
score: 0
Accepted
time: 104ms
memory: 86480kb
input:
300 1 77 259 130 51 79 130 1 104 58 196 26 48 112 106 22 285 30 263 252 79 196 247 134 1 41 15 133 285 100 105 72 40 217 48 62 61 183 217 261 48 86 284 12 10 106 270 230 211 285 103 27 234 16 105 288 263 68 106 194 36 130 283 88 263 217 285 21 24 27 79 75 133 153 285 157 65 293 37 133 1 56 226 152 1...
output:
160857944
result:
ok 1 number(s): "160857944"
Test #7:
score: 0
Accepted
time: 177ms
memory: 97636kb
input:
300 242 149 291 91 233 192 228 231 286 224 184 156 108 138 125 50 86 223 216 209 88 1 148 264 3 72 253 164 267 87 253 35 49 150 220 232 134 110 1 149 253 132 228 9 279 150 144 138 102 39 142 1 286 66 268 219 150 91 286 15 144 153 300 286 203 3 1 275 290 149 124 298 220 48 1 225 111 136 182 133 280 1...
output:
930240562
result:
ok 1 number(s): "930240562"
Test #8:
score: 0
Accepted
time: 157ms
memory: 126184kb
input:
300 1 236 187 186 155 44 272 1 40 47 204 39 285 197 26 243 285 59 185 77 42 209 69 220 76 55 179 173 175 238 209 18 204 277 69 147 250 44 239 1 109 15 72 185 69 131 285 127 194 112 1 285 199 299 90 35 113 42 180 256 196 209 126 292 187 56 202 286 165 204 109 1 204 20 40 209 216 201 112 79 187 176 20...
output:
881450286
result:
ok 1 number(s): "881450286"
Test #9:
score: 0
Accepted
time: 198ms
memory: 134128kb
input:
300 190 298 234 90 232 25 216 110 285 102 246 234 294 171 57 18 279 163 246 188 70 47 164 94 95 101 245 58 126 70 196 58 223 285 202 245 77 1 217 25 48 51 32 270 273 99 18 27 190 83 194 79 22 108 1 25 150 209 55 18 29 164 65 1 58 12 79 80 54 154 235 268 229 49 93 51 117 257 1 3 246 228 1 177 225 33 ...
output:
41667252
result:
ok 1 number(s): "41667252"
Test #10:
score: 0
Accepted
time: 232ms
memory: 139468kb
input:
300 17 92 109 88 8 268 274 122 67 19 67 280 82 226 107 76 67 178 193 256 278 208 185 102 104 182 27 172 26 27 97 244 243 164 38 192 210 67 224 300 153 47 29 293 56 1 44 145 278 207 102 70 267 58 34 288 249 20 66 1 1 58 72 102 153 250 29 186 200 19 148 75 276 146 18 1 9 1 142 193 278 266 58 33 131 27...
output:
766720402
result:
ok 1 number(s): "766720402"
Test #11:
score: 0
Accepted
time: 242ms
memory: 144372kb
input:
300 91 264 183 296 84 43 37 244 187 89 85 243 66 230 64 57 71 172 32 283 176 190 176 269 255 18 159 283 66 232 9 202 66 222 60 172 172 290 107 208 89 290 137 239 218 47 81 29 161 110 109 171 221 67 14 236 25 155 48 298 39 254 176 280 180 66 192 113 276 155 56 273 290 43 29 289 194 124 234 266 68 35 ...
output:
50070976
result:
ok 1 number(s): "50070976"
Test #12:
score: 0
Accepted
time: 192ms
memory: 176632kb
input:
300 15 7 281 65 183 284 99 55 151 93 93 29 213 183 197 155 157 76 174 226 33 143 167 36 11 176 72 262 157 237 123 262 225 151 1 151 207 225 225 265 205 281 157 251 226 117 224 290 20 218 264 278 220 69 242 195 191 253 267 99 138 11 275 115 132 242 226 270 91 248 292 226 125 11 76 38 33 159 43 281 36...
output:
832705434
result:
ok 1 number(s): "832705434"
Test #13:
score: 0
Accepted
time: 224ms
memory: 162540kb
input:
300 164 116 141 294 26 3 135 275 28 211 287 11 217 41 162 182 238 260 53 1 242 243 205 287 1 118 155 286 41 256 199 183 42 30 235 263 45 268 22 72 228 8 98 1 5 18 119 182 16 279 4 224 64 274 152 98 90 230 299 155 1 220 134 150 219 227 151 118 70 31 70 222 27 131 217 170 57 58 253 129 118 177 121 68 ...
output:
101629452
result:
ok 1 number(s): "101629452"
Test #14:
score: 0
Accepted
time: 224ms
memory: 167228kb
input:
300 79 268 294 220 21 292 246 212 7 240 92 101 83 218 56 211 10 122 100 145 87 267 127 145 262 72 28 46 16 137 48 263 139 21 5 53 183 26 60 238 201 221 121 179 28 119 35 121 80 25 264 280 91 160 134 242 125 7 172 240 225 104 135 146 17 213 1 86 14 116 242 50 83 109 265 84 119 61 47 83 111 109 40 256...
output:
310258321
result:
ok 1 number(s): "310258321"
Test #15:
score: 0
Accepted
time: 238ms
memory: 179804kb
input:
300 192 25 131 179 181 92 56 148 237 182 117 243 67 191 124 276 109 246 74 105 78 266 240 29 20 40 223 230 8 19 179 162 273 272 212 72 27 208 235 26 226 48 273 267 136 277 210 132 231 242 172 177 18 231 33 67 22 133 189 167 239 41 68 165 67 38 280 101 233 230 88 203 61 117 54 226 274 74 118 290 185 ...
output:
453258233
result:
ok 1 number(s): "453258233"
Test #16:
score: 0
Accepted
time: 211ms
memory: 194144kb
input:
300 156 77 182 179 92 97 131 205 62 56 229 300 133 183 17 28 18 254 261 71 20 8 76 229 277 21 79 208 15 69 258 215 33 60 139 268 23 155 215 139 13 295 29 73 113 277 170 93 120 256 45 14 240 63 126 194 91 79 130 285 178 55 160 250 239 217 205 116 168 112 177 270 102 285 271 203 204 11 49 38 22 226 23...
output:
958129789
result:
ok 1 number(s): "958129789"
Test #17:
score: 0
Accepted
time: 214ms
memory: 190772kb
input:
300 119 249 283 2 56 179 44 78 151 230 192 268 97 190 113 211 63 98 208 268 280 103 138 69 129 292 201 224 272 298 164 35 122 184 252 132 195 182 109 94 209 165 35 201 247 267 107 112 210 86 112 235 72 211 257 10 141 274 217 297 272 290 286 219 8 59 118 170 276 214 127 193 203 41 256 115 27 96 185 7...
output:
140875750
result:
ok 1 number(s): "140875750"
Test #18:
score: 0
Accepted
time: 280ms
memory: 197180kb
input:
300 138 126 25 96 142 206 227 85 236 89 240 201 192 65 223 185 225 6 78 174 294 72 138 118 1 64 151 118 263 33 53 213 74 127 170 285 286 31 95 205 135 191 185 152 243 178 287 22 279 238 225 295 258 237 165 134 220 269 277 135 56 52 253 150 34 122 202 7 9 109 242 278 40 247 129 168 159 24 88 57 66 17...
output:
525372192
result:
ok 1 number(s): "525372192"
Test #19:
score: 0
Accepted
time: 222ms
memory: 199664kb
input:
300 282 97 194 58 153 187 281 262 160 224 179 25 127 123 68 63 75 156 260 163 177 101 158 255 238 56 267 96 132 122 123 265 282 29 162 58 73 59 166 116 185 9 157 191 141 81 297 255 228 216 269 177 190 175 10 114 125 244 66 79 241 30 33 176 182 44 36 128 207 241 65 124 39 38 227 68 90 291 152 268 17 ...
output:
866098103
result:
ok 1 number(s): "866098103"
Test #20:
score: 0
Accepted
time: 229ms
memory: 196828kb
input:
300 114 226 54 208 213 253 131 192 187 58 71 128 64 281 56 130 238 78 230 228 227 276 248 208 126 183 89 33 200 271 72 264 168 204 102 245 293 36 92 246 157 57 142 215 266 77 123 30 219 88 107 286 210 116 165 279 28 43 272 49 152 187 285 25 59 180 259 75 267 265 206 175 216 226 73 291 96 122 235 148...
output:
448016477
result:
ok 1 number(s): "448016477"
Test #21:
score: 0
Accepted
time: 261ms
memory: 200812kb
input:
300 200 109 91 267 131 106 186 52 216 131 277 227 80 239 86 149 222 90 220 112 219 16 48 150 69 249 82 138 42 1 209 5 195 235 291 146 56 261 141 70 12 66 244 37 55 122 33 241 174 172 295 78 288 151 254 270 298 132 60 146 97 281 12 246 144 28 8 292 121 163 242 197 261 10 278 100 120 211 278 35 28 290...
output:
997878224
result:
ok 1 number(s): "997878224"
Test #22:
score: 0
Accepted
time: 219ms
memory: 195840kb
input:
300 288 36 131 175 283 62 218 82 153 286 243 30 234 76 138 129 215 154 172 146 52 161 202 253 300 29 60 73 293 299 290 104 128 96 237 210 175 40 163 282 150 153 80 8 92 243 247 231 206 110 217 95 159 171 48 277 153 122 230 206 12 183 198 190 117 47 77 211 195 258 23 248 136 211 155 209 72 116 55 202...
output:
120554047
result:
ok 1 number(s): "120554047"
Test #23:
score: 0
Accepted
time: 260ms
memory: 200592kb
input:
300 47 46 292 281 41 8 211 141 62 272 109 265 12 217 156 294 272 298 90 73 131 244 69 149 138 45 90 46 77 67 43 246 55 108 128 148 27 20 30 210 88 121 109 143 289 42 35 4 264 131 38 111 134 239 164 241 101 141 256 68 179 135 262 127 79 31 266 251 30 157 282 77 198 115 112 10 27 250 2 298 183 184 8 2...
output:
684841907
result:
ok 1 number(s): "684841907"
Test #24:
score: 0
Accepted
time: 278ms
memory: 203604kb
input:
300 112 92 68 170 52 166 147 13 283 150 151 13 128 18 158 250 3 6 140 118 300 207 171 168 77 135 38 247 291 125 222 253 138 204 70 152 3 153 91 24 89 87 165 77 41 69 184 36 163 242 137 218 101 78 87 259 226 290 272 156 85 45 107 179 148 11 148 166 212 1 105 26 285 198 173 286 104 144 75 36 130 221 2...
output:
505448774
result:
ok 1 number(s): "505448774"
Test #25:
score: 0
Accepted
time: 280ms
memory: 201120kb
input:
300 223 291 260 121 235 126 290 285 184 99 266 294 20 85 65 208 18 125 127 146 80 118 82 169 248 66 35 160 295 171 103 91 235 238 289 29 239 81 225 23 255 140 84 71 38 224 202 181 54 72 53 300 272 258 261 139 196 15 58 46 297 204 291 237 86 43 228 206 98 185 187 123 12 65 16 97 203 113 25 104 1 184 ...
output:
727627477
result:
ok 1 number(s): "727627477"
Test #26:
score: 0
Accepted
time: 76ms
memory: 190152kb
input:
300 159 130 18 130 7 159 84 159 26 18 13 18 140 7 143 7 265 84 181 84 123 26 241 26 94 13 76 13 281 140 2 140 14 143 1 143 260 265 72 265 4 181 96 181 51 123 121 123 193 241 191 241 197 94 20 94 226 76 208 76 161 281 27 281 199 2 217 2 45 14 63 14 223 1 240 1 196 260 32 260 236 72 5 72 214 4 255 4 1...
output:
314246397
result:
ok 1 number(s): "314246397"
Test #27:
score: -100
Time Limit Exceeded
input:
300 32 172 32 33 32 187 32 193 32 194 32 294 32 86 32 24 32 218 32 266 32 147 32 199 32 137 32 114 32 123 32 126 32 188 32 168 32 281 32 175 32 221 32 48 32 288 32 254 32 212 32 81 32 278 32 75 32 64 32 141 32 245 32 215 32 255 32 185 32 277 32 92 32 236 32 182 32 161 32 227 32 54 32 35 32 184 32 79...