省选考6题, 6道板题.

Table of Contents

  1. BZOJ5296
    1. Des.
    2. Sol.
  2. BZOJ 5297
    1. Des.
    2. Sol.
  3. BZOJ 5298
    1. Des.
    2. Sol.
  4. BZOJ 5299
    1. Des.
    2. Sol.
  5. BZOJ 5300
    1. Des.
    2. Sol.
  6. BZOJ 5301
    1. Des.
    2. Sol.

BZOJ5296

Des.

BSGS.

Sol.

复杂度十分匪夷所思, $\sqrt{N} \times \sqrt{N}$居然能过$2^{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
#pragma GCC optimize("inline")
#pragma GCC optimize(3)
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/hash_policy.hpp>
 
using namespace __gnu_pbds;
using namespace std;
typedef long long ll;

gp_hash_table<ll, ll> h;

int n, g;
ll p, a, b, t;
int indexa, indexb;

inline ll quick_power(ll base, ll index) {
  ll ret = 1;
  while (index) {
    if (index & 1) ret = ret * base % p;
    index >>= 1;
    base = base * base % p;
  }
  return ret;
}
inline int solve(int z) {
  h.clear();
  for (int j = 0; j < t; ++j) {
    ll val = 1ll * z * quick_power(g, j) % p;
    h[val] = j;
  }
  int tmp = quick_power(g, t);
  if (tmp == 0) {
    return 1;
  } else {
    for (int k = 0; k <= t; ++k) {
      ll val = quick_power(tmp, k);
      ll j = h.find(val) == h.end() ? -1 : h[val];
      if (j >= 0 && k * t - j >= 0) {
        return k * t - j;
      }
    }
  }
  return 0;
}

int main() {
  scanf("%d%lld", &g, &p);
  scanf("%d", &n);
  t = (ll)sqrt(p) + 1;
  for (int i = 1; i <= n; ++i) {
    scanf("%lld%lld", &a, &b);
    indexb = solve(b);
    int ans = quick_power(a, indexb);
    printf("%d\n", ans);
  } 
  return 0;
}

BZOJ 5297

Des.

有向图外向生成树计数.

Sol.

Matrix - Tree 定理, 度数矩阵只保留入度, 邻接矩阵随便保留一边.

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

using namespace std;

const int maxn = 255;
const int maxm = maxn * maxn;

struct edge {
  int frm, to;
}e[maxm];
int n, m;
int mtr[maxn][maxn], bas[maxn][maxn];
int gp[maxn][maxn], dgr[maxn][maxn];

inline int solve(int N) {
  int tg = 1, ret = 1;
  for (int i = 1; i <= N; ++i) {
    // int cur = i;
    for (int j = i + 1; j <= N; ++j) {
      int a = i, b = j;
      while (mtr[b][i]) {
        int fac = mtr[a][i] / mtr[b][i];
        for (int k = i; k <= N; ++k)
          mtr[a][k] = (mtr[a][k] - mtr[b][k] * fac % mod + mod) % mod;
        swap(a, b);
      }
      if (a != i) {
        for (int k = 1; k <= N; ++k)
          swap(mtr[i][k], mtr[a][k]);
        tg *= -1;
      }
    }
    ret = (ret * mtr[i][i]) % mod;
  }
  if (tg > 0) return ret % mod;
  else return (mod - ret) % mod;
}

int main() {
  scanf("%d", &n);
  scanf("%d", &m);
  int a, b;
  for (int i = 1; i <= m; ++i) {
    scanf("%d%d", &a, &b);
    e[i] = (edge){b, a};
    dgr[a][a]++;  gp[b][a]++;
  }
  for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= n; ++j)
      bas[i][j] = dgr[i][j] - gp[i][j];
  for (int i = 2; i <= n; ++i)
    for (int j = 2; j <= n; ++j)
      mtr[i - 1][j - 1] = (bas[i][j] + mod) % mod;
  int ret = solve(n - 1);
  printf("%d\n", ret);
  return 0;
}

BZOJ 5298

Des.

令01序列中不得出现连续的1, 一个序列的特征值为$x^ay^b$, 其中$x, y$分别为$0, 1$的个数, 求所有可能方案的特征值和.

Sol.

二项式定理展开然后把DP式矩阵优化一下, 但是还有更高效的方案:

然后考虑转移, 依然是$[0/1]$状态的DP, 转移矩阵就是二项式系数以及一些必要的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
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int maxn = 1e+7 + 7;

int N, n, a, b, mod, dgr;
struct matrix {
  ll arr[205][205];
  matrix() {
    memset(arr, 0, sizeof arr);
  }
  ll* operator[](const int &x) {
    return arr[x];
  }
  inline matrix operator*(matrix rhs) {
    matrix ret;
    /*for (int k = 0; k < N; ++k)
      for (int i = 0; i < N; ++i)
        for (int j = 0; j < N; ++j)
          ret[i][j] = (ret[i][j] + arr[i][k] * rhs[k][j]) % mod;*/
    for (int i = 0; i < N; ++i)
      for (int j = 0; j < N; ++j) {
        for (int k = 0; k < N; ++k)
          if (arr[i][k] && rhs[k][j])
            ret[i][j] = (ret[i][j] + arr[i][k] * rhs[k][j]) % mod;
      }
    return ret;
  }
}ress, trans;

int c[205][205];
inline void quick_power(matrix &res, matrix base, ll index) {
  while (index) {
    if (index & 1) res = res * base;
    index >>= 1;
    base = base * base;
  }
}
void init() {
  c[0][0] = 1;
  for (int i = 1; i <= 200; ++i) {
    c[i][0] = 1;
    for (int j = 1; j <= i; ++j)
      c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;
  }
  for (int i = 0; i < dgr; ++i) {
    trans[i + dgr][i] = 1;
    trans[i][i] = 1;
    for (int j = i; j < dgr; ++j)
      trans[i][dgr + j] = c[j][i];
  }
  ress[0][0] = 1;
}

int main() {
  scanf("%d%d%d%d", &n, &a, &b, &mod);
  int ans = 0;
  dgr = a + b + 1; N = dgr * 2;
  init();
  quick_power(ress, trans, n);
  for (int i = 0; i < dgr; ++i)
    ress[0][i] = (ress[0][i] + ress[0][i + dgr]) % mod;
  for (int i = 0, pw = 1; i <= a; ++i, pw = 1ll * pw * n % mod) {
    ans = (ans + 1ll * (((a - i) & 1) ? -1 : 1) * pw * c[a][i] % mod * ress[0][a + b - i] % mod + mod) % mod;
  }
  if (ans < 0) ans = mod - ans;
  printf("%d\n", ans);
  return 0;
}

BZOJ 5299

Des.

平面上有若干个点, 由一点走到下一点时, 连线上不能有其他未经过的点, 求所有方案数.

Sol.

$O(n^22^n)$, 这复杂度怎么想都过不去结果直接莽过了???

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

using namespace std;

const int maxs = 1048579;
const int maxn = 21;

int n, x[maxn], y[maxn], ban[maxn][maxn];
int f[maxs][maxn], popcnt[maxs];

inline bool appr(int frm, int to, int trans) {
  return ((x[frm] <= x[trans] && x[to] >= x[trans]) || (x[frm] >= x[trans] && x[to] <= x[trans]))
      && ((y[frm] <= y[trans] && y[to] >= y[trans]) || (y[frm] >= y[trans] && y[to] <= y[trans]));
}

int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; ++i) {
    scanf("%d%d", &x[i], &y[i]);
  }
  for (int i = 1; i <= n; ++i) 
    for (int j = i + 1; j <= n; ++j) {
      for (int k = 1; k <= n; ++k) {
        if (k == i || k == j) continue;
        if ((y[i] - y[j]) * (x[j] - x[k]) == 
            (x[i] - x[j]) * (y[j] - y[k]) &&
            appr(i, j, k)) 
          ban[i][j] |= (1 << (k - 1)),
          ban[j][i] |= (1 << (k - 1));
          // printf("%d %d %d\n", i, j, k);
      }
    }
  f[0][0] = 1;
  int lim = (1 << n) - 1, ans = 0;
  for (int i = 0; i <= lim; ++i) {
    popcnt[i] = popcnt[i >> 1] + (i & 1);
    if (i == 0) {
      for (int j = 1; j <= n; ++j) 
        f[i | (1 << (j - 1))][j] += f[i][0];
    } else {
      for (int j = 1; j <= n; ++j) 
        if (i & (1 << (j - 1)))
          for (int k = 1; k <= n; ++k)
            if (!(i & (1 << (k - 1)))) {
              if ((i & ban[j][k]) == ban[j][k])
                f[i | (1 << (k - 1))][k] = (f[i | (1 << (k - 1))][k] + f[i][j]) % mod;
            }
    }
    if (popcnt[i] >= 4) {
      for (int j = 1; j <= n; ++j)
        if (i & (1 << (j - 1)))
          ans = (ans + f[i][j]) % mod;
    }
  }
  printf("%d\n", ans);
  return 0;
}

BZOJ 5300

Des.

$x$连环解锁步骤数.

Sol.

手玩一会(不敢相信于是去查九连环)发现确实状态$n$只和$n-1$, $n-2$有关, 列出递推式, 得到:

然后这题不带取模, 需要使用FFT(Java或Python)

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
import java.io.*;
import java.util.*;
import java.math.*;

public class Main {
  public static BigInteger QuickPower(BigInteger base, int index) {
    BigInteger ret = new BigInteger(Integer.toString(1));
    while (index > 0) {
      if ((index & 1) > 0) ret = ret.multiply(base);
      index >>= 1;
      base = base.multiply(base);
    }
    return ret;
  }
  public static void main(String args[]) throws Exception {
    Scanner cin = new Scanner(System.in);
    int m = cin.nextInt();
    for (int i = 0; i < m; ++i) {
      int n = cin.nextInt();
      if ((n & 1) > 0) {
        BigInteger Thr = new BigInteger(Integer.toString(3));
        BigInteger Bin = new BigInteger(Integer.toString(2));
        BigInteger One = new BigInteger(Integer.toString(1));
        BigInteger Res = QuickPower(Bin, n + 1);
        Res = Res.subtract(One);
        Res = Res.divide(Thr);
        System.out.println(Res.toString());
      } else {
        BigInteger Thr = new BigInteger(Integer.toString(3));
        BigInteger Bin = new BigInteger(Integer.toString(2));
        BigInteger Res = QuickPower(Bin, n + 1);
        Res = Res.subtract(Bin);
        Res = Res.divide(Thr);
        System.out.println(Res.toString());
      }
    }
  }
}

BZOJ 5301

Des.

多次询问区间中满足异或和为$k$的子段数量.

Sol.

莫队. 但是怎么快速增量呢? 把前缀和而不是真实值扔桶里, 这样查询$sum_x \oplus k$时, 桶中的元素刚好满足和该位置组成的区间异或和为$k$, 注意特殊处理$r$位置插入删除时, $l - 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
#include <bits/stdc++.h>

using namespace std;

const int maxn = 1e+5 + 5;

int bkt[maxn], a[maxn], bel[maxn], tagl, tagr;
int n, m, k, blo, ans[maxn], res;
int sum[maxn], L, R;
struct question {
  int l, r, id;
  inline bool operator<(const question &rhs) const {
    return bel[l] == bel[rhs.l] ? r < rhs.r : bel[l] < bel[rhs.l];
  }
}q[maxn];


inline int rd() {
  register int x = 0, c = getchar();
  while (!isdigit(c)) c = getchar();
  while (isdigit(c)) x = x * 10 + (c ^ 48), c = getchar();
  return x;
}
inline void addr(const int &x) {
  bkt[sum[x]]++;
  res += bkt[sum[x] ^ k];
  if ((sum[x] ^ k) == sum[L - 1]) res++;
}
inline void addl(const int &x) {
  bkt[sum[x]]++;
  res += bkt[sum[x - 1] ^ k];
}
inline void delr(const int &x) {
  res -= bkt[sum[x] ^ k];
  bkt[sum[x]]--;
  if ((sum[x] ^ k) == sum[L - 1]) res--;
}
inline void dell(const int &x) {
  res -= bkt[sum[x - 1] ^ k];
  bkt[sum[x]]--;
}

int main() {
  n = rd(); m = rd(); k = rd();
  blo = sqrt(n);
  for (int i = 1; i <= n; ++i) 
    a[i] = rd(), bel[i] = (i - 1) / blo + 1, sum[i] = sum[i - 1] ^ a[i];
  for (int i = 1; i <= m; ++i) {
    q[i].l = rd(); q[i].r = rd();
    q[i].id = i;
  }
  sort(q + 1, q + 1 + m);
  L = 1, R = 0;
  for (int i = 1; i <= m; ++i) {
    while (R < q[i].r) addr(++R);
    while (L > q[i].l) addl(--L);
    while (R > q[i].r) delr(R--);
    while (L < q[i].l) dell(L++);
    ans[q[i].id] = res;
  }
  for (int i = 1; i <= m; ++i)
    printf("%d\n", ans[i]);
  return 0;
}