全国互虐 TEST 6.2【数学难题】

这题= =
赤裸裸的把5题数论拼在一起就变成了数论难题。。
其实这些题也是有一些难点的0 0

直接exgcd即可

显然p-1是一个解 其他的解一定是它的因数(可以证明
于是每次sqrt枚举即可

各种乱推后可以得出答案是
sum(phi(k) * (n / k) * (m / k))
预处理phi前缀和 然后用分段函数的处理方法处理即可

sum(n/i)=sum(f(i))
f(i)表示i的因数个数
证明就是 对于一个i n/i就表示它是几个数的因数 所以一样
f可以用线性筛法预处理
弄出前缀和即可

把b倒序fft即可

全国互虐 TEST 6.2【旅行计划】

可以证明。。
从u到v的最大距离最小的路径是在曼哈顿最小生成树上走
曼哈顿最小生成树的求法就是
可以证明 每个点只要和它按米字切的8个块的最近点分别连边即可
用线段树可以维护

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
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <vector>
#include <functional>
#include <ctime>
#include <cstdlib>
#include <sstream>
#include <set>
using namespace std;
typedef long long ll;

const int maxn = 100005;

struct point
{
  int x, y;
}a[maxn];

struct LINE
{
  int fr, to, v;      
}L[maxn * 50];

struct line
{
  int next, to;      
}li[maxn * 5];

int n, l, be[maxn], c[maxn * 10], m, t[maxn * 13], t2[maxn * 13], lll, k[maxn], fat[maxn], fa[maxn][20][2], d[maxn];
queue<int> q;

void makeline(int fr, int to)
{
  ++l;
  li[l].next = be[fr];
  be[fr] = l;
  li[l].to = to;    
}

int getfa(int a)
{
  return (!fat[a]) ? a : (fat[a] = getfa(fat[a]));    
}

bool cmp(int x, int y)
{
  return a[x].x + a[x].y < a[y].x + a[y].y ||
        (a[x].x + a[x].y == a[y].x + a[y].y &&
         a[x].x < a[y].x);
}

bool cmp2(int x, int y)
{
  return a[x].x + a[x].y > a[y].x + a[y].y ||
        (a[x].x + a[x].y == a[y].x + a[y].y &&
         a[x].x < a[y].x);
}

bool cmp3(LINE a, LINE b) { return a.v < b.v; }

int getv(int b) { return a[b].x - a[b].y; }

int mi(int x, int y)
{
  if (x == 0) return y;
  if (y == 0) return x;
  return getv(x) > getv(y) ? x : y;
}

int query2(int l, int r, int now, int rt)
{
  if (r <= rt) return t2[now];
  int mid = (l + r) / 2, ans = 0;
  ans = mi(ans, query2(l, mid, now * 2, rt));
  if (rt >= mid + 1) ans = mi(ans, query2(mid + 1, r, now * 2 +1, rt));
  return ans;
}

void insert2(int l, int r, int now, int lr, int v)
{
  if (l == r)
  {
    t2[now] = mi(t2[now], v);
    return;    
  }
  int mid = (l + r) / 2;
  if (lr <= mid) insert2(l, mid, now * 2, lr, v);
  else insert2(mid + 1, r, now * 2 + 1, lr, v);
  t2[now] = mi(t2[now * 2], t2[now * 2 + 1]);
}

int query(int l, int r, int now, int lf)
{
  if (l >= lf) return t[now];
  int mid = (l + r) / 2, ans = 0;
  if (mid >= lf) ans = mi(ans, query(l, mid, now * 2, lf));
  ans = mi(ans, query(mid + 1, r, now * 2 + 1, lf));
  return ans;
}

void insert(int l, int r, int now, int lr, int v)
{
  if (l == r)
  {
    t[now] = mi(t[now], v);
    return;    
  }
  int mid = (l + r) / 2;
  if (lr <= mid) insert(l, mid, now * 2, lr, v);
  else insert(mid + 1, r, now * 2 + 1, lr, v);
  t[now] = mi(t[now * 2], t[now * 2 + 1]);
}

int dist(point a, point b) { return abs(a.x - b.x) + abs(a.y - b.y); }

int lca(int u, int v)
{
  if (d[u] < d[v]) swap(u, v);
  int ans = 0;
  while (d[u] != d[v])
  {
    int i;
    for (i = 0; d[u] - (1 << i) >= d[v]; ++i);
    --i;
    ans = max(ans, fa[u][i][1]);
    u = fa[u][i][0];
  }
  while (u != v)
  {
    int i;
    for (i = 0; fa[u][i][0] != fa[v][i][0]; ++i);
    i = i ? i - 1 : i;
    ans = max(ans, fa[u][i][1]);
    u = fa[u][i][0];
    ans = max(ans, fa[v][i][1]);
    v = fa[v][i][0];      
  }
  return ans;
}

int main()
{
  freopen("plan.in","r",stdin);
  freopen("plan.out","w",stdout);
  scanf("%d", &n);
  for (int i = 1; i <= n; ++i)
  {
    scanf("%d%d", &a[i].x, &a[i].y);  
    k[i] = i;
    c[m++] = a[i].x;
    c[m++] = -a[i].x;
    c[m++] = a[i].y;
    a[i].x *= -1;
  }
  sort(c, c + m);
  m = unique(c, c + m) - c;
  sort(k + 1, k + 1 + n, cmp);
  for (int i = 1; i <= n; ++i)
  {
    int x = lower_bound(c, c + m, a[k[i]].x) - c,
        y = lower_bound(c, c + m, a[k[i]].y) - c,
        v = getv(k[i]);
    int t = query(0, m, 1, y);
    if (t)
    {
      L[lll].fr = k[i], L[lll].to = t, L[lll].v = v - getv(t);
      ++lll;
    }
    insert(0, m, 1, y, k[i]);
  }
 
  sort(k + 1, k + 1 + n, cmp2);
  for (int i = 1; i <= n; ++i)
  {
    int x = lower_bound(c, c + m, a[k[i]].x) - c,
        y = lower_bound(c, c + m, a[k[i]].y) - c,
        v = getv(k[i]);
    int t = query2(0, m, 1, x);
    if (t)
    {
      L[lll].fr = k[i], L[lll].to = t, L[lll].v = v - getv(t);
      ++lll;
    }
    insert2(0, m, 1, x, k[i]);
  }
  for (int i = 1; i <= n; ++i) a[i].x *= -1;  
  memset(t, 0, sizeof(t));
  memset(t2, 0, sizeof(t2));
  sort(k + 1, k + 1 + n, cmp);
  for (int i = 1; i <= n; ++i)
  {
    int x = lower_bound(c, c + m, a[k[i]].x) - c,
        y = lower_bound(c, c + m, a[k[i]].y) - c,
        v = getv(k[i]);
    int t = query(0, m, 1, y);
    if (t)
    {
      L[lll].fr = k[i], L[lll].to = t, L[lll].v = v - getv(t);
      ++lll;
    }
    insert(0, m, 1, y, k[i]);
  }
 
  sort(k + 1, k + 1 + n, cmp2);
  for (int i = 1; i <= n; ++i)
  {
    int x = lower_bound(c, c + m, a[k[i]].x) - c,
        y = lower_bound(c, c + m, a[k[i]].y) - c,
        v = getv(k[i]);
    int t = query2(0, m, 1, x);
    if (t)
    {
      L[lll].fr = k[i], L[lll].to = t, L[lll].v = v - getv(t);
      ++lll;
    }
    insert2(0, m, 1, x, k[i]);
  }  
  sort(L, L + lll, cmp3);
  for (int i = 0; i < lll; ++i)
    if (getfa(L[i].fr) != getfa(L[i].to))
    {
      fat[getfa(L[i].fr)] = getfa(L[i].to);
      makeline(L[i].fr, L[i].to);
      makeline(L[i].to, L[i].fr);
    }
  q.push(1);
  d[1] = 1;
  while (!q.empty())
  {
    int now = q.front();
    q.pop();
    for (int i = 1, k = fa[now][0][0]; k; k = fa[k][i - 1][0], ++i)
      fa[now][i][0] = fa[k][i - 1][0],
      fa[now][i][1] = max(fa[now][i - 1][1], fa[k][i - 1][1]);
    for (int i = be[now]; i; i = li[i].next)
    {
      int to = li[i].to;
      if (to == fa[now][0][0]) continue;
      fa[to][0][0] = now;
      fa[to][0][1] = dist(a[now], a[to]);
      d[to] = d[now] + 1;
      q.push(to);
    }
  }
  int T;
  scanf("%d", &T);
  while (T--)
  {
    int fr, to;
    scanf("%d%d", &fr, &to);      
    printf("%d\n", lca(fr, to));
  }
  fclose(stdin);fclose(stdout);    
}

全国互虐 TEST 6.2【圆圈游戏】

这题在建完图后就是裸的树dp 毫无疑问 问题是怎么建图
想一个很暴力的方法 对于每个圆(xi,yi,ri)
枚举所有x在xi-ri~xi+ri范围内的点 直接判断

当然 这很容易被卡掉 于是我们把整个坐标轴转一个随机的角度就不容易卡了
我写的是这个 A了。。

但是这种做法很是会被同心圆卡
于是队长讲了一种算法 比题解的更好理解点
就是对于每个深度维护一棵平衡树
插入一个点 二分它的深度 判断有没有被这个深度的包含即可
判断就是维护括号序列前缀和 判断到你的时候是否为0 为0 就是没有包含的
知道深度后 你的深度-1的 你的前驱就是你的父亲节点

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
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <vector>
#include <functional>
#include <ctime>
#include <cstdlib>
#include <sstream>
#include <set>
using namespace std;
typedef long long ll;

const int maxn = 100005;
const double A = 2.132786;

struct point
{
  double x, y;
  int r, v, n;      
}a[maxn], a2[maxn], a3[maxn];

struct line
{
  int next, to;      
}li[maxn * 2];

int n, be[maxn],l, b[maxn], f[maxn];
queue<int> q;
stack<int> s;

bool cmp1(point a, point b) { return a.x < b.x; }
bool cmp2(point a, point b) { return a.r < b.r; }

point turn(point a)
{
  double x = a.x * cos(A) - a.y * sin(A),
         y = a.x * sin(A) + a.y * cos(A);
  a.x = x, a.y = y;
  return a;
}

void makeline(int fr, int to)
{
  ++l;
  li[l].next = be[fr];
  be[fr] = l;
  li[l].to = to;    
}

int bfs()
{
  for (int i = 0; i < n; ++i)
    if (!b[i]) q.push(i);
  while (!q.empty())
  {
    int now = q.front();
    q.pop();
    s.push(now);
    for (int i = be[now]; i; i = li[i].next)
      q.push(li[i].to);    
  }
  while (!s.empty())
  {
    int now = s.top();
    s.pop();
    f[now] = 0;
    for (int i = be[now]; i; i = li[i].next)
    {
      int to = li[i].to;
      f[now] += f[to];
    }      
    f[now] = max(f[now], a[now].v);
  }
  int ans = 0;
  for (int i = 0; i < n; ++i)
    if (!b[i]) ans += f[i];
  return ans;
}

double sqr(double a) { return a * a; }

double dist(point a, point b)
{
  return sqrt(sqr(a.x - b.x) + sqr(a.y - b.y));
}

bool operator<(point a, point b) { return a.x < b.x; }

int main()
{
  freopen("circle.in","r",stdin);
  freopen("circle.out","w",stdout);
  scanf("%d", &n);
  for (int i = 0; i < n; ++i)
  {
    scanf("%lf%lf%d%d", &a[i].x, &a[i].y, &a[i].r, &a[i].v);
    a[i].n = i;
    a[i] = turn(a[i]);
    a2[i] = a3[i] = a[i];
  }
  sort(a2, a2 + n, cmp1);
  sort(a3, a3 + n, cmp2);
  for (int i = 0; i < n; ++i)
  {
    point tl, tr;
    tl.x = a3[i].x - a3[i].r;
    tr.x = a3[i].x + a3[i].r + 1;
    int l = lower_bound(a2, a2 + n, tl) - a2,
        r = lower_bound(a2, a2 + n, tr) - a2;
    for (int j = l; j < r; ++j)
      if (a2[j].n != a3[i].n && !b[a2[j].n] && dist(a3[i], a2[j]) - 1e-8 < a3[i].r && a2[j].r < a3[i].r)
        makeline(a3[i].n, a2[j].n), b[a2[j].n] = 1;
  }
  printf("%d", bfs());    
  fclose(stdin);fclose(stdout);    
}

全国互虐 TEST 5.31【魔法】

首先 可以证明
一条路径是由一大堆环和一条从1到某个点的链组成的
对于图上的所有环 对于某条链 都可以选或不选
即环和链的选择是独立的
如果现在有cnt个本质不同的环
和ccnt个本质不同的链
答案就是ccnt * 2^(cnt) – 1
因为对于每条链 所有环都可以选或不选
然后减掉0的情况

所谓本质相同的环a,b
就是把a任意异或其他环 得出的答案集合A
和把b任意异或其他环 得出的答案集合B是相同的
则他们本质相同
排除这种情况 只要对他们进行高斯消元 排除掉0的值就行了

本质相同的链的定义类似 两条链在环中进行高斯消元后 如果答案一样 则本质相同

然后就可以算出ans了

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
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <cmath>
#include <vector>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <stack>
#include <iostream>
#include <algorithm>
#include <string>
#include <functional>
#include <sstream>
using namespace std;
typedef long long ll;
typedef long double ld;

const ll maxn = 100005;

struct line
{
  ll to, next, v;
}li[maxn];

struct Line
{
  ll fr, to, v;
}L[maxn];

ll a[maxn], v[maxn], c[maxn], b[maxn], n, m, q, be[maxn], l, ans[maxn], Q[maxn], f[maxn], cnt, ccnt, r[maxn];
set<ll> s;

void dfs(ll now, ll la)
{
  f[now] = la;
  c[++ccnt] = la;
  v[now] = 1;
  for (ll i = be[now]; i; i = li[i].next)
  {
    ll to = li[i].to;
    if (v[to]) a[++cnt] = f[now] ^ f[to] ^ li[i].v;
    else dfs(to, la ^ li[i].v);
  }  
}

ll re(ll v)
{
  for (ll i = 62; i >= 0; --i)
    if (v & (1LL << i)) v ^= r[i];
  return v;
}

ll calc()
{
  for (ll i = 1; i <= cnt; ++i) b[i] = 0;
  for (ll i = 62; i >= 0; --i)
  {
    ll p = 0;
    for (ll j = 1; j <= cnt; ++j)
      if (!b[j] && (a[j] & (1LL << i)))
      {
        p = j;
        break;          
      }
    if (!p)
    {
      r[i] = 0;
      continue;      
    }
    r[i] = a[p]; b[p] = 1;
    for (ll j = 1; j <= cnt; ++j)
      if (p != j && a[j] & (1LL << i)) a[j] ^= a[p];
  }
  ll cur = 0;
  for (ll i = 1; i <= cnt; ++i)
    if (a[i]) a[++cur] = a[i];
  cnt = cur;
  s.clear();
  cur = 0;
  for (ll i = 1; i <= ccnt; ++i)
  {
    ll t = re(c[i]);
    if (s.find(t) == s.end())
    {
      s.insert(t);
      c[++cur] = c[i];          
    }
  }
  ccnt = cur;
  return ccnt * (1LL << cnt) - 1;
}

void makeline(ll fr, ll to, ll v)
{
  ++l;
  li[l].next = be[fr];
  be[fr] = l;
  li[l].to = to;
  li[l].v = v;    
}

int main()
{
  scanf("%lld%lld%lld", &n, &m, &q);
  for (ll i = 1; i <= m; ++i)
    scanf("%lld%lld%lld", &L[i].fr, &L[i].to, &L[i].v);
  for (ll i = 0; i < q; ++i) scanf("%lld", &Q[i]), b[Q[i]] = 1;
  for (ll i = 1; i <= m; ++i)
    if (!b[i])
    {
      makeline(L[i].fr, L[i].to, L[i].v);
      makeline(L[i].to, L[i].fr, L[i].v);
    }
  dfs(1, 0);
  ans[q] = calc();
  for (ll i = q - 1; i >= 0; --i)
  {
    ll fr = L[Q[i]].fr, to = L[Q[i]].to, V = L[Q[i]].v;
    makeline(fr, to, V);
    makeline(to, fr, V);
    if (v[fr] && v[to]) a[++cnt] = f[fr] ^ f[to] ^ V;
    else if (v[fr]) dfs(to, f[fr] ^ V);
    else if (v[to]) dfs(fr, f[to] ^ V);
    ans[i] = calc();
  }
  for (ll i = 0; i <= q; ++i) printf("%lld\n", ans[i]);
}

全国互虐 TEST 5.31【跑步】

这题一看就可以知道是矩阵乘法
但是如果以点为关键字
“不会沿着刚刚经过的道路再返回”这个条件会比较难满足
于是以边为关键字
每条边拆成两条
表示不同方向
然后按边的互相到达关系建立初始矩阵
矩阵乘即可

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
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <cmath>
#include <vector>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <stack>
#include <iostream>
#include <algorithm>
#include <string>
#include <functional>
#include <sstream>
using namespace std;
typedef long long ll;
typedef long double ld;

const int inf = 45989;

struct mxt
{
  ll a[123][123];
}ans, a;

struct line
{
  int to, next;
}li[500];

int n, m, k, s, l, be[500], as[500];
ll q;

mxt c(const mxt &a, const mxt &b)
{
  mxt c;
  memset(c.a, 0, sizeof(c.a));
  for (int i = 2; i <= k + 1; ++i)
    for (int l = 2; l <= k + 1; ++l)
      if (a.a[i][l])
        for (int j = 2; j <= k + 1; ++j)
        {
          c.a[i][j] = (c.a[i][j] + a.a[i][l] * b.a[l][j]) % inf;
          if (c.a[i][j] >= 0x7fffffffffffffffLL - 0x7fffffff)
            c.a[i][j] %= inf;
        }
  for (int i = 2; i <= k + 1; ++i)
    for (int j = 2; j <= k + 1; ++j) c.a[i][j] %= inf;
  return c;
}

void makeline(int fr, int to)
{
  ++l;
  li[l].next = be[fr];
  be[fr] = l;
  li[l].to = to;
}

void power(ll n)
{
  for (int i = 2; i <= k + 1; ++i)
    ans.a[i][i] = 1;
  while (n)
  {
    if (n & 1) ans = c(ans, a);
    a = c(a, a);
    n >>= 1;
  }
}

int main()
{
  freopen("walk.in", "r", stdin);
  freopen("walk.out", "w", stdout);
  scanf("%d%d%d%lld", &n, &m, &s, &q);
  k = m * 2;
  if (q == 0)
  {
    printf("1\n");
    for (int i = 2; i <= n; ++i) printf("0\n");
    fclose(stdin);fclose(stdout);
    return 0;
  }
  l = 1;
  for (int p = 0; p < m; ++p)
  {
    int fr, to;
    scanf("%d%d", &fr, &to);
    for (int i = be[fr]; i; i = li[i].next)
      a.a[l + 2][i] = 1,
      a.a[i ^ 1][l + 1] = 1;
    for (int i = be[to]; i; i = li[i].next)
      a.a[l + 1][i] = 1,
      a.a[i ^ 1][l + 2] = 1;
    makeline(fr, to);
    makeline(to, fr);
  }
  power(q - 1);
  for (int i = be[s]; i; i = li[i].next)
    for (int j = 2; j <= k + 1; ++j)
      as[j] = (as[j] + ans.a[i][j]) % inf;
  for (int i = 1; i <= n; ++i)
  {
    int t = 0;
    for (int j = be[i]; j; j = li[j].next)
      t = (t + as[j ^ 1]) % inf;
    printf("%d\n", (t % inf + inf) % inf);
  }
  fclose(stdin);fclose(stdout);
}

全国互虐 TEST 5.19【差额】

先求dfs序
对于一个询问(u, v) 可以看成一个点(dfs序上u的起始位置, dfs序上v的起始位置)

一个询问 其实就是询问某个矩形内的点数
对于询问(u, v) 设p=lca(u, v)

如果p != u && p != v则
  能包含它的询问的两个点
  一定一个在u的子树 一个在v的子树
  即为(dfs[u].begin~dfs[u].end, dfs[v].begin~dfs[v].end)范围内的点
否则
  设u == p
  能包含它的询问的两个点
  一定一个在v的子树 一个不在u向v路径上的第二个点的子树
  这样是两个矩形

这些查询 把点排序后用线段树维护就行了
对于一个矩形询问 拆成两个进行询问 差分 你懂的。

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
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <cmath>
#include <vector>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <stack>
#include <iostream>
#include <algorithm>
#include <string>
#include <functional>
#include <sstream>
using namespace std;
typedef long long ll;
typedef long double ld;

const int maxn = 100005;

struct line
{
  int to, next;
}li[maxn * 2];

struct inout
{
  int in, out;
  inout(int a = 0, int b = 0) : in(a), out(b) {}
}a[maxn];

struct point
{
  int x, y;
  point(int a = 0, int b = 0) : x(a), y(b) {}
}Q[maxn];

int dfsq[maxn * 2], t[maxn * 8], n, m, be[maxn], fa[maxn][20], d[maxn], tot, l, tot2, to;
ll ans[maxn];

struct query
{
  int l, r, x, v, to;
  query(int a = 0, int b = 0, int c = 0, int d = 0, int e = 0) : l(a), r(b), x(c), v(d), to(e) {}
}qu[maxn * 3];

queue<int> q;

int lca(int u, int v)
{
  if (d[u] < d[v]) swap(u, v);
  int i;
  while (d[u] > d[v])
  {
    for (i = 0; d[fa[u][i]] >= d[v]; ++i);
    u = fa[u][i - 1];
  }
  while (u != v)
  {
    for (i = 1; fa[u][i] != fa[v][i]; ++i);
    u = fa[u][i - 1];
    v = fa[v][i - 1];
  }
  return u;
}

void dfs(const int &now)
{
  a[now].in = tot;
  dfsq[tot++] = now;
  for (int i = be[now]; i; i = li[i].next)
  {
    if (li[i].to == fa[now][0]) continue;
    dfs(li[i].to);
  }
  a[now].out = tot;
  dfsq[tot++] = now;
}

void makeline(int fr, int to)
{
  ++l;
  li[l].next = be[fr];
  be[fr] = l;
  li[l].to = to;
}

bool cmp(point a, point b) { return a.x < b.x; }
bool cmp2(query a, query b) { return a.x < b.x; }

void insert(int l, int r, int now, int lr)
{
  if (l == r)
  {
    ++t[now];
    return;
  }
  int mid = (l + r) / 2;
  if (lr <= mid) insert(l, mid, now * 2, lr);
  else insert(mid + 1, r, now * 2 + 1, lr);
  t[now] = t[now * 2] + t[now * 2 + 1];
}

int quer(int l, int r, int now, int lf, int rt)
{
  if (l >= lf && r <= rt) return t[now];
  int mid = (l + r) / 2, ans = 0;
  if (lf <= mid) ans += quer(l, mid, now * 2, lf, rt);
  if (rt >= mid + 1) ans += quer(mid + 1, r, now * 2 + 1, lf, rt);
  return ans;
}

ll gcd(ll a, ll b)
{
  return (!b) ? a : gcd(b, a % b);
}

int getfa(int u, int de)
{
  int i;
  while (d[u] > de)
  {
    for (i = 0; d[fa[u][i]] >= de; ++i);
    u = fa[u][i - 1];
  }
  return u;
}

int main()
{
  freopen("painting.in", "r", stdin);
  freopen("painting.out", "w", stdout);
  scanf("%d%d", &n, &m);
  for (int i = 1; i < n; ++i)
  {
    int fr, to;
    scanf("%d%d", &fr, &to);
    makeline(fr, to);
    makeline(to, fr);
  }
  q.push(1);
  d[1] = 1;
  while (!q.empty())
  {
    int now = q.front();
    q.pop();
    for (int i = be[now]; i; i = li[i].next)
    {
      int to = li[i].to;
      if (to == fa[now][0]) continue;
      fa[to][0] = now;
      d[to] = d[now] + 1;
      q.push(to);
    }
    for (int i = fa[now][0], j = 0; i; i = fa[i][j++])
      fa[now][j + 1] = fa[i][j];
  }
  dfs(1);
  for (int i = 0; i < m; ++i)
  {
    int fr, to;
    scanf("%d%d", &fr, &to);
    if (a[fr].in > a[to].in) swap(fr, to);
    Q[i * 2] = point(a[fr].in, a[to].in);
    Q[i * 2 + 1] = point(a[to].in, a[fr].in);
    if (lca(fr, to) == fr)
    {
      int t = getfa(to, d[fr] + 1);
      qu[tot2++] = query(a[to].in, a[to].out, tot - 1, 1, i);
      qu[tot2++] = query(a[to].in, a[to].out, a[t].out, -1, i);
      qu[tot2++] = query(a[to].in, a[to].out, a[t].in - 1, 1, i);
    }
    else
    {
      qu[tot2++] = query(a[to].in, a[to].out, a[fr].in - 1, -1, i);
      qu[tot2++] = query(a[to].in, a[to].out, a[fr].out, 1, i);
    }
  }
  sort(Q, Q + m * 2, cmp);
  sort(qu, qu + tot2, cmp2);
  int k1 = 0, k2 = 0;
  for (; k2 < tot2 && qu[k2].x == -1; ++k2);
  for (int i = 0; i < tot; ++i)
  {
    for (; k1 < m * 2 && Q[k1].x <= i; ++k1) insert(0, tot, 1, Q[k1].y);
    for (; k2 < tot2 && qu[k2].x <= i; ++k2)
      ans[qu[k2].to] += quer(0, tot, 1, qu[k2].l, qu[k2].r) * qu[k2].v;
  }/*
  for (int i = 0; i < m; ++i) printf("%d ", ans[i]);
cout << endl;*/

  ll ANS = 0;
  for (int i = 0; i < m; ++i)
    ANS += ans[i] - 1;
  if (ANS == 0) printf("0/1");
  else
  {
    ll t = gcd(ANS, (ll)m * (m - 1) / 2);
    printf("%I64d/%I64d", ANS / t, (ll)m * (m - 1) / 2 / t);
  }
  fclose(stdin);fclose(stdout);
}

全国互虐 TEST 5.17【路线】

f[i][j]表示高度<=i 大小为j 的方案数 f[i][j] = Σ(f[i - 1][j - k] * f[i - 1][k]) 先处理处所有f 直接回答每个询问 还要优化常数 还有一种方法——分段打表 每sqrt的i打一行 然后就没有然后了~

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
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <cmath>
#include <vector>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <stack>
#include <iostream>
#include <algorithm>
#include <string>
#include <functional>
#include <sstream>
using namespace std;
typedef long long ll;
typedef long double ld;

const ll inf = 1000000007;
ll f[605][605], sum[605], n, h, T, init[12][2], mx, mxn;

int main()
{
  freopen("route.in", "r", stdin);
  freopen("route.out", "w", stdout);
  scanf("%I64d", &T);
  for (int i = 0; i < T; ++i) scanf("%I64d%I64d", &init[i][0], &init[i][1]), mx = max(mx, init[i][1]), mxn = max(mxn, init[i][0]);

  f[1][1] = 1;
  f[0][0] = 1;
  sum[1] = 1;
  sum[0] = 1;
  for (ll i = 2; i <= mx + 1; ++i)
  {
    for (ll j = i; j <= mxn + 1; ++j)
    {
      f[i][j] = 0;
      for (ll k = 0; k < j; ++k)
      {
        f[i][j] = (f[i][j] + f[i - 1][k] * (sum[j - 1 - k] - f[i - 1][j - 1 - k]) * 2) % inf,
        f[i][j] = (f[i][j] + f[i - 1][k] * f[i - 1][j - 1 - k] * 2) % inf;
        if (k == j - 1 - k) f[i][j] = (f[i][j] - f[i - 1][k]) % inf;
      }
    }
    for (ll j = 0; j <= mxn + 1; ++j) sum[j] = (sum[j] + f[i][j]) % inf;
  }
  for (int i = 0; i < T; ++i) printf("%I64d\n", f[init[i][1] + 1][init[i][0]]);
  fclose(stdin);fclose(stdout);
}