D. Dark LaTeX vs. Light LaTeX

题意：

给你两个字符串、，分别从 和 中找出一段非零的、连续的子串，将组成 = + ，要求长度为偶数，且前一半与后一半相等。输出满足这样的条件的字符串的数量（可以重复）。

input

abab
ab

output

8

数据范围

，

分析

首先思考：我们应该怎么找，才能不重不漏呢？我们为什么会有这样的问题？因为我们有两个串。

但我们只考虑一个串的时候，会有很多方法能够做到这一点。进一步的，如果，那我们发现短的这个串是被长的这个串给限制住的。但是如果我们只有短的串，长的串会有很多情况。因此我们可以想到我们可以枚举长串，这样的短串是固定的，直接加上短串的数量即可。后面约定 。

好现在我们已经确定好顺序了。既然的前半等于后半，那么可以知道的是，至少存在一个前缀等于后缀。但是这样还是很复杂，我们应该对此进行优化。我们发现长串决定短串，而的全部信息都在中，为什么不枚举的前半部分呢？即枚举的，这样其实就已经确定了。

如果，直接不可能。
如果，有多少情况？我们发现可扩展的长度是和的。比如，我们找到，有这样两个串：，，这两个串都是前缀等于后缀的。也就是和的个。对于这两个串，我们发现我们要找的是：、。此时又可以发现，这两个串都是以为结尾的。原因很显然，无论是多少，是必然要找的，但是前面可以缩短。也就是。

我们貌似还是不好统计。但是“固定”这个性质是非常好的。记 为 中以 结尾、 中以 结尾的最长长度。现在 = 。如果 大于，那么贡献就是。如果小于，贡献就是0。否则就是 。发现我们这一步用到的性质，是中的一个位置（），与 中所有的位置的信息。我们可以对中的每一个位置开一个数组。如果我现在需要找长度为，那么有以下性质：
||贡献|
|---|---|
|||
|||
|||
|||
|||
|||

最后处理一下长度相等的。信息可以在数组中得到。
为方便处理长串和短串，在讨论的时候，对和进行即可。
所以我们只需求出和即可。时间复杂度。

code

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define X first
#define Y second
#define umap unordered_map
using ll = long long;
using ull = unsigned long long;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int maxn = 2e5 + 5, mod = 1e9 + 7, maxp = 31, inf = 1e9;
const ll INF = 1e18;
const double eps = 1e-6;
const int N = 5005;

int lcs[N][N], lcp[N][N];
int f[N][N], g[N][N];

void solve() {
    string ss, tt;
    cin >> ss >> tt;
    const int n = ss.size(), m = tt.size();
    ll ans = 0;

    bool ok = true;

    auto work = [&](string s, string t) {
        const int n = s.size(), m = t.size();
        s = " " + s;
        t = " " + t;
        const int N = max(n, m);

        memset(lcp, 0, sizeof lcp);
        memset(lcs, 0, sizeof lcs);
        memset(f, 0, sizeof f);
        memset(g, 0, sizeof g);

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (s[i] == t[j]) {
                    lcs[i][j] = lcs[i - 1][j - 1] + 1;
                }
                else {
                    lcs[i][j] = 0;
                }
            }
        }

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                int len = lcs[i][j];
                if (len) {
                    f[i][len]++;
                    if (ok) {
                        ans += len;
                    }
                }
            }
        }

        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                g[i][j] = j * f[i][j] + g[i][j - 1];
            }
        }

        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                f[i][j] += f[i][j - 1];
            }
        }

        for (int i = n; i >= 1; i--) {
            for (int j = i - 1; j >= 1; j--) {
                if (s[i] == s[j]) {
                    lcp[j][i] = lcp[j + 1][i + 1] + 1;
                }
                else {
                    lcp[i][j] = 0;
                }
            }
        }
    
        // 这里枚举的位置是l和r + 1
        for (int p1 = 1; p1 <= n; p1++) {
            for (int p2 = p1 + 2; p2 <= n; p2++) {
                if (p2 == p1 + 1) continue;
                int lo = max(1, p2 - (p1 + lcp[p1][p2] - 1) - 1);
                int hi = p2 - p1 - 1;
                int len = hi - lo + 1;
                ans += g[p2 - 1][hi] - g[p2 - 1][lo - 1] - 1ll * (lo - 1) * (f[p2 - 1][hi] - f[p2 - 1][lo - 1]) + 1ll * (f[p2 - 1][m] - f[p2 - 1][hi]) * len;
            }
        }

        ok = false;
    };

    work(ss, tt);
    reverse(ss.begin(), ss.end());
    reverse(tt.begin(), tt.end());
    work(tt, ss);

    cout << ans << endl;
} 

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int tt = 1;
    // cin >> tt;
    while (tt--) solve();
    return 0;
}

I. Three Rectangles

看似过题人数I < B < D，实际I题非常非常水。

题意：

给你一个高为，宽为的长方形，再给你三个小长方形， () 和 ()，不能越界、旋转，但是可以重叠，问有多少方案数，使得这个大长方形能被三个小长方形铺满。答案对取模。

input

10

2 2
1 1
1 1
1 1

2 2
1 1
1 2
1 2

2 2
1 1
1 2
2 1

2 2
1 2
1 2
1 2

2 2
1 2
1 2
2 1

1 3
1 1
1 2
1 3

1 4
1 1
1 2
1 3

1 5
1 1
1 2
1 3

1 6
1 1
1 2
1 3

1000000000 1000000000
1 1
1 1
1000000000 1000000000

output

0
8
4
6
4
6
12
14
6
2401

数据范围

有样例数，；
。

分析

切入点是四个角。这四个角上是肯定要放的。所以想枚举四个角放谁。
但是这样是有问题的。如果一个长方形占了两个角甚至四个角呢？想到这个点之后就有新的思路了。如果有一个长方形占了大于一个角，那么肯定有。有了这个新想法，我们就可以从这个想法入手了。分以下几种情况。

下面记为的个数。同理，swap即可。
1. 存在 and 。此时随便放即可。

if (h[i] == H && w[i] == W) {
    ll ans = 1;
    for (int j = 0; j < 3; j++) {
        ans = ans * (H - h[j] + 1) % mod * (W - w[j] + 1) % mod;
    }
    cout << ans << endl;
    return;
}

2. 。这是最复杂的一种情况了，但也不难。此时长方形退化成了一条线段。因为要做到不重不漏，我们可以枚举谁靠着最左端（下称），谁靠着最右端（下称）。因为有可能有重叠的部分会重复计算（重叠是指有两个放在最左端，两个放在最右端），因此我们分离开来。

• 先讨论不重叠的情况。如果，那么除了最左最右端是随便放的。否则，能放的最大位置就是贴着，能放的最小位置就是贴着。
• 那么重叠的部分呢？显然不可能三个都贴着一端。此时枚举谁单独在一端就行了，剩下两个重叠。由于左右端可以互换，因此一旦满足就需要。

if (cnt == 3) {
    ll s = 0;
    for (int i = 0; i < 3; i++) {
        s += w[i];
    }
    if (s < W) {
        cout << 0 << endl;
        return;
    }

    vector<int> p(3);// p与上文意义相同
    iota(p.begin(), p.end(), 0);
    ll ans = 0;
    do {
        if (w[p[0]] + w[p[2]] < W) {
            ll mn = max(1ll, W - w[p[2]] - w[p[1]]);
            ll mx = min(W - w[p[1]] - 1, w[p[0]]);
            ans += mx - mn + 1;
            ans %= mod;
        }
        else {
            ans += max(0ll, W - w[p[1]] - 1);
            ans %= mod;
        }
    } while (next_permutation(p.begin(), p.end()));

    for (int i = 0; i < 3; i++) {
        for (int j = i + 1; j < 3; j++) {//i和j是两个重叠的
            int k = 3 - i - j;
            if (max(w[i], w[j]) + w[k] >= W) {
                ans += 2;
            }
        }
    }
    cout << ans % mod << endl;
    return;
}

3. 。这就非常好判断了。你会发现如果满足的这两个中间留了一条缝，那么答案肯定是。否则，这两个已经把所有空间占满了。剩下的那个随便放即可。

if (cnt == 2) {
    int p1 = -1, p2 = -1;
    for (int i = 0; i < 3; i++) {
        if (h[i] == H) {
            if (p1 == -1) {
                p1 = i;
            }
            else {
                p2 = i;
            }
        }
    }

    int p3 = 3 - p1 - p2;
    if (w[p1] + w[p2] >= W) {
        cout << 2 * (W - w[p3] + 1) * (H - h[p3] + 1) % mod << endl;
    }
    else {
        cout << 0 << endl;
    }
    return;
}

4. 。剩下两个不满足的如果不能把填满，答案是0；或者不能把填满的，答案为0。否则上下互换，左右互换，。

for (int i = 0; i < 3; i++) {
    if (h[i] == H) {
        ll mn = inf, s = 0;
        for (int j = 0; j < 3; j++) {
            if (j == i) continue;
            s += h[j];
            mn = min(mn, w[j]);
        }

        if (s >= H && mn + w[i] >= W) {
            cout << 4 << endl;
            return;
        }
    }
}

5. 。只能占三个角。答案是0。
   时间复杂度。（带点常数，问题不大
   最后贴个总代码

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define X first
#define Y second
#define umap unordered_map
using ll = long long;
using ull = unsigned long long;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int maxn = 2e5 + 5, mod = 1e9 + 7, maxp = 31, inf = 1e9;
const ll INF = 1e18;
const double eps = 1e-6;

void solve() {
    ll H, W;
    cin >> H >> W;
    vector<ll> w(3), h(3);
    for (int i = 0; i < 3; i++) {
        cin >> h[i] >> w[i];
    }

    for (int i = 0; i < 3; i++) {
        if (h[i] == H && w[i] == W) {
            ll ans = 1;
            for (int j = 0; j < 3; j++) {
                ans = ans * (H - h[j] + 1) % mod * (W - w[j] + 1) % mod;
            }
            cout << ans << endl;
            return;
        }
    }

    int cnt = 0;
    for (int i = 0; i < 3; i++) {
        if (h[i] == H) {
            cnt++;
        }
    }


    if (cnt == 3) {
        ll s = 0;
        for (int i = 0; i < 3; i++) {
            s += w[i];
        }
        if (s < W) {
            cout << 0 << endl;
            return;
        }

        vector<int> p(3);
        iota(p.begin(), p.end(), 0);
        ll ans = 0;
        do {
            if (w[p[0]] + w[p[2]] < W) {
                ll mn = max(1ll, W - w[p[2]] - w[p[1]]);
                ll mx = min(W - w[p[1]] - 1, w[p[0]]);
                ans += mx - mn + 1;
                ans %= mod;
            }
            else {
                ans += max(0ll, W - w[p[1]] - 1);
                ans %= mod;
            }
        } while (next_permutation(p.begin(), p.end()));

        for (int i = 0; i < 3; i++) {
            for (int j = i + 1; j < 3; j++) {
                int k = 3 - i - j;
                if (max(w[i], w[j]) + w[k] >= W) {
                    ans += 2;
                }
            }
        }
        cout << ans % mod << endl;
        return;
    }

    if (cnt == 2) {
        int p1 = -1, p2 = -1;
        for (int i = 0; i < 3; i++) {
            if (h[i] == H) {
                if (p1 == -1) {
                    p1 = i;
                }
                else {
                    p2 = i;
                }
            }
        }

        int p3 = 3 - p1 - p2;
        if (w[p1] + w[p2] >= W) {
            cout << 2 * (W - w[p3] + 1) * (H - h[p3] + 1) % mod << endl;
        }
        else {
            cout << 0 << endl;
        }
        return;
    }

    swap(H, W);
    swap(h, w);

    cnt = 0;
    for (int i = 0; i < 3; i++) {
        if (h[i] == H) {
            cnt++;
        }
    }

    cnt = 0;
    for (int i = 0; i < 3; i++) {
        if (h[i] == H) {
            cnt++;
        }
    }


    if (cnt == 3) {
        ll s = 0;
        for (int i = 0; i < 3; i++) {
            s += w[i];
        }
        if (s < W) {
            cout << 0 << endl;
            return;
        }

        vector<int> p(3);
        iota(p.begin(), p.end(), 0);
        ll ans = 0;
        do {
            if (w[p[0]] + w[p[2]] < W) {
                ll mn = max(1ll, W - w[p[2]] - w[p[1]]);
                ll mx = min(W - w[p[1]] - 1, w[p[0]]);
                ans += mx - mn + 1;
                ans %= mod;
            }
            else {
                ans += max(0ll, W - w[p[1]] - 1);
                ans %= mod;
            }
        } while (next_permutation(p.begin(), p.end()));

        for (int i = 0; i < 3; i++) {
            for (int j = i + 1; j < 3; j++) {
                int k = 3 - i - j;
                if (max(w[i], w[j]) + w[k] >= W) {
                    ans += 2;
                }
            }
        }
        cout << ans % mod << endl;
        return;
    }

    if (cnt == 2) {
        int p1 = -1, p2 = -1;
        for (int i = 0; i < 3; i++) {
            if (h[i] == H) {
                if (p1 == -1) {
                    p1 = i;
                }
                else {
                    p2 = i;
                }
            }
        }

        int p3 = 3 - p1 - p2;
        if (w[p1] + w[p2] >= W) {
            cout << 2 * (W - w[p3] + 1) * (H - h[p3] + 1) % mod << endl;
        }
        else {
            cout << 0 << endl;
        }
        return;
    }

    swap(H, W);
    swap(h, w);

    for (int i = 0; i < 3; i++) {
        if (h[i] == H) {
            ll mn = inf, s = 0;
            for (int j = 0; j < 3; j++) {
                if (j == i) continue;
                s += h[j];
                mn = min(mn, w[j]);
            }

            if (s >= H && mn + w[i] >= W) {
                cout << 4 << endl;
                return;
            }
        }
    }

    swap(H, W);
    swap(h, w);

    for (int i = 0; i < 3; i++) {
        if (h[i] == H) {
            ll mn = inf, s = 0;
            for (int j = 0; j < 3; j++) {
                if (j == i) continue;
                s += h[j];
                mn = min(mn, w[j]);
            }

            if (s >= H && mn + w[i] >= W) {
                cout << 4 << endl;
                return;
            }
        }
    }

    cout << 0 << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int tt = 1;
    cin >> tt;
    while (tt--) solve();
    return 0;
}

B. Turning Permutation

题意：

令为出现的位置。定义转折序列是指一个排列，对于每个 都有 给你 和 ，求长度为的第大的排列。如果不存在则输出。
### input

3 2

output

2 1 3

数据范围

分析

我们发现转折序列和第 大这两个点是对不上的。转折序列是对于而言的，而 是对原排序而言的。我们应该把这两点并到一起。
在做这些之前，我们分析一下题目本身的性质。
- 给你一个长度为 的排列，能组合出多少种情况？我们考虑递推。表示第一、二个为增大的个数，则是递减。怎么递推？我们考虑放在哪个位置。既然放完了，剩下的数字都是比大的。因此递增递减的顺序就确定了。直接递推即可。结束后发现开始位置递增递减两种的排列个数是相同的。因此直接将定义为长度为 的转折序列的个数。

dp[0] = dp[1] = 2;
for (int i = 2; i <= 23; i++) {
    ll x = 0;
    for (int p = 1; p <= i; p++) {
        int l = p - 1, r = i - p;
        x += C(i - 1, l) * dp[l] / 2 * dp[r] / 2;
    }
    dp[i] = x;
}

发现已经是 的极限了。因此如果，可以直接判断是否有解；否则肯定有解。

接下来把 “转折序列” 和 “第大” 的性质结合。
我们考虑把第 大放到 上去，因为主要的性质在转折序列上。原数组的大小，在 上是怎么体现的？在原数组上，大小是由第一个放谁决定的。转到数组上，那就是 放在哪里决定的。显然，在原数组中，越靠后的位置贡献越小。因此在 数组中， 越大的数字贡献越少。

这下思路就清晰了。我们从小到大枚举每个数放在哪个位置。注意除了 以外，放其他数是有不合法的位置的。比如，我们知道奇数位置上比下一个数小，偶数位置上比下一个数大。一旦 放在第 个，因为后面放的数一定比 大，因此是不满足的。所以这么分析， 和 就一定放在奇数位置上了吗？下面看，就是合法的。因此应当进一步细化。

接下来，如果我们已经确定的一些位置，那么会产生多少种情况呢？我们对于每个区间考虑。找到两个相邻