曾经做的一些小水题, 总之我不会做就对了.

这是第1篇.

TCO 2014 Semifinal 2 Div.1

口胡报告.

300

DP. 懒得写了.

500

$N$个点的无向图有条边$M$, 现在必须给边定向, 有一些从$S$到$T$的询问, 问最多能同时满足多少个询问.

边双内部的询问肯定是可以满足的.

因为图规模很小, 我们把所有桥压成一个状态. 对于每个询问, 考虑它经过的桥指向哪里, 在正向或反向的状态里压入这个桥.

然后$2^q$枚举询问, 考虑是否矛盾, 更新答案即可.

RoadsReform.cpp:

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

using namespace std;

const int maxn = 60;

typedef long long ll;

struct edge {
  int to, nxt; 
}e[maxn * 200];
int ptr = 1, lnk[maxn], dfn[maxn], low[maxn], bel[maxn];
int cnt, num, cut[maxn * 200], allq, lim, ans;
ll fow[maxn], bkw[maxn];
int pre[maxn], tot, pth[maxn], vis[maxn];
vector<pair<int, int> > brg;

inline void add(int bgn, int end) {
  e[++ptr] = (edge){end, lnk[bgn]};
  lnk[bgn] = ptr;
}
void tarjan(int x, int f) {
  low[x] = dfn[x] = ++cnt;
  for (int p = lnk[x]; p; p = e[p].nxt) {
    int y = e[p].to;
    if (!dfn[y]) {
      tarjan(y, x);
      low[x] = min(low[x], low[y]);
      if (low[y] > dfn[x])
        cut[p] = cut[p ^ 1] = 1,
        brg.push_back(make_pair(e[p].to, e[p ^ 1].to));
    } else if (y != f) {
      low[x] = min(low[x], dfn[y]);
    }
  }
}
void dfs(int x) {
  bel[x] = num;
  for (int p = lnk[x]; p; p = e[p].nxt) {
    if (cut[p] || bel[e[p].to]) continue;
    dfs(e[p].to);
  }
}


class RoadsReform {
public:
  int getMax(int n, vector<int> e1, vector<int> e2,
             vector<int> s, vector<int> t);
};

int getMax(int n, vector<int> e1, vector<int> e2,
           vector<int> s, vector<int> t) {
    for (vector<int>::size_type i = 0; i < e1.size(); ++i) {
      add(e1[i], e2[i]);
      add(e2[i], e1[i]);
    }
    tarjan(1, 0);
    for (int i = 1; i <= n; ++i)
      if (!bel[i]) {
        num++;
        dfs(i);
      }
    allq = s.size();
    queue<int> q;
    for (int i = 0; i < allq; ++i) {
      int fr = s[i], to = t[i];
      if (bel[fr] == bel[to]) continue;
      tot = 0;
      memset(vis, 0, sizeof vis);
      q.push(fr); vis[fr] = 1;
      while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int p = lnk[u]; p; p = e[p].nxt) {
          int y = e[p].to;
          if (vis[y]) continue;
          q.push(y);
          pre[y] = u;
          vis[y] = 1;
        }
      }
      for (int p = to; p != fr; p = pre[p]) pth[++tot] = p;
      pth[++tot] = fr;
      for (vector<int>::size_type v = 0; v < brg.size(); ++v) {
        for (int j = 1; j < tot; ++j) {
          if (brg[v].first == pth[j] && brg[v].second == pth[j + 1])
            fow[i] |= (1ll << v);
          if (brg[v].second == pth[j] && brg[v].first == pth[j + 1])
            bkw[i] |= (1ll << v);
        }
      }
    }
    lim = (1 << allq) - 1;
    for (int i = 0; i <= lim; ++i) {
      ll fs = 0, bs = 0; int ret = 0;
      for (int j = 0; j < allq; ++j) {
        if (i & (1 << j)) 
          fs |= fow[j], bs |= bkw[j], ret++;
      }
      if (fs & bs) continue;
      ans = max(ans, ret);
    }
    return ans;
}

850

有一棵树, 一开始只有一个点, 每轮在每个点上挂一个点, 问$N$轮操作后, 长度为$D$的路径有多少, 对质数$P$取模.

$N \le 10^9, M \le 500$.

orz jcvb.

注意到每轮操作后树必然是关于一条边对称的. 于是我们可以把他分解成上一轮的两个问题. 设$g_{n,d}$ 为$n$轮以一对称边端点为起点的长为$d$的路径条数.

那么我们有: $g_{n,d} = g_{n - 1, d - 1} + g_{n - 1, d}$, 也就是从自己这边的子问题$d$和用一条边接过来的子问题$d-1$来更新答案.

那么总的答案为: $f_{n,d} = \sum_{i+j=d-1}{g_{n - 1, i}g_{n - 1, j}} + 2f_{n - 1, d}$, 也就是考虑原来存在的答案和新增的答案.

对这两个问题列生成函数. 我们发现$g$就是组合数的形式. 所以$g_n(x) = (1+x)^n$.

那么原来$g$中两项卷起来的系数加到了$f$中$i+j+1$的系数中了, 也就是:

$f_n(x) = x(1+x)^{2n-2} + 2f_{n-1}(x)$.

解出: $\frac{2^nx-x(1+x)^{2n}}{1 - 2x - x^2} + 2^n$.

多项式卷积求逆都可以$O(D\log{D})$做, 不过不用那么麻烦, $D^2$也可以.

jcvb有$O(D)$的神仙做法, 我不会.

TwiceTwiceTree.cpp:

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

using namespace std;
typedef long long ll;

const int maxn = 1000;

ll f[maxn], finv[maxn], inv[maxn];
ll mod;

inline ll C(const int &N, const int &M) {
  ll ret = 1;
  for (int i = 1; i <= M; ++i) 
    ret = (ret * (N - i + 1)) % mod,
    ret = (ret * inv[i]) % mod;
  return ret;
}
inline ll quick_power(ll base, ll index) {
  ll ret = 1;
  while (index) {
    if (index & 1) ret = ret * base % mod;
    base = base * base % mod;
    index >>= 1;
  }
  return ret;
}

class TwiceTwiceTree {
public:
  int sumup(int, int, int);
};

int TwiceTwiceTree::sumup(int N, int D, int P) {
  int n = N; mod = P;
  inv[1] = 1;
  for (int i = 2; i <= D; ++i)
    inv[i] = (mod - mod / i) * inv[mod % i] % mod;
  f[0] = 1; f[1] = mod - 2; f[2] = mod - 1; finv[0] = 1;
  for (int i = 1; i <= D; ++i) {
    ll ret = 0;
    for (int j = 1; j <= i; ++j) ret = (ret + f[j] * finv[i - j]) % mod;
    finv[i] = mod - ret;
  }
  int ans = 0, poww = quick_power(2, n);
  for (int i = 1; i <= D; ++i) {
    ll ret = mod - C(2 * n, i - 1);
    if (i == 1) ret = (ret + poww) % mod;
    ret = (ret * finv[D - i]) % mod;
    ans = (ans + ret) % mod;
  }
  return D ? ans : poww;
}`