The Preliminary Contest for ICPC Asia Shanghai 2019

A	B	C	D	E	F	G	H	I	J	K	L
补	sineMora	cycleke	cycleke	补	OwenCreeper	补	.	.	sineMora	x	cycleke

这次网络赛中途出现了一些策略上的失误，中途全队都在查 F 代码，还在 E 上花了太长的时间，没有及时弃掉。

这里写一下我做（补）的题的简要题解。

A.Lightning Routing I

题意：给出一棵带边权树，每次修改一条边权或者询问距离一个点最远点的距离。

通过 bfs 寻找树直径的算法可以知道，距离每个点最远的点一定是直径的一个端点，之后就是动态维护树的直径。可以参考CEOI2019 / CodeForces 1192B. Dynamic Diameter。

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171


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

typedef long long ll;
typedef pair<int, int> pii;
typedef tuple<int, int, int> tiii;

const int MAXN = 1e5 + 5;

int n, q;
tiii edges[MAXN];

namespace BIT {
ll tree[MAXN];

void add(int x, const int &val) {
  for (; x <= n; x += x & -x) tree[x] += val;
}
void add(int l, int r, const int &val) { add(l, val), add(r + 1, -val); }

ll ask(int x) {
  ll res = 0;
  for (; x; x &= x - 1) res += tree[x];
  return res;
}
} // namespace BIT

namespace tcs {

int size[MAXN], son[MAXN], fa[MAXN], top[MAXN], dep[MAXN], val[MAXN];
int in[MAXN], out[MAXN], idx[MAXN], dfs_c;
vector<pii> adj[MAXN];

void cal_son(int u) {
  son[u] = 0;
  size[u] = 1;
  for (pii &e : adj[u]) {
    int v = e.first;
    if (v == fa[u]) continue;
    fa[v] = u;
    dep[v] = dep[u] + 1;
    val[v] = e.second;
    cal_son(v);
    if (size[v] > size[son[u]]) son[u] = v;
    size[u] += size[v];
  }
}

void cal_top(int u, int anc) {
  top[u] = anc;
  idx[in[u] = ++dfs_c] = u;

  if (son[u]) {
    cal_top(son[u], anc);
    BIT::add(in[son[u]], out[son[u]], val[son[u]]);
    for (pii &e : adj[u])
      if (e.first != son[u] && e.first != fa[u]) {
        cal_top(e.first, e.first);
        BIT::add(in[e.first], out[e.first], val[e.first]);
      }
  }
  out[u] = dfs_c;
}

void init() {
  cal_son(1);
  cal_top(1, 1);
}

int lca(int u, int v) {
  while (top[u] ^ top[v]) {
    if (dep[top[u]] < dep[top[v]]) swap(u, v);
    u = fa[top[u]];
  }
  return dep[u] < dep[v] ? u : v;
}

ll dist(int u, int v) {
  int g = lca(u, v);
  return BIT::ask(in[u]) + BIT::ask(in[v]) - 2 * BIT::ask(in[g]);
}
} // namespace tcs

namespace SGT {
struct Node {
  int u, v;
  ll d;
  Node *left, *right;

  void change(int _u, int _v, ll _d) { u = _u, v = _v, d = _d; }
  void change(int _u, int _v) {
    ll _d = tcs::dist(_u, _v);
    if (_d > d) change(_u, _v, _d);
  }
  void change(Node *a) { change(a->u, a->v, a->d); }
} node_pool[MAXN * 2], *node_it, *root;

void maintain(Node *u) {
  if (u->left->d > u->right->d) {
    u->change(u->left);
  } else {
    u->change(u->right);
  }
  int a = u->left->u, b = u->left->v;
  int c = u->right->u, d = u->right->v;
  u->change(a, c), u->change(a, d);
  u->change(b, c), u->change(b, d);
}

void build(Node *&u, int l, int r) {
  u = node_it++;
  if (l == r) {
    *u = (Node){tcs::idx[l], tcs::idx[l], 0, NULL, NULL};
    return;
  }
  int mid = (l + r) >> 1;
  build(u->left, l, mid);
  build(u->right, mid + 1, r);
  maintain(u);
}

void init() {
  node_it = node_pool;
  build(root, 1, n);
}

void update(Node *u, int l, int r, const int &x, const int &y) {
  if (x <= l && r <= y) return;
  int mid = (l + r) >> 1;
  if (x <= mid) update(u->left, l, mid, x, y);
  if (y > mid) update(u->right, mid + 1, r, x, y);
  maintain(u);
}

} // namespace SGT

int main() {
  // freopen("a.in", "r", stdin);
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  cin >> n;
  for (int i = 1, u, v, w; i < n; ++i) {
    cin >> u >> v >> w;
    tcs::adj[u].emplace_back(v, w);
    tcs::adj[v].emplace_back(u, w);
    edges[i] = (tiii){u, v, w};
  }

  tcs::init();
  SGT::init();

  cin >> q;
  char op[3];
  for (int id, _w, u, v, w, p1 = SGT::root->u, p2 = SGT::root->v; q; --q) {
    cin >> op;
    if (*op == 'Q') {
      cin >> u;
      cout << max(tcs::dist(p1, u), tcs::dist(p2, u)) << '\n';
    } else {
      cin >> id >> _w;
      tie(u, v, w) = edges[id];
      if (tcs::dep[u] > tcs::dep[v]) swap(u, v);
      BIT::add(tcs::in[v], tcs::out[v], _w - w);
      SGT::update(SGT::root, 1, n, tcs::in[v], tcs::out[v]);
      p1 = SGT::root->u, p2 = SGT::root->v;
      edges[id] = (tiii){u, v, _w};
    }
  }
  return 0;
}

C.Triple

考虑到不满足的三元组，有$A_i+B_j < C_k$或$B_i+C_k < A_i$或$A_i+C_k < B_j$。这是一个经典的 FFT 题目。注意，由于至多有 20 组 n 超过 1000，而最多有 100 组，所以可以在小数据跑暴力，大数据跑 FFT，避免 FFT 大常数。

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216


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

namespace FastIO {
struct Control {
  int ct, val;
  Control(int Ct, int Val = -1) : ct(Ct), val(Val) {}
  inline Control operator()(int Val) { return Control(ct, Val); }
} _endl(0), _prs(1), _setprecision(2);

const int IO_SIZE = 1 << 16 | 127;

struct FastIO {
  char in[IO_SIZE], *p, *pp, out[IO_SIZE], *q, *qq, ch[20], *t, b, K, prs;
  FastIO() : p(in), pp(in), q(out), qq(out + IO_SIZE), t(ch), b(1), K(6) {}
  ~FastIO() { fwrite(out, 1, q - out, stdout); }
  inline char getc() {
    return p == pp && (pp = (p = in) + fread(in, 1, IO_SIZE, stdin), p == pp)
               ? (b = 0, EOF)
               : *p++;
  }
  inline void putc(char x) {
    q == qq && (fwrite(out, 1, q - out, stdout), q = out), *q++ = x;
  }
  inline void puts(const char str[]) {
    fwrite(out, 1, q - out, stdout), fwrite(str, 1, strlen(str), stdout),
        q = out;
  }
  inline void getline(string &s) {
    s = "";
    for (char ch; (ch = getc()) != '\n' && b;) s += ch;
  }
#define indef(T)                                                               \
  inline FastIO &operator>>(T &x) {                                            \
    x = 0;                                                                     \
    char f = 0, ch;                                                            \
    while (!isdigit(ch = getc()) && b) f |= ch == '-';                         \
    while (isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = getc();      \
    return x = f ? -x : x, *this;                                              \
  }
  indef(int);
  indef(long long);

  inline FastIO &operator>>(string &s) {
    s = "";
    char ch;
    while (isspace(ch = getc()) && b) {}
    while (!isspace(ch) && b) s += ch, ch = getc();
    return *this;
  }
  inline FastIO &operator>>(double &x) {
    x = 0;
    char f = 0, ch;
    double d = 0.1;
    while (!isdigit(ch = getc()) && b) f |= (ch == '-');
    while (isdigit(ch)) x = x * 10 + (ch ^ 48), ch = getc();
    if (ch == '.')
      while (isdigit(ch = getc())) x += d * (ch ^ 48), d *= 0.1;
    return x = f ? -x : x, *this;
  }
#define outdef(_T)                                                             \
  inline FastIO &operator<<(_T x) {                                            \
    !x && (putc('0'), 0), x < 0 && (putc('-'), x = -x);                        \
    while (x) *t++ = x % 10 + 48, x /= 10;                                     \
    while (t != ch) *q++ = *--t;                                               \
    return *this;                                                              \
  }
  outdef(int);
  outdef(long long);
  inline FastIO &operator<<(char ch) { return putc(ch), *this; }
  inline FastIO &operator<<(const char str[]) { return puts(str), *this; }
  inline FastIO &operator<<(const string &s) { return puts(s.c_str()), *this; }
  inline FastIO &operator<<(double x) {
    int k = 0;
    this->operator<<(int(x));
    putc('.');
    x -= int(x);
    prs && (x += 5 * pow(10, -K - 1));
    while (k < K) putc(int(x *= 10) ^ 48), x -= int(x), ++k;
    return *this;
  }
  inline FastIO &operator<<(const Control &cl) {
    switch (cl.ct) {
    case 0: putc('\n'); break;
    case 1: prs = cl.val; break;
    case 2: K = cl.val; break;
    }
    return *this;
  }
  inline operator bool() { return b; }
};
} // namespace FastIO

FastIO::FastIO io;

const int MAXN = 1e5 + 5;

int n, A[MAXN], B[MAXN], C[MAXN], rev[MAXN * 4];

const double PI = acos(-1);

inline void fft(complex<double> *a, int sign, int n, int bit) {
  for (int i = 0; i < n; ++i)
    if (i < rev[i]) swap(a[i], a[rev[i]]);

  for (int j = 1; j < n; j <<= 1) {
    complex<double> wn(cos(2 * PI / (j << 1)), sign * sin(2 * PI / (j << 1)));
    for (int i = 0; i < n; i += (j << 1)) {
      complex<double> w(1, 0), t0, t1;
      for (int k = 0; k < j; ++k) {
        t0 = a[i + k];
        t1 = w * a[i + j + k];
        a[i + k] = t0 + t1;
        a[i + j + k] = t0 - t1;
        w *= wn;
      }
    }
  }
  if (sign == -1)
    for (int i = 0; i < n; ++i) a[i] /= n;
}

inline void gao_big(int *A, int *B, int *C, long long &ans) {
  static int max_a, max_b, bit, nn;
  static long long cnt[MAXN];
  static complex<double> a[MAXN * 4], b[MAXN * 4];
  nn = 1, bit = 0;
  max_a = max_b = -1;
  for (int i = 0; i < n; ++i)
    if (max_a < A[i]) max_a = A[i];
  for (int i = 0; i < n; ++i)
    if (max_b < B[i]) max_b = B[i];
  while (nn <= max_a + max_b) nn <<= 1, ++bit;
  rev[0] = 0;
  for (int i = 1; i < nn; ++i)
    rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (bit - 1));

  for (int i = 0; i < nn; ++i) a[i] = b[i] = complex<double>(0, 0);
  for (int i = 0; i < n; ++i) {
    a[A[i]].real(a[A[i]].real() + 1);
    b[B[i]].real(b[B[i]].real() + 1);
  }

  /*
  cerr << endl;
  for (int i = 0; i <= max_a; ++i) cerr << a[i].real() << ' ';
  cerr << endl;
  for (int i = 0; i <= max_b; ++i) cerr << b[i].real() << ' ';
  cerr << endl;
  */

  fft(a, 1, nn, bit), fft(b, 1, nn, bit);
  for (int i = 0; i < nn; ++i) a[i] *= b[i];
  fft(a, -1, nn, bit);

  int end = min(max_a + max_b + 1, MAXN);
  // for (int i = 0; i < end; ++i) cerr << int(a[i].real() + 0.5) << ' ';
  // cerr << endl;

  cnt[0] = 0;
  for (int i = 1; i < end; ++i) cnt[i] = cnt[i - 1] + (a[i].real() + 0.5);
  // cerr << ans << '\n';
  for (int i = 0; i < n; ++i) ans += cnt[min(C[i] - 1, end - 1)];
  // cerr << ans << '\n';
}

inline void big() {
  static long long ans;
  ans = 0;
  gao_big(A, B, C, ans);
  gao_big(B, C, A, ans);
  gao_big(C, A, B, ans);
  io << 1LL * n * n * n - ans << '\n';
}

inline void gao_small(int *A, int *B, int *C, long long &ans) {
  static int cnt[MAXN], maxx;
  maxx = -1;
  for (int i = 0; i < n; ++i)
    if (maxx < A[i]) maxx = A[i];
  memset(cnt, 0, sizeof(int) * (maxx + 1));
  for (int i = 0; i < n; ++i) ++cnt[A[i]];
  for (int i = maxx - 1; i; --i) cnt[i] += cnt[i + 1];
  for (int i = 0, j; i < n; ++i)
    for (j = 0; j < n; ++j)
      if (B[i] + C[j] < maxx) ans += cnt[B[i] + C[j] + 1];
}

inline void small() {
  static long long ans;
  ans = 0;
  gao_small(A, B, C, ans);
  gao_small(B, A, C, ans);
  gao_small(C, A, B, ans);
  io << 1LL * n * n * n - ans << '\n';
}

inline void solve() {
  io >> n;
  for (int i = 0; i < n; ++i) io >> A[i];
  for (int i = 0; i < n; ++i) io >> B[i];
  for (int i = 0; i < n; ++i) io >> C[i];
  if (n <= 1000) {
    small();
  } else {
    big();
  }
}

int main() {
  int o_o, v_v;
  for (io >> o_o, v_v = 1; v_v <= o_o; ++v_v) {
    io << "Case #" << v_v << ": ";
    solve();
  }
}

D. Counting Sequences I

题意：问有多少个正整数序列满足$\sum a_i=\Pi a_i$。

直接用 dfs 去求解，注意剪枝。先不考虑位置，先求 N 个数，然后利用$N!/(k1!k2!\ldots)$算序列个数，~~然后打表~~。

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449


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

const int MAXN = 3e3 + 5;

int a[MAXN] = {
    0,         0,         1,         6,         12,        40,        30,
    84,        224,       144,       135,       715,       627,       1326,
    1274,      420,       480,       2720,      5202,      16530,     3800,
    2590,      924,       16951,     552,       9300,      68575,     82134,
    21168,     24360,     165300,    3720,      45632,     199584,    2244,
    22015,     2520,      29304,     77330,     57798,     398320,    1285760,
    4255062,   81270,     41624,     48510,     97290,     1479889,   106032,
    11760,     180075,    132600,    3254004,   429936,    1267866,   38115,
    2293060,   20948298,  40667106,  299425,    208860,    2325320,   344162,
    7394058,   7636608,   82875520,  8580,      305118,    4013836,   171258,
    173880,    11850965,  70320672,  1866318,   14396330,  4872900,   17100,
    895356,    468468,    499122,    252800,    20509200,  7012845,   1391827,
    578676,    25229190,  26418340,  211474989, 784847184, 497121123, 15339150,
    49140,     393484,    1972158,   821748,    2924575,   53598240,  55872,
    45638306,  15086610,  753390000, 50040450,  417498852, 18788230,  1649648,
    1168440,   1202040,   63736369,  2461428,   68719050,  162308630, 564673856,
    24864,     5916680,   12882,     83753235,  89751520,  869785371, 124424274,
    827222264, 916501173, 142157979, 2679303,   3661464,   39416252,  40718500,
    31500,     4096512,   135201152, 132178560, 5399940,   191928100, 764103895,
    303683688, 755446880, 403450390, 878166801, 7620488,   63013698,  181404174,
    188003060, 1490370,   40044,     7198477,   2965248,   73807320,  222581380,
    897305600, 3241644,   486312756, 838638473, 668099857, 87240552,  277345965,
    3652110,   279481895, 569777520, 909958004, 17438618,  102598248, 6080160,
    331917600, 704201656, 12886128,  6522608,   11108130,  856576600, 6916639,
    773139192, 393768648, 453484704, 5029110,   10088316,  597113652, 30102,
    2755725,   479740800, 6824611,   490800468, 6727676,   453731610, 810770040,
    174453052, 127995139, 76742980,  579462920, 6400260,   197469008, 621276832,
    63131059,  3519180,   655161515, 315686842, 28570176,  246855106, 708291090,
    7567560,   468395047, 15329358,  7998606,   803840600, 57548093,  624161197,
    809432154, 689858065, 197982428, 630455180, 357065367, 320910720, 936082576,
    87780,     963476640, 74767476,  379431305, 9754548,   380663735, 10031040,
    156955682, 25639852,  20815512,  5347980,   198166963, 886901487, 225570529,
    242056473, 501024386, 533868153, 603037815, 920524624, 245275990, 718210895,
    212520,    12540528,  543375195, 461026027, 32361615,  540843679, 392427831,
    168324999, 208713599, 700359503, 28225920,  380401421, 67909312,  81646278,
    630637420, 1293931,   889031838, 949548624, 259817649, 549967486, 898626104,
    686911972, 56583450,  24419560,  817851652, 16842240,  891525490, 17040642,
    862442760, 43568980,  561311662, 17984466,  437032941, 809577120, 18959160,
    388056851, 262408964, 560202110, 38713404,  657023276, 821728799, 818922105,
    190585256, 635328541, 948130242, 157183696, 704797050, 309867908, 277830386,
    51523419,  134870012, 749747645, 184738215, 448245518, 318027562, 275886879,
    333883532, 395070958, 48524256,  475894014, 49114980,  236370917, 784569639,
    979573108, 921821882, 773970379, 110038107, 105145128, 235499832, 26910000,
    64267522,  208632348, 110356236, 214584532, 461333294, 560051640, 903997718,
    590609103, 218012655, 780213045, 692419287, 439786580, 279209594, 383153779,
    93074310,  814843017, 988535918, 205584668, 145543973, 54218796,  420841210,
    489026136, 101531951, 476789328, 74482200,  664404815, 556029323, 35179968,
    106293320, 217140,    72747180,  127035152, 215692694, 111253064, 388964221,
    61191507,  848268878, 659514248, 487518216, 265388569, 771127213, 748161940,
    681164077, 541338475, 70311036,  85182422,  882943718, 804827001, 59357303,
    21376250,  43611750,  43737408,  807625711, 44111586,  713948361, 860057995,
    984432333, 137008032, 883198273, 305220824, 581376307, 283279826, 758860975,
    670467540, 619538990, 874650824, 656833322, 504482780, 851303417, 791600048,
    321615528, 207289111, 969710687, 224897578, 969569932, 975009846, 12704182,
    147213128, 181988425, 550724752, 138047730, 536076394, 19423120,  474768550,
    534347422, 277774654, 873715625, 305094536, 448946783, 855709629, 60538530,
    209522824, 693786590, 927479183, 18760111,  123571800, 467930686, 548061617,
    339961478, 377197825, 929122116, 510292238, 260505648, 898560496, 606820688,
    73823363,  167968493, 753754165, 643514715, 617757502, 468134774, 139190904,
    429596203, 499872283, 804316856, 158784988, 500436898, 330820304, 833779290,
    309908865, 798032191, 19144628,  330236216, 227597688, 791835097, 548987726,
    78035958,  933622580, 464458901, 606535622, 336637759, 837971159, 466100351,
    501035131, 722499131, 998404247, 40098260,  401772714, 106748090, 42495200,
    86735880,  877149,    383556205, 196692,    263769300, 896584125, 250541410,
    706926755, 322185268, 663522473, 595974710, 915622764, 342038221, 55675413,
    585447394, 719165182, 809889789, 569918083, 97217522,  72682038,  663560186,
    103370673, 909754905, 634643969, 791101815, 701424289, 688651692, 481800017,
    873272360, 331481464, 944159323, 607048176, 450140201, 307580852, 633067279,
    507471325, 680972531, 932698257, 847108034, 329935200, 841861733, 931230222,
    86653572,  298186557, 317306433, 382511484, 941206421, 998651093, 269587042,
    223414638, 901347339, 381257681, 299192826, 716507553, 865165128, 88498570,
    843173027, 268662409, 919135809, 671588778, 222222296, 816798687, 794783532,
    382042584, 329002916, 363573101, 606409032, 111669003, 820596994, 868832953,
    599417016, 293953140, 806616576, 764889370, 63761101,  853583648, 276375792,
    65522872,  998575523, 883199315, 676000997, 149580165, 348663191, 678678481,
    255020512, 485229036, 109282577, 448477583, 149990544, 76877264,  304513527,
    150568236, 655124776, 151988148, 534097455, 270093859, 221569978, 619992276,
    544538574, 150812922, 389192157, 202124556, 637466796, 904314865, 928886810,
    154958903, 986123802, 493231088, 174281319, 670239135, 620110933, 863183249,
    934326167, 819168264, 7982499,   709372942, 504356707, 254984246, 388526852,
    40220645,  796202131, 485121798, 860777029, 845478466, 228206320, 616806504,
    373998577, 548461368, 270464656, 47395831,  356441469, 376758112, 144582797,
    511930601, 460865219, 191102400, 759228371, 706166393, 656083619, 483915676,
    233711788, 334721218, 366744996, 256254932, 939464893, 820630126, 744833546,
    727795522, 280642674, 886252016, 350529523, 205557637, 252080132, 562214776,
    526787415, 474826371, 467447759, 426265164, 903873639, 814861053, 652325400,
    373440437, 687691947, 369572971, 323140786, 69302116,  43642259,  660284932,
    778084009, 340284840, 31054896,  788787168, 688336753, 145029237, 985504152,
    789054774, 962884714, 395571569, 233780504, 168115571, 494552394, 67447035,
    202266088, 798703541, 395891121, 135046153, 403981400, 159247666, 143493859,
    798227695, 55224865,  357009419, 454515132, 150274489, 178570260, 210983813,
    498819674, 361042201, 426347031, 720670392, 170511627, 29604571,  941026002,
    196725873, 117997015, 558944842, 993648602, 775173055, 482897329, 216451053,
    588351508, 69968544,  839465698, 267745819, 497919246, 707866547, 515002033,
    457109086, 791806544, 756143730, 501423063, 621969865, 65435703,  1760928,
    294520520, 295850520, 171480964, 75037306,  746533086, 735283669, 993956457,
    761593809, 576182646, 29796753,  307091250, 750194451, 127938676, 113624041,
    684683623, 559264596, 910352698, 632570004, 922079143, 700674648, 107768085,
    12803389,  315230643, 69719392,  684737497, 713196061, 500895558, 489199334,
    118998513, 154225376, 601094140, 605921272, 635704768, 226235052, 487165332,
    520733089, 660828412, 510296466, 70596855,  87989882,  814956472, 989764782,
    509684340, 105100373, 56635131,  878945228, 75750103,  889601833, 805395626,
    1018164,   550074525, 591104443, 507686325, 106832893, 121280127, 252901789,
    754281360, 55124492,  539232854, 378979248, 37596279,  871423269, 46434673,
    303502248, 831327476, 682341354, 984281639, 518822386, 209012379, 373818194,
    280886837, 200784330, 835954781, 952391185, 708363654, 854813534, 31991942,
    892048110, 573477097, 726697464, 481008185, 838200926, 184369893, 235370739,
    451975003, 442549874, 346154363, 664956781, 751500417, 766800077, 612475552,
    603329623, 900187875, 480110290, 124363866, 359437181, 75806737,  428987741,
    280183261, 255034614, 138883350, 744685088, 284786294, 118056680, 857162814,
    86710025,  111734528, 902382760, 671383828, 390551308, 330049507, 268637353,
    432803347, 734228779, 52835114,  1215240,   794111495, 169789549, 974873498,
    2455488,   7533512,   434190168, 275570612, 631324980, 694449373, 796264418,
    520361981, 566911084, 141925319, 310049960, 259421112, 389584998, 465612970,
    741650255, 15626799,  817985602, 955298916, 373067244, 749792253, 519072048,
    709957667, 352435327, 307806691, 103532642, 931274568, 55054546,  508958223,
    334183064, 784907041, 514706626, 765771029, 654170840, 327024525, 265119102,
    997643052, 198350910, 662827123, 380189614, 818560301, 792090648, 648806412,
    565603500, 370645480, 697510117, 191781902, 714187644, 68919578,  775673314,
    802156026, 327313830, 981974078, 353487139, 356667790, 612781218, 123314900,
    720381882, 234631072, 725805855, 662954402, 249842351, 851066342, 815392996,
    425744774, 876287207, 974652300, 945822500, 514375749, 436698245, 389982090,
    638765679, 953468095, 254442313, 374933677, 546717955, 718111373, 785286672,
    40983236,  854513483, 869334736, 706111287, 760755468, 477779463, 106101468,
    555653287, 467970542, 448928923, 244409126, 132202982, 45032659,  183576156,
    723789448, 331709380, 646468723, 7618074,   634316500, 507395929, 739563824,
    358168213, 307141879, 906239919, 383552291, 603072554, 927872338, 992793541,
    106993994, 959368012, 239359520, 958645519, 97766556,  731202273, 524097717,
    897101113, 696767626, 119789136, 506989682, 454761793, 260903034, 924524905,
    436819382, 460758311, 350337118, 742856580, 632420149, 647647472, 119844310,
    736127169, 625054057, 951065689, 523298143, 55071410,  495972022, 948411706,
    661284847, 543872197, 327608264, 717372706, 816254369, 365398585, 849672317,
    892787726, 91534997,  561260042, 200048155, 615104795, 893042933, 398432214,
    686351665, 720195287, 512767529, 354028115, 730207706, 758504201, 989913501,
    338764389, 727411977, 595038002, 181853274, 396483757, 432243270, 485643332,
    877319158, 140454505, 745000975, 611498115, 395296858, 292419313, 191311267,
    853411926, 446691238, 580623351, 397273986, 740302027, 954140674, 368525042,
    496213255, 99729633,  819445721, 223561524, 791028285, 725818523, 391350585,
    1864380,   471961435, 460468174, 110523007, 188242539, 601916944, 869058584,
    154915878, 373400807, 566756325, 525860165, 283085347, 96330146,  735389956,
    947087381, 931924086, 914515318, 998942683, 972426722, 825933663, 917666394,
    34729893,  639560602, 6392083,   997565381, 357134307, 688692967, 810741123,
    779912339, 146525680, 451628321, 76797290,  548922635, 837490667, 170994838,
    423345877, 129090457, 818477932, 59887299,  921448552, 696661704, 376243808,
    23624929,  593822289, 7631378,   669643487, 457636516, 966360400, 169535581,
    221258907, 804640886, 946579310, 759818681, 502069767, 488732898, 189768562,
    874303301, 139105262, 74788345,  342563828, 814987229, 518441160, 486616097,
    264157861, 781755606, 220233735, 293262794, 47192702,  744589011, 502087245,
    644009612, 698703472, 933094451, 437047482, 973869717, 353009606, 311989248,
    891410657, 574727666, 112067918, 586375307, 881918259, 178185268, 777795697,
    383723936, 833629481, 705150479, 74265245,  146538580, 8917416,   364089236,
    603597984, 669065439, 56801053,  340987474, 491430879, 167637977, 795083390,
    514321126, 628034835, 73435079,  331767,    587868050, 925257726, 296025157,
    4583880,   94548187,  27129928,  687485123, 153476345, 971505419, 240975411,
    655010663, 784968058, 730969296, 549515837, 190402315, 812520333, 837233823,
    580225672, 214692760, 968382817, 349551304, 872030955, 913289980, 727860843,
    904421703, 525699547, 718377743, 86469381,  290404560, 349078279, 893847202,
    18047457,  532613704, 687247627, 2426604,   48290411,  565094863, 952919356,
    929554956, 331258640, 442063720, 109848068, 546344621, 689175476, 639256606,
    61256976,  666659774, 900152643, 609635265, 59764974,  747453865, 82276239,
    608996864, 188466878, 754517941, 873055451, 767056914, 376133080, 452677803,
    236489791, 894446733, 124367604, 798555100, 929966018, 218211120, 159167283,
    832017848, 764662630, 12452848,  291468549, 310525484, 224341245, 461404668,
    171786431, 424308103, 659875206, 914488331, 233375053, 88095382,  705038270,
    127859679, 727692572, 845393508, 275751707, 924561422, 821163746, 823207036,
    198946905, 361117238, 855245947, 882535045, 661613930, 922227576, 132563739,
    700201660, 134187592, 378134320, 206304426, 647483758, 446869221, 537761316,
    836501507, 737942573, 101462914, 254976945, 984195498, 820249000, 513006904,
    883675686, 557168210, 450052408, 525873517, 546387405, 452391975, 919501853,
    832568757, 15771841,  484526551, 175134775, 16034822,  211327375, 330263119,
    617274503, 691022710, 7120151,   858681594, 335637869, 433252481, 458555250,
    651254990, 663858506, 194778510, 921937639, 458334254, 851969973, 369221056,
    832965539, 224982723, 278741460, 208135475, 527091615, 13727746,  933648460,
    979217271, 977908109, 699347534, 605275061, 680006844, 138207385, 476420524,
    454337834, 432857762, 329129493, 249917198, 635207838, 925775672, 319266038,
    887064863, 955698465, 800487244, 890273204, 197837460, 772046625, 448568903,
    994270983, 2202083,   337825364, 314855310, 571777590, 100930605, 804271258,
    896561440, 209505045, 636202604, 654077994, 354744867, 654916048, 892346636,
    900874886, 875082407, 820397405, 744408326, 319524142, 857109769, 825251278,
    139189036, 740415394, 734723593, 549082845, 449981465, 682193071, 264849052,
    548097428, 256591101, 904105174, 216886060, 546346517, 925358843, 354864453,
    722718671, 321846273, 425509709, 550501155, 887998324, 242630205, 341203401,
    567799310, 945919477, 234461536, 992565773, 532984267, 706692878, 477501163,
    907735581, 385409880, 24084117,  152826686, 535828167, 505728432, 576019572,
    637926206, 63597142,  486048180, 175547747, 204747271, 448146096, 457727918,
    488912075, 108205956, 810889345, 741657960, 989265235, 90709325,  667608082,
    363714689, 842189216, 938344764, 621625602, 73955312,  150044362, 114626882,
    431495595, 507500775, 572205175, 382879956, 114216690, 806893429, 210570498,
    455186137, 425417333, 386398714, 596827545, 263703787, 703382548, 761557694,
    277792423, 862325960, 812639623, 493319930, 395541306, 568546355, 292602262,
    842784527, 988275384, 5275735,   9710626,   591395332, 275741918, 827299964,
    84102555,  794676041, 449558369, 968205208, 118854753, 217545063, 638934535,
    577554378, 445509020, 359426758, 531701358, 413836019, 645845897, 478408830,
    210980547, 484616283, 736453663, 134784663, 230072569, 594470544, 199456481,
    687245914, 944400397, 367422508, 502407246, 327525248, 2409329,   637838117,
    460451360, 620429823, 385772555, 444059169, 663166708, 905797888, 150216305,
    925211932, 967581856, 856604826, 633524252, 818608774, 779154260, 351933796,
    241245687, 539079581, 380121579, 358363358, 656464946, 744407036, 445509866,
    623576335, 552371119, 243859757, 767639129, 916565394, 780997900, 345270688,
    45337896,  365937901, 918769991, 737716077, 872053942, 745882925, 304107437,
    742913162, 152591197, 504005602, 745963069, 339027008, 648158708, 356979055,
    251658644, 350267449, 218396195, 528325581, 853128591, 61960438,  934101045,
    545726740, 164051638, 318390731, 344462276, 628428015, 941306094, 416249377,
    403965815, 124891583, 493241663, 719780684, 704028812, 738481155, 477766621,
    480078395, 205758213, 788722302, 940576196, 530403854, 644491372, 147765447,
    730407129, 526483058, 839247469, 953647876, 230174645, 738401499, 252016089,
    839168584, 318135333, 691236099, 522885642, 57852387,  665872925, 610449631,
    335587637, 38225843,  873941520, 860129357, 411876821, 650600889, 78154329,
    249283617, 234331961, 768939567, 213615420, 941385655, 948215702, 330205876,
    110301667, 511776193, 237458114, 833816311, 732543873, 332144563, 824338191,
    344405298, 255873062, 268201855, 388755074, 530063844, 725604699, 437231399,
    767499657, 412006069, 727898630, 959761288, 368963259, 753594261, 941168673,
    895390098, 324029172, 223503548, 123695774, 708347793, 234357695, 276680917,
    874921399, 808351598, 185838366, 689388859, 374465797, 188032072, 909068155,
    8103993,   921653969, 110434802, 23592891,  863079363, 530641790, 745174775,
    398849683, 982492459, 30669775,  460755580, 676159524, 466381915, 171201376,
    490088863, 626115977, 339492394, 260661008, 808962706, 783494263, 757057702,
    650205840, 671600850, 395289600, 268699433, 200749052, 760092115, 854974626,
    617918852, 146480360, 367958301, 665443459, 651958596, 591996333, 529141385,
    103042755, 635875078, 229543266, 975622787, 990059255, 526296735, 124207077,
    779086258, 127431824, 478615557, 194940896, 549034158, 838633292, 630929695,
    992660528, 179905595, 797408180, 286079740, 54997013,  531739658, 160399507,
    533581146, 669649060, 567027529, 834300318, 782811285, 834852547, 268762765,
    673491579, 752621948, 181327100, 987648234, 994705061, 935860549, 48395022,
    549649238, 26096245,  67139606,  533925322, 615363850, 889938131, 470733890,
    13002602,  532459537, 409148235, 584397893, 586072331, 858764587, 427977500,
    110641909, 831590950, 906744401, 917704525, 342763113, 428849488, 998462639,
    578275833, 51671902,  834310940, 843525388, 170077969, 421311707, 774941292,
    372210264, 957332890, 938318941, 756823220, 249986665, 281293021, 190083027,
    500167713, 567291252, 587178315, 300549645, 806113912, 516253563, 55634069,
    401950511, 317126622, 369911780, 652840113, 995547002, 333897128, 746359351,
    76209238,  839552484, 118141423, 241283438, 751474087, 203444846, 32164240,
    638177450, 547414034, 894616496, 106931614, 637581208, 52040668,  331409981,
    670064014, 759726278, 373057342, 728961125, 398421321, 600741147, 664406486,
    873395333, 828186101, 682634524, 599791867, 210650856, 704668342, 771258344,
    593207903, 637940973, 832297357, 711254335, 228743345, 561644275, 741275954,
    152879080, 765704746, 886538877, 264033059, 769721022, 452249881, 765404529,
    263878981, 529906201, 424675564, 123370262, 862734196, 275732613, 108121357,
    168897336, 745259944, 275432564, 804959304, 921962888, 725908689, 337253841,
    190937005, 954433122, 319125904, 951881672, 279216420, 978112731, 790310060,
    418123021, 341506955, 879497486, 439639234, 309283317, 811120551, 5175526,
    502449372, 515256688, 579419243, 229419994, 995589181, 866246760, 26610876,
    516875986, 37065936,  507816804, 365834308, 441987874, 965406799, 366042511,
    245802532, 264579631, 651328115, 533437999, 978270999, 902688496, 948335674,
    938252023, 548615466, 866583655, 192236829, 469532833, 608959286, 829987660,
    98460012,  350364548, 353524134, 273438762, 751361525, 104696494, 724719530,
    635381352, 873474376, 24492933,  870561443, 890772582, 64841777,  188736251,
    708591998, 434240511, 586686106, 995174017, 919069658, 422661660, 989767876,
    779664326, 568742428, 555571170, 331095961, 743189129, 679638082, 173723643,
    795843190, 843437031, 191954921, 164546533, 709767378, 530779693, 951738508,
    37529444,  830757701, 851230860, 336572181, 464724213, 806214991, 103681548,
    482107178, 779781178, 568834211, 828359381, 794619755, 119224858, 144284441,
    221489584, 217832265, 409643065, 666067174, 17805710,  847806650, 884710707,
    79469595,  650370309, 416226143, 460498390, 964744198, 772525458, 823037564,
    978423245, 642109060, 291791327, 887427390, 691797252, 460317501, 245566383,
    305470990, 87733481,  353487672, 824102564, 991301856, 711556084, 531020430,
    720557952, 844714453, 491631445, 63851524,  434703155, 2435425,   790404246,
    904657164, 438661023, 151033395, 396172161, 418835087, 206614697, 457074720,
    608773629, 264116201, 223275367, 245993799, 496965931, 565076367, 537794619,
    367113924, 252100958, 709127314, 955740165, 717448530, 994033575, 401632962,
    479531706, 771835736, 582097172, 974725684, 120159476, 176935535, 370842860,
    230417041, 443706478, 623894274, 125138058, 847667397, 965552842, 503036584,
    238729727, 771366596, 846308038, 385665487, 144000504, 971774721, 862963782,
    676308938, 306748904, 214162181, 798645022, 965147303, 221783444, 968638180,
    596118398, 613689375, 440199970, 326609542, 200407677, 188180453, 311644091,
    437387952, 492429919, 295268147, 207642414, 387827252, 387204044, 286727804,
    992211167, 801906940, 182465008, 717529343, 109496137, 56346212,  817066611,
    722093165, 278338119, 125519775, 339560430, 95097088,  954781013, 606165034,
    440895227, 323946877, 322883952, 204899821, 242128720, 987880142, 420098921,
    37923330,  958225089, 122221704, 772855662, 688733852, 719240677, 623219519,
    368476454, 826744655, 121794566, 580055217, 21017408,  58334458,  723669214,
    646117361, 919270103, 713591804, 414167117, 749255488, 387744086, 481431314,
    778935000, 765824383, 99751371,  290751602, 99100808,  745302997, 150845735,
    285271048, 640059268, 72688131,  885179308, 563557137, 627116239, 467926228,
    154038981, 855078908, 239847057, 224974902, 122188560, 630966900, 948703110,
    111762527, 643314729, 458317020, 347201947, 12260974,  290362454, 634790741,
    326860120, 762906451, 189110897, 144685453, 338136139, 486192267, 542560718,
    390360006, 768623878, 555237875, 200618633, 411646662, 640902819, 375122720,
    859840755, 926440334, 983901029, 644361167, 557768887, 471531181, 839019911,
    492236151, 302466426, 619067868, 105040990, 331785240, 925654069, 57844772,
    692034765, 48498242,  173578244, 330210638, 604566249, 943490380, 769799859,
    66924496,  614397810, 483134411, 548440861, 611172651, 182043044, 836488615,
    267112763, 36899421,  170177389, 284124493, 209747550, 646096654, 66428152,
    640009911, 417026703, 204258590, 680746748, 368803537, 249840809, 924665621,
    411817689, 558003974, 349799126, 315013999, 572137860, 120833284, 174118387,
    790884748, 611641624, 245313746, 493071659, 149624586, 26381110,  755522217,
    21853784,  220111412, 180053444, 457340982, 886562009, 173724526, 951327622,
    926270785, 220543246, 980743241, 758691577, 520939772, 920838631, 205931308,
    939756328, 127209836, 49345476,  427346061, 157072463, 788168698, 789011320,
    387408827, 805584922, 520587768, 344833484, 944402100, 505371045, 858708031,
    721939765, 123885123, 181672954, 984166396, 544325554, 902088524, 63682305,
    743280884, 98282317,  705755871, 446819467, 514887133, 787448645, 217889683,
    121213294, 427078898, 708917990, 878460076, 455497803, 188688702, 32845539,
    148203353, 739564502, 962381246, 730353844, 350822169, 300896832, 593976448,
    58898711,  876865498, 803005309, 104990357, 367204649, 502881890, 125815409,
    111510829, 435176333, 509278129, 501575299, 39102238,  823765969, 946483679,
    306248971, 708800537, 662005514, 323003352, 262757830, 660921811, 609033158,
    806699587, 376532152, 653905608, 771074077, 403966670, 699051879, 751148442,
    667523617, 293892043, 216700826, 475523317, 611175855, 349750403, 397122770,
    600991650, 811873949, 490600655, 56091305,  341631112, 7687611,   644789227,
    306289630, 385652175, 51610979,  146413842, 345076831, 318654777, 659542972,
    358176183, 728989702, 403151556, 135326157, 485219462, 322725678, 893250857,
    199042878, 42398970,  225008067, 20707686,  910835055, 281018401, 869115498,
    560751993, 570799146, 186189152, 82012912,  446308901, 116332513, 407369447,
    439749755, 803681666, 423959206, 967926299, 802286977, 315528585, 643645200,
    264777346, 571374721, 133368312, 389173633, 899240221, 174467132, 412823343,
    21849670,  366777395, 337371546, 824215722, 407041089, 766446890, 426284226,
    309134906, 45999942,  585261605, 689507865, 546107746, 961896000, 636500332,
    135133533, 295001698, 981121543, 310622632, 646664316, 853242302, 286506103,
    830315517, 164079343, 157584893, 98928198,  714493736, 846792037, 118567936,
    524596615, 742292678, 718601928, 882939162, 530683041, 82716066,  419412605,
    241084210, 127563843, 496286870, 168923909, 497701150, 64884037,  907404815,
    412595578, 243295012, 64070595,  847374357, 108407193, 285510730, 105702210,
    512649952, 586758748, 761333635, 579114732, 580055349, 965005046, 650791737,
    33850971,  119466849, 550688638, 140298310, 717293427, 712850525, 100756288,
    810543135, 246124914, 863189769, 337306457, 249857916, 531007670, 139659082,
    866771448, 97020004,  662357536, 105708199, 767804835, 532480484, 350672723,
    866120656, 377313835, 961461578, 714816787, 888420842, 562365416, 793124261,
    676364684, 535627784, 345437779, 588558905, 947122281, 185010198, 122699228,
    448688298, 401386588, 769858791, 158355617, 702201105, 877622978, 489166721,
    851037457, 113428131, 164322101, 711992816, 296377603, 126433807, 180450232,
    146837392, 607717358, 563604593, 356043954, 922055014, 319182365, 174193926,
    377458326, 18507492,  143952738, 823582808, 911429426, 440611855, 182016880,
    489811390, 453582279, 501061568, 265897023, 242575754, 590437149, 701707491,
    368361266, 873217515, 206915966, 477560642, 195945276, 800255933, 146328848,
    238086060, 64124447,  568639082, 825639698, 37835610,  459285599, 405655713,
    264184088, 811118450, 771538314, 758568653, 67288752,  442678232, 513740510,
    249153131, 631804884, 745225615, 303368839, 92091573,  907775472, 192991161,
    236563759, 25776285,  131890473, 21132408,  847102938, 149488348, 148778253,
    843822831, 163190499, 283941706, 842734246, 29230259,  744428930, 144384672,
    350981976, 369149228, 499015910, 998276706, 923782806, 583341467, 887420440,
    547851984, 944178640, 925745128, 259534405, 676669256, 21008387,  595626741,
    795993673, 687487400, 878932432, 262993325, 132916880, 288019935, 303500548,
    798425037, 967539431, 130866909, 690889743, 2256339,   47921417,  167151952,
    172000018, 569932621, 181260821, 854724929, 615055120, 990557991, 184519647,
    696726312, 165633744, 18611998,  94903228,  108907137, 784609625, 46356688,
    111175813, 95565207,  921448284, 965725965, 629304430, 34924296,  21198028,
    797483283, 212669536, 976406737, 352447176, 218531740, 655441606, 771430154,
    792985102, 270095956, 395491706, 631203998, 141112477, 129095841, 713050733,
    361092102, 582080861, 989296009, 765944610, 449622199, 562260454, 60008778,
    924177229, 730633959, 531523490, 305988364, 137309655, 467422290, 59364172,
    245102202, 884904070, 851933726, 8498945,   363027638, 478241543, 376816288,
    647176824, 900548916, 714776422, 398586738, 754134414, 949513695, 812482309,
    738765334, 96373561,  456583815, 778396146, 824708228, 169241669, 18513247,
    248953188, 866649542, 925833075, 879168660, 686521069, 294429425, 678005040,
    225667101, 476975131, 563022008, 257669221, 359816064, 964823152, 949198453,
    942487694, 550498060, 149911444, 265842716, 848412399, 712541894, 262004030,
    990279140, 397094833, 385436353, 349417395, 343346366, 793922093, 505807774,
    206700717, 923970484, 617836626, 654647686, 92296771,  656850619, 106462179,
    332302661, 395494094, 300769295, 416862903, 250124878, 328061056, 363399471,
    89342190,  996824166, 110025828, 493324057, 340271519, 515307727, 500719764,
    296308480, 375927426, 99937293,  739326961, 171481824, 603207978, 317624308,
    824560460, 718392046, 473621824, 658907409, 120298672, 935512512, 957477156,
    550497051, 314368608, 79592957,  735904230, 947458707, 97663817,  516391131,
    936369964, 201869156, 148854868, 105101392, 757013867, 579559607, 867993522,
    590082342, 654916098, 232871119, 497801638, 795057605, 879031953, 20536976,
    984651426, 417681904, 618101543, 827509797, 22145237,  558974756, 571472687,
    729136028, 934819037, 408198760, 660348706, 490104187, 672922042, 265997754,
    160698662, 665096775, 199606210, 738727709, 902511005, 738641098, 951490713,
    170465881, 791853629, 603824480, 869243557, 874763267, 794397707, 547857170,
    653126256, 846302493, 774655222, 599648854, 236412620, 912437371, 32727778,
    554859775, 25994353,  271780454, 292906854, 378285222, 233557402, 751320564,
    529931475, 371953160, 533539382, 463597568, 470933499, 916267699, 929447279,
    645679550, 928931634, 594083681, 892537734, 388048241, 839147883, 340716716,
    799113275, 600857249, 293924167, 868198295, 556913221, 912657133, 120917217,
    870176863, 96911369,  456964969, 969501857, 96227060,  137468292, 12325728,
    844016408, 51534403,  656437267, 868256084, 200485713, 568923513, 439337409,
    852619174, 634116035, 356331473, 644072860, 608828254, 679830843, 408364825,
    819994273, 708409577, 33289493,  729955094, 596908384, 552676290, 804063672,
    642210283, 87969249,  139856655, 573837082, 585204162, 709919080, 62019450,
    690340904, 134375538, 239873992, 248897451, 344866625, 929545102, 553885732,
    378658393, 844885049, 839814934, 567317169, 38067232,  429000062, 781481111,
    237895107, 782073191, 337473894, 141506057, 492977927, 460288582, 745195402,
    482110822, 102004165, 152293447, 685882358, 485879386, 848080146, 599355957,
    488608364, 19053402,  423318689, 471333487, 188166164, 302107539, 372743633,
    177700432, 978971079, 366701808, 401596902, 927509072, 171361096, 95127688,
    424301456, 399542853, 768237456, 601860578, 499990629, 187805495, 191279700,
    481600043, 305424704, 222429969, 602590712, 904063876, 842352983, 944208736,
    819657360, 49463685,  538026209, 906352779, 419674963, 930518965, 778141124,
    255585286, 33994747,  519787112, 79986460,  226108045, 524476702, 27656221,
    255579862, 646238174, 847099521, 272965646, 865493485, 385727148, 126314306,
    37843618,  788938122, 618363112, 928198145, 400264960, 871653169, 62240715,
    364773082, 617467205, 972975522, 710291243, 636653364, 440799981, 141210740,
    57867049,  423646746, 714493511, 177625722, 617783970, 274650380, 687499716,
    611743818, 664745550, 378779532, 204366492, 162895731, 549949937, 442481335,
    525455322, 740477352, 481424096, 305714815, 51047601,  438699099, 262169947,
    133720731, 478955102, 436063979, 595492260, 936083246, 863122159, 945175103,
    263539607, 510732407, 282342468, 686191734, 492765857, 436266853, 1776510,
    904247837, 612920718, 48007182,  239884386, 11204682,  40517916,  620896715,
    428051563, 228035641, 81480630,  987941217, 506734291, 827420210, 315533927,
    873321075, 194012513, 701591193, 469021066, 977224823, 287810653, 418116475,
    229914328, 680362293, 685870845, 221377050, 217438428, 436976820, 956610315,
    609746286, 995059943, 834130154, 620333413, 129424212, 85123869,  684341657,
    372232483, 849850868, 39008962,  334692007, 441172896, 441332548, 832399170,
    559399752, 817223339, 368656463, 508150161, 982500386, 805756404, 361093783,
    782516904, 227697402, 552864398, 376648315, 131219359, 824310464, 88378402,
    105093721, 931111394, 978424570, 462045876, 775812495, 375392919, 974899300,
    472606090, 544185580, 50284084,  401130151, 414301598, 593630705, 917370510,
    658630453, 411490799, 178655844, 380745385, 325174122, 3082222,   682403282,
    550267455, 841077458, 610783619, 361233023, 793693746, 460107087, 799438353,
    760107599, 52044074,  119468097, 44303927,  132339297, 573405675, 272388138,
    43419227,  411058183, 220220432, 611745919, 805350568, 970746014, 764062232,
    393882739, 983284303, 272507287, 577270472, 846617654, 491819287, 206119318,
    521558324, 910021282, 639310249, 620356611, 64059745,  687961292, 625991240,
    25907400,  59892214,  88040640,  776895239, 818968695, 160783525, 954869542,
    293693723, 468987937, 446082996, 916942884, 311292313, 658592565, 634756596,
    70358162,  210975824, 253238476, 832920931, 963525669, 882776534, 763829888,
    717755102, 134562859, 992220619, 532109146, 425961811, 493677646, 107786653,
    207818522, 196066339, 111474900, 257644627, 274562332, 307727812, 717836315,
    326865766, 873090201, 124492385, 846032717, 722268565, 757127484, 332116994,
    432329903, 443274582, 610441402, 698528081, 310044953, 260046011, 554112619,
    703742007, 402774419, 292306979, 760774539, 402066147, 752998364, 271696960,
    177313912, 309878494, 540104932, 779043454, 569185053, 160233288, 325474984,
    756301940, 892820990, 500053160, 231334896, 794606267, 404678875, 980732369,
    283755839, 368386613, 86296858,  67762572,  75074675,  991932675, 688983358,
    913104550, 786957021, 879078663, 146575829, 191767008, 638549864, 146213572,
    79225954,  65949125,  267399617, 616601372, 31296380,  534786460, 871570500,
    417735380, 771785110, 376385944, 154401309, 234734748, 631694290, 542886380,
    102226975, 785537721, 242796494, 777292172, 650777687, 121632024, 490436396,
    331066103, 939668693, 433716263, 980024850, 797678562, 305812176, 982021027,
    688100320, 829876446, 125002285, 364614521, 219921143, 245211624, 309829642,
    43455167,  364536486, 85737790,  425628595, 859372492, 471784346, 403385340,
    96571820,  837277437, 386811318, 745690100, 28585286,  438708382, 6635488,
    915376438, 487080701, 247830110, 935059609, 76336473,  816549921, 272103268,
    768416972, 859456661, 463819251, 32608561,  698776266, 688501880, 939605786,
    5192087,   844383395, 550698387, 396220525, 25232358,  122324978, 874042807,
    493690026, 447201459, 855822480, 585455069, 894491961, 989605241, 539114271,
    273794598, 517458429, 753561258, 41854924,  936179443, 534463507, 784177424,
    645763670, 839030396, 385673367, 619137125, 536106422,
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int o_o, n;
  for (cin >> o_o; o_o; --o_o) {
    cin >> n;
    cout << a[n] << '\n';
  }

  return 0;
}

E. Counting Sequences II

题意：问有多少个长度为 n 的序列,每个数的范围是 1~m, 偶数在序列中出现次数必须是偶数。

通过生产函数推公式。 ~~可怜的 cycleke 打表推出了 m 在 1 到 6 的公式，然而没有发现规律。~~

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33


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

const int MOD = 1e9 + 7;

inline int mod_pow(int a, long long b) {
  int res = 1;
  for (; b; b >>= 1, a = 1LL * a * a % MOD)
    if (b & 1) res = 1LL * res * a % MOD;
  return res;
}

void solve() {
  long long n;
  int m, sum = 0, C = 1;
  cin >> n >> m;
  for (int i = 0, end = (m >> 1) + 1; i < end; ++i) {
    sum = (sum + 1LL * C * mod_pow(i * 2 + (m & 1), n)) % MOD;
    C = 1LL * C * (m / 2 - i) % MOD * mod_pow(i + 1, MOD - 2) % MOD;
  }
  static int inv2 = mod_pow(2, MOD - 2);
  cout << 1LL * sum * mod_pow(inv2, m / 2) % MOD << '\n';
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int o_o;
  for (cin >> o_o; o_o; --o_o) solve();

  return 0;
}

F.Rhyme scheme

注意会 Bell26 会溢出 long long，要使用__int128

G. Substring

题意:给了一个母串 S, 每次循环给了一个模板串,问模板串在母串中“匹配”了多少次?“匹配”的意思就是首字母和尾字母一样, 中间字母顺序可以换。

由于$\sum |M| \leq 1e5$，所以不同的长度不超过$\sqrt{1e5}$，对每个长度用 hash 就好了。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82


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

const int MAXN = 1e5 + 5;
const int MAXM = 2e4 + 5;
const int ALPHABET = 26;

const unsigned int SEED = 6163;

struct Query {
  int id, s, t;
  unsigned int val;
};

vector<Query> q[MAXN];
int ans[MAXM], n, m, cnt[ALPHABET];
char str[MAXN], t[MAXN];
unordered_map<unsigned int, int> sum[ALPHABET][ALPHABET];
unsigned int p[ALPHABET];

inline void add(unordered_map<unsigned int, int> &cnt, const unsigned int &val) {
  auto it = cnt.find(val);
  if (it != cnt.end()) ++it->second;
}

inline void gao(const int &len) {
  if (q[len].empty()) return;
  memset(cnt, 0, sizeof(cnt));
  unsigned int val = 0;
  for (register int i = 0; i < len; ++i) ++cnt[str[i] - 'a'];
  for (register int i = 0; i < ALPHABET; ++i) val = val * SEED + cnt[i];
  for (register int i = 0; i < ALPHABET; ++i)
    for (register int j = 0; j < ALPHABET; ++j) sum[i][j].clear();
  for (auto &qu : q[len]) sum[qu.s][qu.t][qu.val] = 0;
  for (register int l = 0, r = len - 1; r < n; ++l) {
    add(sum[str[l] - 'a'][str[r] - 'a'], val);
    val -= p[str[l] - 'a'];
    if (++r < n) val += p[str[r] - 'a'];
  }
  for (auto &qu : q[len]) ans[qu.id] = sum[qu.s][qu.t][qu.val];
}

inline void solve() {
  fgets(str, MAXN, stdin);
  n = strlen(str);
  while (str[n - 1] == '\n' || str[n - 1] == '\r') --n;
  for (int i = 1; i <= n; ++i) q[i].clear();

  scanf("%d\n", &m);
  for (int i = 0, l, j; i < m; ++i) {
    // cin >> t;
    fgets(t, MAXN, stdin);
    memset(cnt, 0, sizeof(cnt));
    l = strlen(t);
    while (t[l - 1] == '\n' || t[l - 1] == '\r') --l;
    if (l > n) {
      ans[i] = 0;
      continue;
    }
    for (j = 0; j < l; ++j) ++cnt[t[j] - 'a'];
    unsigned int val = 0;
    for (j = 0; j < ALPHABET; ++j) val = val * SEED + cnt[j];
    q[l].push_back((Query){i, t[0] - 'a', t[l - 1] - 'a', val});
  }
  for (int i = 1; i <= n; ++i) gao(i);
  for (int i = 0; i < m; ++i) printf("%d\n", ans[i]);
}

int main() {
  // freopen("in.txt", "r", stdin);
  // ios::sync_with_stdio(false);
  // cin.tie(nullptr);

  p[0] = 1;
  for (int i = 1; i < ALPHABET; ++i) p[i] = p[i - 1] * SEED;
  reverse(p, p + ALPHABET);

  int o_o;
  for (scanf("%d\n", &o_o); o_o; --o_o) solve();

  return 0;
}

L.Digit sum

题意：询问 1~n 在 b 进制下的数字和。

签到题，经典的数位 dp。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47


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

typedef pair<int, int> pii;

const int MAXD = 22;

pii dp[MAXD][10];
int n, b, dig[MAXD], len;

pii dfs(int step, int cur, bool limit) {
  if (!step) return pii(cur, 1);
  if (!limit && (~dp[step][cur].first)) return dp[step][cur];
  int f = 0, s = 0;

  int end = limit ? dig[step - 1] : b - 1;
  for (int i = 0; i <= end; ++i) {
    pii p = dfs(step - 1, i, limit && i == end);
    f += p.first;
    s += p.second;
  }
  f += s * cur;

  if (!limit) dp[step][cur] = pii(f, s);
  return pii(f, s);
}

void solve() {
  cin >> n >> b;

  for (len = 0; n; n /= b, ++len) dig[len] = n % b;
  dig[len] = 0;
  memset(dp, -1, sizeof(dp));
  cout << dfs(len, 0, true).first << '\n';
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int o_o;
  cin >> o_o;
  for (int i = 1; i <= o_o; ++i) {
    cout << "Case #" << i << ": ";
    solve();
  }
}