A、回文括号序列计数

既要是回文又要是括号序列，我们知道回文具有对称性，但是我们写一个回文串就会发现。
类似这种回文串不可能是括号序列，所以只有在的时候存在一个空串，特殊判断即可。

#include <bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
#define all(__vv__) (__vv__).begin(), (__vv__).end()
#define endl "\n"
#define pai pair<int, int>
#define ms(__x__,__val__) memset(__x__, __val__, sizeof(__x__))
#define rep(i, sta, en) for(int i=sta; i<=en; ++i)
#define repp(i, sta, en) for(int i=sta; i>=en; --i)
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar())    s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; }
inline void print(ll x, int op = 10) { if (!x) { putchar('0'); if (op)    putchar(op); return; }    char F[40]; ll tmp = x > 0 ? x : -x;    if (x < 0)putchar('-');    int cnt = 0;    while (tmp > 0) { F[cnt++] = tmp % 10 + '0';        tmp /= 10; }    while (cnt > 0)putchar(F[--cnt]);    if (op)    putchar(op); }
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll qpow(ll a, ll b) { ll ans = 1;    while (b) { if (b & 1)    ans *= a;        b >>= 1;        a *= a; }    return ans; }    ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
const int dir[][2] = { {0,1},{1,0},{0,-1},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1} };
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
struct Node {
    ll val;
    int id;
    bool operator < (const Node& opt) const {
        return val < opt.val;
    }
};

const int N = 1e6 + 7;
ll n, m;
ll p[N];
void solve() {
    n = read();
    if (!n)    print(1);
    else print(0);
}

int main() {
    int T = read();    while (T--)
        solve();
    return 0;
}

B、系数

发现答案可对3取模，又是，我们知道多项式的系数和排列组合有关，所以这个量级使用可以解决组合数问题。剩下的关键就是找到应该求解的组合数式子。
我们观察里面每一项模3，考虑一个转化。把看成，这样在每次挑选幂次的时候还是按照的幂次依次从括号中选取，但是这样在选中1次幂的时候，会选择，当它和别的项累乘时，你会发现它等于，显然后面的一项会等于0，那么也就是说明和在求解系数的时候是等价的。
我们就可以把式子变化为。这个式子的系数求解就很简单了吧。

，还要注意一下我们虽然说等价，但是前面式子可能求解出负数，当求解到负数的时候就加个3变成整数即可。时间复杂度

#include <bits/stdc++.h>
#pragma GCC optimize(2)
#pragma GCC optimize(3)
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
typedef long long ll;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); while (ch < 48 || ch > 57) { if (ch == '-') w = -1; ch = getchar(); }    while (ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();    return s * w; }

// 模数p较小打表 并且前提p是素数
//const int N = 1e5 + 10;
//ll fac[N];//阶乘打表
//void init(ll p) {//此处的p应该小于1e5，这样Lucas定理才适用
//    fac[0] = 1;
//    for (int i = 1; i <= p; i++)
//        fac[i] = fac[i - 1] * i % p;
//}

// 模数p较大直接计算组合数
ll qpow(ll a, ll b, ll m) { //非质数也要用快速幂
    ll ans = 1;
    a %= m;
    while (b) {
        if (b & 1)ans = (ans % m) * (a % m) % m;
        b /= 2;
        a = (a % m) * (a % m) % m;
    }
    ans %= m;
    return ans;
}
ll inv(ll x, ll p) {//x关于p的逆元，p为素数
    return qpow(x, p - 2, p);
}

// p较小情况
//ll C(ll n, ll m, ll p){//组合数C(n, m) % p
//    if (m > n)return 0;
//    return fac[n] * inv(fac[m] * fac[n - m], p) % p;
//}

ll C(ll n, ll m, ll p) {//组合数C(n, m) % p
    if (m > n)return 0;
    ll up = 1, down = 1;//分子分母;
    for (int i = n - m + 1; i <= n; i++)up = up * i % p;
    for (int i = 1; i <= m; i++)down = down * i % p;
    return up * inv(down, p) % p;
}
ll lucas(ll n, ll m, ll p) {
    if (m == 0)return 1;
    return C(n % p, m % p, p) * lucas(n / p, m / p, p) % p;
}

int main() {
    int T = read();
    while (T--) {
        ll n = read(), k = read();
        int ans = lucas(2 * n, k, 3);
        if (k & 1)    ans = (3 - ans) % 3;
        printf("%d\n", ans);
    }
    return 0;
}

C、末三位

可以找规律，也可以直接快速幂，规律就按照奇偶分类就行。

void solve() {
    while (~scanf("%lld", &n)) {
        int ans = qpow(5, n, MOD);
        printf("%03d\n", ans);
    }
}

D、划数

最后剩下的一个数一定是，所以这个数一定没有处理过，也就是表明其他数都被算过了，直接求合算一下即可。注意特判的情况。

const int N = 1e6 + 7;
ll n, m;
ll p[N];
void solve() {
    int m = read();
    bool flag = 1;
    rep(i, 1, n) {
        p[i] = read();
        if (p[i] == m and flag)
            p[i] = 0, flag = 0;
    }
    if (n == 2) {
        int ans = max(p[1], p[2]);
        print(ans);
        return;
    }
    rep(i, 1, n) {
        p[i] = (p[i] + p[i - 1]) % 11;
    }
    print(p[n]);
}

E、网格

每一个格点只能在左右选一个方向，也只能在上下选一个方向，那么可以看出他们对于选择是独立的。我们分行列处理。
我们处理行的时候，使用数组，代表当前行的第列的方向选择是往左还是往右，那么知道当前行的第一个点只能选择往右，第二个点可以选择往右也可以选择往左，在第三个点开始往后就有明显的转移规律了。

处理完列之后，把行一样的按照选择方向的上下处理，预处理每个数的一的数量可以把时间复杂度做到。

const int N = 1e3 + 7;
ll n, m;
int cnt[N * 3];
int a[N][N], f[N][2];

// f[i][0/1] 代表某一行中第i列数往左(0)往右(1)选择的最大值
// 同理用在行中计算时往上是(0)往下是(1)

int calc(int x) { return x + cnt[x]; }

void solve() {
    rep(i, 1, 3000)    cnt[i] = cnt[i & (i - 1)] + 1;
    n = read(), m = read();
    rep(i, 1, n)
        rep(j, 1, m)    a[i][j] = read();
    ll ans = 0;
    rep(i, 1, n) {
        f[2][0] = calc(a[i][1] ^ a[i][2]); // 第二个数只能往左才会产生贡献
        f[2][1] = 0;
        rep(j, 3, m) {
            f[j][0] = max(f[j - 1][0], f[j - 1][1] + calc(a[i][j] ^ a[i][j - 1]));
            f[j][1] = max(f[j - 1][0], f[j - 1][1]);
        }
        ans += max(f[m][0], f[m][1]);
    }
    rep(j, 1, m) {
        f[2][0] = calc(a[1][j] ^ a[2][j]); // 第二个数只能往上才会有贡献
        f[2][1] = 0;
        rep(i, 3, n) {
            f[i][0] = max(f[i - 1][0], f[i - 1][1] + calc(a[i][j] ^ a[i - 1][j]));
            f[i][1] = max(f[i - 1][0], f[i - 1][1]);
        }
        ans += max(f[n][0], f[n][1]);
    }
    print(ans);
}

F、组合数问题

正解使用的是复数的快速幂，因为本人暂时没看到他如何转换的，所以就不多介绍了 赛中我解题的方法是暴力找出前