[AGC040C] Neither AB nor BA

Description

一个长度为 n 的字符串是好的当且仅当它由 'A', 'B', 'C' 组成，且可以通过若干次删除除了"AB"和"BA"的连续子串变为空串。

问有多少个长度为 n 的好串，对 998244353 取模。

\(n\le 10 ^ 7\) , 保证 n 为偶数。

Solution

本题的关键在于转化题意，即找到一个更加简洁抽象的等价条件方便计数。

连续删除两个字符后发现每一个 A 和 B 的奇偶性没有改变。

这说明了奇数位置的 A 一定不能和偶数位置的 B 消除，偶数位置的 A 不能和奇数位置的B消除。

设奇数位置的 A 有 x 个，偶数位置的 B 有 y 个，偶数位置的非 B 字符有 n - y 个，那么必须满足（即必要性）：

\[x \le \frac{n}{2} - y\\
x + y \le \frac n2
\]

所以有：

奇数位置上A的数量 + 偶数位置上B的数量\(\le \frac n 2\)
奇数位置上B的数量 + 偶数位置上A的数量\(\le \frac n 2\)

必要性显然。

仿照上式子记为：

\[c + d \le \frac n 2 \\
a + b \le \frac n 2
\]

充分性可以考虑先吧序列的 C 都消掉，剩只需考虑 A 和 B 。

由于

\(a + c = b + d = \frac n 2\)

所以

\(a + d = b + c = \frac n 2\)

这样就必然可以找到一对 AA 或 BB 消去。

Thus，\(Ans = 3 ^ n - count(a + b > \frac n 2) - count(c + d > \frac n 2)\) 。

枚举有多少个 a + b (c + d) ，其余的位置就只有两种方案，用组合数算一下即可.

code

#include <cstdio>

#include <cstring>

#include <vector>

#include <iostream>

#include <algorithm>

using namespace std;

#define End exit(0)

#define LL long long

#define mp make_pair

#define SZ(x) ((int) x.size())

#define GO cerr << "GO" << endl

#define DE(x) cout << #x << " = " << x << endl

#define DEBUG(...) fprintf(stderr, __VA_ARGS__)

void proc_status()

{

	freopen("/proc/self/status","r",stdin);

	string s; while(getline(cin, s)) if (s[2] == 'P') { cerr << s << endl; return; }

}

template<typename T> inline T read()

{

	register T x = 0;

	register char c; register int f(1);

	while (!isdigit(c = getchar())) if (c == '-') f = -1;

	while (x = (x << 1) + (x << 3) + (c ^ 48), isdigit(c = getchar()));

	return x * f;

}

template<typename T> inline bool chkmin(T &a,T b) { return a > b ? a = b, 1 : 0; }

template<typename T> inline bool chkmax(T &a,T b) { return a < b ? a = b, 1 : 0; }

const int maxN = 1e7 + 2;

const int mod = 998244353;

int qpow(int a, int b)

{

    int ans = 1;

    for (; b; b >>= 1, a = 1ll * a * a % mod)

        if (b & 1) ans = 1ll * ans * a % mod;

    return ans;

}

inline void Inc(int &x) { x < 0 ? x += mod : 0; }

int fac[maxN + 2], ifac[maxN + 2], pw2[maxN + 2];

void init(int N = 1e7)

{

    fac[0] = 1;

    for (int i = 1; i <= N; ++i) fac[i] = (LL) fac[i - 1] * i % mod;

    ifac[N] = qpow(fac[N], mod - 2);

    for (int i = N - 1; i >= 0; --i) ifac[i] = (LL) ifac[i + 1] * (i + 1) % mod;

    pw2[0] = 1;

    for (int i = 1; i <= N; ++i) pw2[i] = pw2[i - 1] * 2ll % mod;

}

int C(int n, int m)

{

    if (n < m) return 0;

    return (LL) fac[n] * ifac[m] % mod * ifac[n - m] % mod;

}

int n;

void input() { n = read<int>(); }

void solve()

{

    int ans = qpow(3, n);

    for (int i = n / 2 + 1; i <= n; ++i)

        Inc(ans -= 2ll * C(n, i) * pw2[n - i] % mod);

    printf("%d\n", ans);

}

int main()

{

#ifndef ONLINE_JUDGE

	freopen("xhc.in", "r", stdin);

	freopen("xhc.out", "w", stdout);

#endif

    input(), init(), solve();

    return 0;

}

巴特西

[AGC040C] Neither AB nor BA

Description

Solution

code

最新文章

热门文章