扫描线，数论 + 找规律，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$ 即可。

暴力能得 60pts 真・良心。

本题正解是 $dp$ 。

我们设 $dp[i][j][k]$ 表示到了第 $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;
	}