已經快三周了啊……終于把坑填了……

首先顯然是把除了自身的所有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; }

轉載于:https://www.cnblogs.com/daklqw/p/11606992.html

總結

以上是生活随笔為你收集整理的【WC2016】论战捆竹竿的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。