BZOJ 3926 广义后缀自动机

BZOJ 3926 广义后缀自动机

给一棵树,点上有字母,问树上路径组成的本质不同的字符串有多少个。

$ n\le10^5,|\Sigma|\le10, |\text {leaves}| \le 20 $ .

Sol.

很久之前就会做……直到今天才来打……

打题半小时调题两小时……

注意到叶子特别少,以每个叶子为根的 trie 合并成一棵打 trie 后所有树上路径构成字符串都是大 trie 上一条从祖先到后代的路径。

对这棵打 trie 建广义后缀自动机(其实应该叫多串)。

注意到转移图的前驱结点就是 trie 上的父亲对应的结点,直接接上去就好。

不同串之间可能因为所在的 trie 不同却同时有相同的前驱,这会使得重复计算,因为前一棵 trie 的后面的串显然与当前 trie 的字符串不共享。我们显式的建出的转移图其实是有问题的,但因为我们求的这个自动机能识别的字符串个数,所以我们只关心 parent 树的结构,而这个显然是一直正确的,即便是隐式的。所以不必多做处理,每次都对当前 trie 结点都新开一个自动机结点即可。

Code

#include <bits/stdc++.h>
using namespace std;
template<class T> void read(T& x)
{
    char c = getchar(); T p = 1, n = 0;
    while(c < '0' || c > '9') {if(c == '-') p = -1; c = getchar();}
    while(c >= '0' && c <= '9'){n = n * 10 + c - '0'; c = getchar();}
    x = p * n;
}
template<class T,class U>void read(T&x,U&y){read(x),read(y);}
template<class T,class U,class V>void read(T&x,U&y,V&z){read(x),read(y),read(z);}
const int maxn = 1e5 + 10, sigma = 15;
struct E{int v, n;}e[maxn << 1];
int h[maxn], ec = 1;
inline void add_edge(int u, int v){e[ec] = (E){v, h[u]}; h[u] = ec++;}
struct N{int ch[sigma], f, len, cnt, n;} pool[maxn * sigma * sigma];
int h2[maxn], head = 1, pc = 2;
int add(int p, int c)
{
    int newnode = pc++;
    pool[newnode].n = h2[pool[newnode].len = pool[p].len + 1]; h2[pool[newnode].len] = newnode;
    pool[newnode].cnt = 0;
    for(; p && !pool[p].ch[c]; p = pool[p].f) pool[p].ch[c] = newnode;
    if(!p) pool[newnode].f = head;
    else if(pool[p].len + 1 == pool[pool[p].ch[c]].len) pool[newnode].f = pool[p].ch[c];
    else
    {
        int q = pool[p].ch[c], r = pc++;
        pool[r] = pool[q];
        pool[r].n = h2[pool[r].len = pool[p].len + 1]; h2[pool[r].len] = r;
        pool[q].f = pool[newnode].f = r;
        for(; p && pool[p].ch[c] == q; p = pool[p].f) pool[p].ch[c] = r;
    }
    return newnode;
}
int col[maxn];
void dfs(int s, int u, int f = 0)
{
    int t = add(s, col[u]);
    for(int i = h[u], v = e[i].v; i; i = e[i].n, v = e[i].v) if(v != f)
        dfs(t, v, u);
}
int deg[maxn];
int main()
{
    int n, c; read(n, c);
    for(int i = 1; i <= n; ++i) read(col[i]);
    for(int i = 1, u, v; i < n; ++i) read(u, v), add_edge(u, v), add_edge(v, u), ++deg[u], ++deg[v];
    for(int i = 1; i <= n; ++i) if(deg[i] == 1) dfs(head, i);
    long long ans = 0;
    for(int i = n; i; --i) for(int j = h2[i]; j; j = pool[j].n) 
        ans += pool[j].len - pool[pool[j].f].len;
    printf("%lld\n", ans);
    return 0;
}

BZOJ 3625 FFT

BZOJ 3625 FFT

点权集合为 $ \{c_i\}_{i=1}^n $ . 求总权值为 $ 1\le i\le m $ 的不同的有根二叉树个数。$ n,m\le 10^5 $ .

Sol.

设 $ C $ 为点权集合的 ogf , $ F $ 为二叉树个数关于总权值的 ogf , 则易有

$$ F=CF^2+1 $$

容易看出式子的组合意义为空集或者递归枚举左右子树。

解得 $ F={2\over1\pm\sqrt{1-4C}} $ .

多项式开根求逆硬上即可。

多项式技术本质来说是平凡的。反正这种问题能不能得分关键就在能不能推出式子。(当然能不能打出 NTT 和推出基本式子是基本功)

干脆改名叫组合数学竞赛吧(鼓掌)。

CMO Au 都不一定能做出吧。

注意模意义下单位根是 $ g^{P-1\over 2^k}, 2^k\ge2N $ .

如果预计多项式操作后度数是 $ N $ ,那么求当前单位根系数的时候是需要用到 $ 2N $ .

做个好孩子变量要好好取名。

Code(34060kb, 28388ms)

#include <bits/stdc++.h>
using namespace std;
template<class T> void read(T& x)
{
    char c = getchar(); T p = 1, n = 0;
    while(c < '0' || c > '9') {if(c == '-') p = -1; c = getchar();}
    while(c >= '0' && c <= '9'){n = n * 10 + c - '0'; c = getchar();}
    x = p * n;
}
template<class T,class U>void read(T&x,U&y){read(x),read(y);}
template<class T,class U,class V>void read(T&x,U&y,V&z){read(x),read(y),read(z);}
const long long mod = 998244353, g = 3;
const int maxn = 1 << 20;
inline int power(int a, int b){int ret = 1;for(; b; b >>= 1, a = 1ll * a * a % mod) if(b & 1) ret = 1ll * ret * a % mod; return ret;}
int eps[maxn], inv_eps[maxn];
int C[maxn], N, bitrev[maxn];
void FFT(int *A, int n, int *w = eps)
{
    for(int i = 0; i < n; ++i) if(i < bitrev[i]) swap(A[i], A[bitrev[i]]);
    for(int s = 1; s < n; s <<= 1) for(int i = 0; i < n; i += s << 1)
    {
        int t = N * 2 / (s << 1);
        for(int j = i, k = 0; j < i + s; ++j, k += t)
        {
            int p = A[j], q = 1ll * A[j + s] * w[k] % mod;
            A[j] = (p + q) % mod;
            A[j + s] = (p - q + mod) % mod;
        }
    }
}
void IFFT(int *A, int n)
{
    FFT(A, n, inv_eps);
    int inv = power(n, mod - 2);
    for(int i = 0; i < n; ++i) A[i] = 1ll * A[i] * inv % mod;
}
int T[maxn], S[maxn];
void inverse(int *A, int *B, int n = N)
{
    if(n == 1){B[0] = power(A[0], mod - 2); return;}
    int half = (n) >> 1;
    inverse(A, B, half);
    int p = 1, l = -1; for(; p < (n << 1); p <<= 1, ++l);
    for(int i = 0; i < p; ++i) bitrev[i] = bitrev[i >> 1] >> 1 | ((i & 1) << (l));
    fill(B + half, B + p, 0);
    FFT(B, p);
    fill(S, S + p, 0);
    copy(A, A + n, S);
    FFT(S, p);
    for(int i = 0; i < p; ++i) B[i] = (2ll * B[i] % mod - 1ll * S[i] * B[i]% mod * B[i] % mod + mod) % mod;
    IFFT(B, p);
}
int inv2;
void square_root(int *A, int *B, int n = N)
{
    if(n == 1) {B[0] = 1; return;}
    square_root(A, B, (n) >> 1);
    int half = (n) >> 1;
    int p = 1, l = -1; for(; p < (n << 1); p <<= 1, ++l);
    for(int i = 0; i < p; ++i) bitrev[i] = bitrev[i >> 1] >> 1 | ((i & 1) << (l));
    fill(B + half, B + n, 0);
    fill(T, T + n, 0);
    inverse(B, T, n);
    fill(T + n, T + p, 0);
    fill(B + half, B + p, 0);
    FFT(T, p);
    FFT(B, p);
    fill(S, S + p, 0);
    copy(A, A + n, S);
    FFT(S, p);
    for(int i = 0; i < p; ++i) B[i] = 1ll * (S[i] + (1ll * B[i] * B[i] % mod)) % mod * T[i] % mod * inv2 % mod;
    IFFT(B, p);
}
int P[maxn], Q[maxn];
int main()
{
    inv2 = power(2, mod - 2);
    int n, m; read(n, m);
    for(int t; n--; ) read(t), C[t] = mod - 4; ++C[0];
    for(N = 1; N <= m; N <<= 1);
    int base = power(g, (mod - 1) / (N * 2)), invbase = power(base, mod - 2);
    eps[0] = inv_eps[0] = 1;
    for(int i = 1; i < N * 2; ++i) eps[i] = 1ll * eps[i - 1] * base % mod, inv_eps[i] = 1ll * inv_eps[i - 1] * invbase % mod;
    square_root(C, P);
    ++P[0];
    inverse(P, Q);
    for(int i = 1; i <= m; ++i) printf("%d\n", 2ll * Q[i] % mod);
    return 0;
}

BZOJ 3622 容斥 二项式反演

BZOJ 3622 容斥 二项式反演

给长度一样两组数。问有多少种两两配对的方式使得前面一个数组的数比对应的数大的对数恰好为 $ k $ 对。模 $ 10^9+9 $ .

$ n,k \le 2000 $ .

Sol.

记 $ G_k :=$ 恰好 $ k $ 组的方案数,$ F_k := $ 至少*有 $ k $ 组的方案数。

又令 $ f_{i,j} := $ 在 $ a_{1..i} $ 中选 $ j $ 个数恰好比对应的 $ b $ 组大的方案数,有转移 $ f_{i,j}=f_{i-1,j}+f_{i-1,j-1}\cdot(t_i-j+1) $ ,其中 $ t_i $ 表示 $ a_i $ 比 $ b $ 的多少个数大。

那么 $ F_k=f_{n,k}\cdot (n-k)! $ ,表示剩下的数随便选。

此时注意到 (*) 标记的定义实际上有问题,会有重复计算,准确的说每个 $ G_k $ 会给 $ F_n $ 贡献 $ n\choose k $ 种情况,即

$ F_k=\sum_{i=k}^n{i\choose k}G_i $ ,二项式反演后为

$$ G_k=\sum_{i=k}^n(-1)^{i-k}{i\choose k}F_i $$

$ O(n^2) $ 计算即可。


(*) 标记处的定义困扰了我很久。问 @whj 为啥不能直接差分得到恰好的情况,讨论后发现这种算法其实本来就是会重复计算的,也就是说名实不符,$ F $ 根本不是一个所谓的“至少”的计数对象。

以及注意模数。

Code (64168kb, 1104ms)

#include <bits/stdc++.h>
using namespace std;
template<class T> void read(T& x)
{
    char c = getchar(); T p = 1, n = 0;
    while(c < '0' || c > '9') {if(c == '-') p = -1; c = getchar();}
    while(c >= '0' && c <= '9'){n = n * 10 + c - '0'; c = getchar();}
    x = p * n;
}
template<class T,class U>void read(T&x,U&y){read(x),read(y);}
template<class T,class U,class V>void read(T&x,U&y,V&z){read(x),read(y),read(z);}
const int maxn = 2e3 + 5, mod = 1e9 + 9;
long long f[maxn][maxn], p[maxn], q[maxn], t[maxn], C[maxn][maxn], fac[maxn];
int main()
{
    int n, k; read(n, k); k = n + k >> 1;
    for(int i = 1; i <= n; ++i) read(p[i]);
    for(int i = 1; i <= n; ++i) read(q[i]);
    sort(p + 1, p + n + 1); sort(q + 1, q + n + 1);
    for(int i = 1; i <= n; ++i) 
        for(int j = (t[i] = t[i - 1]) + 1; j <= n && q[j] < p[i]; ++j, ++t[i]);
    for(int i = 0; i <= n; ++i) f[i][0] = 1;
    for(int i = 1; i <= n; ++i) for(int j = 1; j <= i; ++j)
        f[i][j] = (f[i - 1][j] + f[i - 1][j - 1] * max(0ll, t[i] - j + 1) % mod) % mod;
    for(int i = 0; i <= n; C[i][0] = 1, ++i) 
        for(int j = 1; j <= i; ++j)
            C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % mod;
    fac[0] = 1; for(int i = 1; i <= n; ++i) fac[i] = fac[i - 1] * i % mod;
    long long ans = 0;
    for(int i = k, sgn = 1; i <= n; ++i, sgn = -sgn)
        (ans += C[i][k] * f[n][i] % mod * fac[n - i] % mod * sgn + mod) %= mod;
    printf("%lld\n", ans);
    return 0;
}

BZOJ 3563 & 3569 dfs 树 线性基

BZOJ 3563 & 3569 dfs 树 线性基

给一张图,在线询问删掉边集 $ K $ 后还连不连通。

$ |V|\le10^5,|E|\le5\times10^5,|Q|\le5\times10^4,|K|\le15 $ .

Sol.

注意到不删去 dfs 树上的边的话原图一定联通。那么我们只需要知道删掉一些树边和返祖边之后原图是否连通。

又注意到一条返祖边会覆盖若干条树边,那么这个环内必须至少也有一条树边被删除才能使得不连通。

如果删的边都在树上,那么若存在覆盖其的返祖边是一些子集的对称差可以生成其,才可以。直观的话可以想象如何才能在这个边集里面找到同在一个环里面的边。

形式的话来说,给每一条返祖边一个随机变量 $ X_i $ 而树边的权值为 $ \oplus X_j $ , $j $ 为覆盖其的返祖边,那么删掉一个边集不连通当且仅当 $ X_i(i\in K) $ 总是线性相关的。

[20180405 upd.]

惊了,突然发现这个证明不简单。贴两个链接先 suspend

dwj's

whx's

3563 其实只需用并查集处理最后一个询问就好了。懒得打。

只贴 3569 的代码。

Code

#include <bits/stdc++.h>
using namespace std;
template<class T> void read(T& x)
{
    char c = getchar(); T p = 1, n = 0;
    while(c < '0' || c > '9') {if(c == '-') p = -1; c = getchar();}
    while(c >= '0' && c <= '9'){n = n * 10 + c - '0'; c = getchar();}
    x = p * n;
}
template<class T,class U>void read(T&x,U&y){read(x),read(y);}
template<class T,class U,class V>void read(T&x,U&y,V&z){read(x),read(y),read(z);}
const int maxn = 5e5 + 10;
struct E{int v, n, w; }e[maxn << 1];
int h[maxn], ec = 2;
inline void add_edge(int u, int v, int w){e[ec] = (E){v, h[u], w}; h[u] = ec++;}
bool vis[maxn], tree[maxn];
void dfs(int u)
{
    vis[u] = true;
    for(int i = h[u], v = e[i].v; i; i = e[i].n, v = e[i].v) if(!vis[v])
        tree[e[i].w] = true, dfs(v);
}
unsigned long long w[maxn], num[maxn];
void dfs2(int u, int f = 0)
{
    for(int i = h[u], v = e[i].v; i; i = e[i].n, v = e[i].v) if(tree[e[i].w] && v != f)
        dfs2(v, u), num[e[i].w] ^= w[v], w[u] ^= num[e[i].w];
}
inline unsigned long long Rand(){return rand();}
inline unsigned long long getrand(){return Rand() | (Rand() << 16);}

unsigned long long a[64];
void clear(){memset(a, 0, sizeof a);}
inline bool add(unsigned long long v)
{
    for(int i = 31 ; ~i; --i) if(v >> i & 1)
    {
        if(!v) return false;
         if(a[i]) v ^= a[i];
         else
         {
             a[i] = v;
             for(int j = i - 1; ~j; --j) if(a[i] >> j & 1 && a[j])
                 a[i] ^= a[j];
             return true;
         }
    }
    return false;
}
unsigned long long v[maxn];
int main()
{
    srand(*new char);
    int n, m; read(n, m);
    for(int u, v, i = 1; i <= m; ++i) read(u, v), add_edge(u, v, i), add_edge(v, u, i);
    dfs(1);
    for(int i = 1; i <= m; ++i) if(!tree[i]) num[i] = getrand(), w[e[i << 1].v] ^= num[i], w[e[i << 1 | 1].v] ^= num[i];
    dfs2(1);
    int q; read(q);
    int cnt = 0;
    while(q--)
    {
        int k; read(k);
        memset(a, 0, sizeof a);
        bool flag = false;
        for(int i = 0, c; i < k; ++i) read(c), c ^= cnt, add(num[c]) ? 1 : flag = true;
        if(!flag) puts("Connected"), ++cnt;
        else puts("Disconnected");
    }
    return 0;
}

BZOJ 3105 贪心 线性基

BZOJ 3105 贪心 线性基

与普通 nim 游戏的区别在于前两次可以任意取若干个集合。

Sol.

求极大线性无关集,总和减去这个集合的和即为答案。

线性基按于元素从小到大维护即可。注意不用也不能消成上三角。

为什么不是水题?因为我不会证。

等会了拟阵再补。

Code

#include <bits/stdc++.h>
using namespace std;
template<class T> void read(T& x)
{
    char c = getchar(); T p = 1, n = 0;
    while(c < '0' || c > '9') {if(c == '-') p = -1; c = getchar();}
    while(c >= '0' && c <= '9'){n = n * 10 + c - '0'; c = getchar();}
    x = p * n;
}
template<class T,class U>void read(T&x,U&y){read(x),read(y);}
template<class T,class U,class V>void read(T&x,U&y,V&z){read(x),read(y),read(z);}
const int maxn = 105;
int a[maxn], b[35];
int main()
{
    int k; read(k);
    long long sum = 0, ret = 0;
    for(int i = 0; i < k; ++i) read(a[i]), sum += a[i];
    sort(a, a + k, greater<int>());
    for(int i = 0; i < k; ++i)
    {
        int t = a[i];
        for(int j = 30; ~j; --j) if(a[i] >> j & 1)
        {
            if(b[j]) a[i] ^= b[j];
            else
            {
                b[j] = a[i];
                break; 
            }
        }
        if(a[i]) ret += t;
    }
    if(ret) printf("%lld\n", sum - ret);
    else puts("-1");
    return 0;
}