【WC2016】论战捆竹竿

已经*周了啊……终于把坑填了……

首先显然是把除了自身的所有border拿出来，即做 \(\left\{ n - b_1, n - b_2, \dots, n - b_k, n \right\}\) 的完全背包。但是值域很大，所以考虑同余最短路。

首先，由 [国家集训队]墨墨的等式的经验，显然可以 \(O(n^2)\)，因为最长border可以很小，所以可以卡到满。

然后就要一个性质：一个串的border可以分成 \(O\left( \log n \right)\) 个等差数列。证明咕咕咕。

有了这个，就可以干一些有趣的事：

考虑一个有趣的暴力，每次更新一个首项为 \(x\)，公差为 \(d\) 的等差数列时，可以把点按模 \(d\) 剩余系分类，这样子dp更新的区间是连续的。线段树搞搞，因为没有负权所以可以跑dijkstra，然后同样可以不保存边。最后再像之前那题的经验，每个等差数列分别更新。这样复杂度两个 \(\log\)，空间 \(O\left(n\right)\)。（来自官方题解）

然而这样做复杂度还是太大了。能不能不用线段树啊？

我们要将一个等差数列有效边压到 \(O(n)\)，那么也就剩余系有希望了。

观察到一个等差数列是 \(\left[x, x + d, x + 2d, \dots\right]\)，可以考虑模 \(x\)，然后在模 \(x\) 的剩余系下转移，显然还是构成了一堆环。

先考虑如果是在模 \(x\) 意义下的情况的DP转移，注意到等差数列长度的限制，转移点不能太远，因此考虑单调队列维护（也就是滑动窗口类似的）。

然后考虑如何在模 \(P\) 意义下转换为模 \(Q\)。

如果直接将所有能搞出的方案放进去，发现能表示出来的都是 \(dis_i + k \cdot P\) 类型的，这启发我们先把所有 \(dis_i\) 扔到模 \(Q\) 意义下序列上，然后用 \(P\) 更新同余最短路，这样同样能表示出 \(dis_i + k \cdot P\) 了。

所以找出所有等差数列后，对于每个数列分别先转换模数，再做dp转移。注意这道题卡常数（该优化的都优化上去就好了，比如下标加的时候用取模优化）。

我写挂一堆地方：直接拿border长度上去DP，单调队列少个等号，转换模数时用了 \(i\) 而不是 \(dis_i\) 初始化……

#include <bits/stdc++.h>
struct data {
    int x, d, c;
    data() { x = d = c = 0; }
    bool ins(int v) {
        if (!c) return x = v, d = 0, c = 1, true;
        if (!d) return d = v - x, c = 2, true;
        if (x + c * d == v) return ++c, true;
        return false;
    }
} ;
const int MAXN = 500010;
typedef long long LL;
const LL INF = 0x3f3f3f3f3f3f3f3fLL;
typedef std::vector<data> V;
struct KMP {
    int nxt[MAXN];
    V build(char * buf, int len) {
        for (int i = 1; i <= len; ++i) {
            int now = nxt[i - 1];
            while (now && buf[now + 1] != buf[i]) now = nxt[now];
            nxt[i] = buf[now + 1] == buf[i] && now + 1 != i ? now + 1 : 0;
        }
        V res; data rt; int now = nxt[len];
        while (now) {
            if (!rt.ins(now))
                res.push_back(rt), (rt = data()).ins(now);
            now = nxt[now];
        }
        if (rt.x) res.push_back(rt);
        for (auto & t : res)
            t.x = len - t.x, t.d = -t.d;
        std::reverse(res.begin(), res.end());
        return res;
    }
} kmp;

int n; LL W;
LL dis[MAXN];
int mod;
void getmax(LL & x, LL y) { x < y ? x = y : 0; }
void getmin(LL & x, LL y) { x > y ? x = y : 0; }
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
void trans(int v) {
    static LL d2[MAXN];
    memset(d2, 0x3f, v << 3);
    for (int i = 0; i < mod; ++i) getmin(d2[dis[i] % v], dis[i]);
    const int G = gcd(v, mod);
    for (int i = 0; i < G; ++i) {
        int at = i;
        int tm = mod % v;
        for (int j = (i + mod) % v; j != i; j += tm - v, j += j >> 31 & v)
            if (d2[j] < d2[at]) at = j;
        LL now = d2[at] + mod;
        for (int j = (at + mod) % v; j != at; j += tm - v, j += j >> 31 & v)
            getmin(d2[j], now), now = std::min(now, d2[j]) + mod;
    }
    mod = v;
    memcpy(dis, d2, mod << 3);
}
struct qnode {
    LL v; int at;
    qnode() { v = at = 0; }
    qnode(LL x, int y) { v = x, at = y; }
} Q[MAXN];
void dp(int v, int D, int C) {
    trans(v);
    const int G = gcd(v, D);
    for (int i = 0; i < G; ++i) {
        int at = i;
        int tm = D % v;
        for (int j = (i + D) % v; j != i; j += tm - v, j += j >> 31 & v)
            if (dis[j] < dis[at]) at = j;
        int qb = 1, qe = 0;
        for (int j = at, k = 0; k * G != v; j += tm - v, j += j >> 31 & v, ++k) {
            while (qb <= qe && Q[qb].at + C <= k) ++qb;
            if (qb <= qe) {
                auto x = Q[qb];
                getmin(dis[j], v + x.v + (k - x.at) * D);
            }
            while (qb <= qe && Q[qe].v + (k - Q[qe].at) * D >= dis[j]) --qe;
            Q[++qe] = (qnode) {dis[j], k};
        }
    }
}

int main() {
    std::ios_base::sync_with_stdio(false), std::cin.tie(0);
    int T; std::cin >> T;
    while (T --> 0) {
        static char buf[MAXN];
        std::cin >> n >> W >> buf + 1; W -= n;
        mod = n; memset(dis, 0x3f, n << 3); *dis = 0;
        for (auto t : kmp.build(buf, n)) dp(t.x, t.d ? t.d : 1, t.c);
        LL ans = 0;
        for (int i = 0; i != mod; ++i)
            dis[i] <= W ? ans += (W - dis[i]) / mod + 1 : 0;
        std::cout << ans << std::endl;
    }
    return 0;
}

【WC2016】论战捆竹竿

相关推荐