扫描线，数论 + 找规律，dp + kmp

# A. 【常中20180915T1】（第一套）牧场

扫描线求周长板子（

然而并不会写线段树优化的，于是写了个 $O(nL)$ 的暴力，神奇的得到了 90pts ！！！

# B. 【常中20180921】（第二套）C

解决这道题有两种方法：

打表
推结论

打表就不说了，这里来讲讲怎么推。

当 $a = b$ 时，显然不合法。

假设 $a > b$ ，

那么 $\gcd(a, b) \leq a - b$ ， $a\ xor\ b \geq a - b$ 。

很显然吧。

于是我们枚举一个 $\gcd$ 为 $d$ ，然后枚举它的倍数，判断 $k \times d\ xor\ (k - 1) \times d$ 是否等于 $d$ 即可。

# C. 【常中20180812T2】track

暴力能得 60pts 真 · 良心。

本题正解是 $dp$ 。

我们设 $dp[i][j][k]$ 表示到了第 $i$ 个路口，匹配输入的字符串匹配到了第 $j$ 位，此时的高度是 $k$ 的方案数。

转移方程分两种情况：

继续匹配下一个字符： $dp[i + 1][j + 1][k + a[j + 1]] += dp[i][j][k]$
不匹配下一个字符： $dp[i + 1][Next(j)][k - a[j + 1]] += dp[i][j][k]$

$Next(j)$ 就是先做个 $kmp$ ，然后在 $nxt$ 数组上往前跳匹配点。

最后统计答案时，考虑正难则反。

先计算出总方案数，也就是卡特兰数 $C_n^{\frac n2} - C_n^{\frac n2 - 1}$ 。

然后减去不合法的即可。

$code$

#include <bits/stdc++.h>
#define ll long long

using namespace std;

const int N = 210;
const int mod = 1e9 + 7;
int n, m;
char s[N];
int a[N], nxt[N];
ll f[N][N][N], fac[N];

inline int Next(int pos, char c){
    while(pos && s[pos + 1] != c) pos = nxt[pos];
    return s[pos + 1] == c ? pos + 1 : pos;
}

inline ll qpow(ll a, int b){
    ll res = 1;
    while(b){
        if(b & 1) res = res * a % mod;
        a = a * a % mod, b >>= 1;
    }
    return res;
}

inline ll C(int n, int m){
    if(n < m) return 0;
    return fac[n] * qpow(fac[m], mod - 2) % mod * qpow(fac[n - m], mod - 2) % mod;
}

int main(){
    scanf("%d%s", &n, s + 1);
    if(n & 1) return puts("0"), 0;
    m = strlen(s + 1);
    for(int i = 1; i <= m; ++i) a[i] = (s[i] == 'U' ? 1 : -1);
    for(int i = 2, j = 0; i <= m; ++i){
        while(j && a[j + 1] != a[i]) j = nxt[j];
        if(a[j + 1] == a[i]) j++;
        nxt[i] = j;
    }
    f[0][0][0] = 1;
    for(int i = 0; i < n; ++i)
        for(int j = 0; j <= min(i, m - 1); ++j)
            for(int k = 0; k <= i; ++k){
                if(k >= -a[j + 1]) (f[i + 1][j + 1][k + a[j + 1]] += f[i][j][k]) %= mod;
                if(k >= a[j + 1]) (f[i + 1][Next(j, s[j + 1] == 'U' ? 'D' : 'U')][k - a[j + 1]] += f[i][j][k]) %= mod;
            }
    fac[0] = 1;
    for(int i = 1; i <= n; ++i) fac[i] = fac[i - 1] * i % mod;
    ll ans = C(n, n >> 1) - C(n, (n >> 1) - 1);
    for(int i = 0; i < m; ++i)
        ans = (ans - f[n][i][0] + mod) % mod;
    printf("%lld\n", ans);
    return 0;
}

# A. 【常中20180915T1】（第一套）牧场

# B. 【常中20180921】（第二套）C

# C. 【常中20180812T2】track

20220210

CF17E Palisection 题解