No Abstract.

T1

Des.

有一堆点, 每个有两个属性, 对于一个点, 要找从原点出发, 经过在她之前的点, 到达她的最短链.

Sol.

KD-Tree.

考场上GG了, 居然拿代表点的值来估价, 把宽限开再大也没有过去, 用矩形内最小值来估价就行了.

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
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int maxn = 15e+4 + 105;
const ll inf = 1e+12;

int n, k, d, qe, rt, rev[maxn], tot;
int a[maxn][2], q[maxn], hd, tl;
ll f[maxn], ans;

struct p {
  int coe[2], id; ll val;
  inline bool operator<(const p &rhs) const {
    if (d) return (coe[0] == rhs.coe[0]) ? coe[1] < rhs.coe[1] : coe[0] < rhs.coe[0];
    else return (coe[1] == rhs.coe[1]) ? coe[0] < rhs.coe[0] : coe[1] < rhs.coe[1];
  }
}arr[maxn];
struct KDnode {
  int ch[2], p[2], mn[2], mx[2], fa;
  ll val, mnval;
  KDnode(){}
  KDnode(int x) {
    ch[0] = ch[1] = 0;
    mn[0] = mx[0] = p[0] = a[x][0]; 
    mn[1] = mx[1] = p[1] = a[x][1];
    val = f[x];
  }
}t[maxn];
inline bool cmp(int x, int y) {
  if (d) return (t[x].p[0] == t[y].p[0]) ? t[x].p[1] < t[y].p[1] : t[x].p[0] < t[y].p[0];
  else return (t[x].p[1] == t[y].p[1]) ? t[x].p[0] < t[y].p[0] : t[x].p[1] < t[y].p[1];
}
int ptr; 

inline void pushup(int cur, int s) {
  for (int i = 0; i <= 1; ++i)
    t[cur].mn[i] = min(t[cur].mn[i], t[s].mn[i]);
  for (int i = 0; i <= 1; ++i)
    t[cur].mx[i] = max(t[cur].mx[i], t[s].mx[i]);
  t[cur].mnval = min(t[cur].mnval, t[s].mnval);
}
inline ll sqr(ll val) {
  return val * val;
}

#define ls t[cur].ch[0]
#define rs t[cur].ch[1]
int build(int l, int r, int dim) {
  if (l > r) return 0;
  int mid = (l + r) >> 1; int cur = ++tot;
  d = dim;
  nth_element(arr + l, arr + mid, arr + r);
  rev[arr[mid].id] = tot;
  for (int i = 0; i <= 1; ++i)
    t[cur].mn[i] = t[cur].mx[i] = t[cur].p[i] = arr[mid].coe[i];
  // printf("%d %d %d\n", cur, t[cur].mn[0], t[cur].mx[0]);
  t[cur].val = t[cur].mnval = inf;
  if (arr[mid].coe[0] == 0) t[cur].val = t[cur].mnval = 0;
  if (l < mid) ls = build(l, mid - 1, dim ^ 1), pushup(cur, ls), t[ls].fa = cur;
  if (r > mid) rs = build(mid + 1, r, dim ^ 1), pushup(cur, rs), t[rs].fa = cur;
  return cur;
}
ll calc_precise(int x, int y) {
  ll ret = 1ll * (t[x].p[0] - t[y].p[0]) * (t[x].p[0] - t[y].p[0]) + 
          1ll * (t[x].p[1] - t[y].p[1]) * (t[x].p[1] - t[y].p[1]) + t[y].val;
  // printf("%d %d %lld\n", x, y, ret);
  return ret;
}
ll calc(int x, int y) {
  ll ret = 0;
  for (int i = 0; i <= 1; ++i)
    if (t[x].p[i] < t[y].mn[i] || t[x].p[i] > t[y].mx[i]) 
      ret += (t[x].p[i] < t[y].mn[i]) ? sqr(t[x].p[i] - t[y].mn[i]) : sqr(t[x].p[i] - t[y].mx[i]);
  ret += t[y].mnval;
  return ret;
}
void pushup(int cur) {
  t[cur].mnval = t[cur].val;
  if (ls) pushup(cur, ls);
  if (rs) pushup(cur, rs);
  if (t[cur].fa) pushup(t[cur].fa);
}
void query(int cur) {
  if (!cur) return;
  ans = min(ans, calc_precise(qe, cur));
  // printf("%d %lld\n", cur, ans);
  ll dis[2] = {calc(qe, ls), calc(qe, rs)};
  if (!ls) dis[0] = inf;
  if (!rs) dis[1] = inf;
  int pre = dis[0] > dis[1];
  query(t[cur].ch[pre]);
  if (dis[pre ^ 1] < ans) query(t[cur].ch[pre ^ 1]);
}

int main() {
  // freopen("a.in", "r", stdin);
  // freopen("my.out", "w", stdout);
  scanf("%d%d", &n, &k);
  for (int i = 1; i <= n; ++i) {
    if (k == 1) scanf("%d", &a[i][0]);
    else scanf("%d%d", &a[i][0], &a[i][1]);
    arr[i].val = inf;
    arr[i].coe[0] = a[i][0]; arr[i].coe[1] = a[i][1];
    arr[i].id = i;
  }
  arr[++n].val = 0;
  arr[n].coe[0] = arr[n].coe[1] = 0;
  arr[n].id = 0;
  t[0].mn[0] = t[0].mn[1] = 1e9;
  t[0].mx[0] = t[0].mx[1] = -1e9;
  t[0].val = inf;
  rt = build(1, n, 0);
  qe = n + 100;
  for (int i = 1; i < n; ++i) {
    t[qe].p[0] = a[i][0]; t[qe].p[1] = a[i][1]; ans = inf;
    query(rt);
    t[rev[i]].val = ans;
    printf("%.4lf\n", sqrt(ans));
    pushup(rev[i]);
  }
  return 0;
}

T2

Des.

给一些轮换的长度集合, 求$1$到$n$的每个长度有多少符合条件的置换, 即其中的所有循环长度都属于这个集合.

Sol.

$k-$轮换集合的生成函数是$\frac{(k-1)!}{k!}x^k$, 也就是$\frac{x^k}{k}$. 我们令指定位有值即可.

置换是轮换的集合, 所以我们用轮换的生成函数生成置换, 为$e^{f(x)}$.

集合的生成函数系数下面带一个阶乘, 要在对应的次数位置乘回来.

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
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

int n, k;

namespace PolyTech {
  #define mod 950009857
  #define g 7

  static const int maxn = 4e+5 + 5;
  ll A[maxn], B[maxn], inv[maxn], tmp[maxn], tmp2[maxn];
  ll tmp5[maxn];
  int rev[maxn];

  void init() {
    inv[1] = 1;
    for (int i = 2; i < maxn; ++i) 
      inv[i] = inv[mod % i] * (mod - mod / i) % mod;
  }
  inline ll quick_power(ll base, ll index) {
    ll ret = 1;
    while (index) {
      if (index & 1) ret = ret * base % mod;
      index >>= 1;
      base = base * base % mod;
    }
    return ret;
  }
  void DFT(ll *arr, int typ, int n) {
    int N = 1, L = 0;
    while (N < n) N <<= 1, L++;
    for (int i = 0; i < N; ++i)
      rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (L - 1));
    for (int i = 0; i < N; ++i)
      if (i > rev[i]) swap(arr[i], arr[rev[i]]);
    for (int i = 2; i <= N; i <<= 1) {
      int m = (i >> 1);
      ll e = quick_power(g, (mod - 1) / i);
      if (typ == -1) e = quick_power(e, mod - 2);
      for (int j = 0; j < N; j += i) {
        ll w = 1;
        for (int k = 0; k < m; ++k) {
          ll t = arr[j + m + k] * w % mod;
          arr[j + m + k] = (arr[j + k] - t + mod) % mod;
          arr[j + k] = (arr[j + k] + t) % mod;
          w = w * e % mod;
        }
      }
    }
    if (typ == 1) return;
    ll inv = quick_power(N, mod - 2);
    for (int i = 0; i < N; ++i)
      arr[i] = arr[i] * inv % mod;
  }
  void Derivative(ll *arr, ll *res, int len) {
    for (int i = 1; i < len; ++i)
      res[i - 1] = i * arr[i] % mod;
    res[len] = res[len - 1] = 0;
  }
  void Intergral(ll *arr, ll *res, int len) {
    for (int i = 1; i < len; ++i)
      res[i] = arr[i - 1] * inv[i] % mod;
    res[0] = 0;
  }
  void Inversion(ll *arr, ll *res, int len) {
    if (len == 1) {
      res[0] = quick_power(arr[0], mod - 2);
      return;
    }
    Inversion(arr, res, len >> 1);
    int now = len << 1;
    for (int i = 0; i < len; ++i) tmp5[i] = arr[i];
    for (int i = len; i < now; ++i) tmp5[i] = 0;
    DFT(tmp5, 1, now); DFT(res, 1, now);
    for (int i = 0; i < now; ++i)
      tmp5[i] = res[i] * (2ll - tmp5[i] * res[i] % mod + mod) % mod;
    DFT(tmp5, -1, now);
    for (int i = 0; i < len; ++i) res[i] = tmp5[i];
    for (int i = len; i < now; ++i) res[i] = 0;
  }
  void Logarithmic(ll *arr, ll *res, int len) {
    memset(tmp, 0, sizeof tmp);
    memset(tmp2, 0, sizeof tmp);
    Derivative(arr, tmp, len);
    Inversion(arr, tmp2, len);
    DFT(tmp, 1, len << 1); DFT(tmp2, 1, len << 1);
    for (int i = 0; i < (len << 1); ++i)
      tmp[i] = tmp[i] * tmp2[i] % mod;
    DFT(tmp, -1, len << 1);
    Intergral(tmp, res, len);
  }
  ll tmp3[maxn], tmp4[maxn];
  void Exponent(ll *arr, ll *res, int len) {
    if (len == 1) {
      res[0] = 1;
      return;
    }
    Exponent(arr, res, len >> 1);
    for (int i = 0; i < len; ++i) tmp3[i] = res[i];
    Logarithmic(tmp3, tmp4, len);
    for (int i = 0; i < len; ++i)
      tmp4[i] = (arr[i] - tmp4[i] + mod) % mod;
    tmp4[0] = (tmp4[0] + 1) % mod;
    DFT(tmp3, 1, len << 1); DFT(tmp4, 1, len << 1);
    for (int i = 0; i < (len << 1); ++i) tmp3[i] = tmp3[i] * tmp4[i] % mod;
    DFT(tmp3, -1, (len << 1));
    for (int i = 0; i < len; ++i) res[i] = tmp3[i];
    memset(tmp3, 0, sizeof tmp);
    memset(tmp4, 0, sizeof tmp2);
  }

  void solve() {
    init();
    scanf("%d%d", &n, &k);
    int x;
    for (int i = 1; i <= k; ++i) {
      scanf("%d", &x);
      A[x] = inv[x];
    }
    int m = 1;
    while (m <= n) m <<= 1;
    Exponent(A, B, m);
    ll fac = 1;
    for (int i = 1; i <= n; ++i, fac = fac * i % mod) {
      ll ret = B[i] * fac % mod;
      printf("%lld\n", ret);
    }
  }
}

int main() {
  PolyTech::solve();
  return 0;
}