Problem:


Score : 800 points

Problem Statement

Given is a positive even number N.

Find the number of strings s of length N consisting of A, B, and C that satisfy the following condition:

s can be converted to the empty string by repeating the following operation:

Choose two consecutive characters in s and erase them. However, choosing AB or BA is not allowed.

For example, ABBC satisfies the condition for N=4, because we can convert it as follows: ABBC → (erase BB) → AC → (erase AC) → (empty).

The answer can be enormous, so compute the count modulo 998244353.

Constraints

2 \leq N \leq 10^7

N is an even number.

Input

Input is given from Standard Input in the following format:

N

Output

Print the number of strings that satisfy the conditions, modulo 998244353.

Sample Input 1

2

Sample Output 1

7

Except AB and BA, all possible strings satisfy the conditions.

Sample Input 2

10

Sample Output 2

50007

Sample Input 3

1000000

Sample Output 3

210055358



Sample input:
2


Sample output:
7

Submission status: Accepted

Solution code:
N = int(input())
MOD = 998244353

list_size = 10000010

f_list = [1] * list_size
f_r_list = [1] * list_size

for i in range(list_size - 1):
	f_list[i + 1] = int((f_list[i] * (i + 2)) % MOD)

f_r_list[-1] = pow(f_list[-1], MOD - 2, MOD)

for i in range(2, list_size + 1):
	f_r_list[-i] = int((f_r_list[-i + 1] * (list_size + 2 - i)) % MOD)


def conv(n,r):
    if r == 0:
        return 1
    return (((f_list[n - 1] * f_r_list[n - r - 1]) % MOD) * f_r_list[r - 1]) % MOD 

ans = 0
for i in range((N//2)):
    ans += conv(N,i) * pow(2,i,MOD)
    ans %= MOD

print((pow(3,N,MOD)-ans*2)%MOD)

Submission status: Accepted

Solution code:
MOD = 998244353
list_size = 10000010

f_list = [1] * list_size
f_r_list = [1] * list_size

for i in range(list_size - 1):
	f_list[i + 1] = int((f_list[i] * (i + 2)) % MOD)

f_r_list[-1] = pow(f_list[-1], MOD - 2, MOD)

for i in range(2, list_size + 1):
	f_r_list[-i] = int((f_r_list[-i + 1] * (list_size + 2 - i)) % MOD)

def comb(n, r):
	if n < r:
		return 0
	elif n == 0 or r == 0 or n == r:
		return 1
	else:
		return (((f_list[n - 1] * f_r_list[n - r - 1]) % MOD) * f_r_list[r - 1]) % MOD 

n = int(input())
sub = 0
for i in range(n//2+1, n+1):
	sub += comb(n, i) * pow(2, n-i, MOD)
	sub %= MOD
print((pow(3, n, MOD) - 2 * sub) % MOD)

Submission status: Accepted

Solution code:
#C
def main():
    mod=998244353
    n=int(input())
    Fact=[1] #階乗
    for i in range(1,n+1):
        Fact.append(Fact[i-1]*i%mod)
    Finv=[0]*(n+1) #階乗の逆元
    Finv[-1]=pow(Fact[-1],mod-2,mod)
    for i in range(n-1,-1,-1):
        Finv[i]=Finv[i+1]*(i+1)%mod
    def comb(n,r):
        if n<r:
            return 0
        return Fact[n]*Finv[r]*Finv[n-r]%mod
    
    impossible=0
    m=1
    for k in range(n//2):
        impossible+=comb(n,k)*m%mod
        impossible%=mod
        m*=2
        m%=mod
    print((pow(3,n,mod)-impossible*2)%mod)

if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
def prepare(n, MOD):
    f = 1
    for m in range(1, n + 1):
        f *= m
        f %= MOD
    fn = f

    inv = pow(f, MOD - 2, MOD)
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv *= m
        inv %= MOD
        invs[m - 1] = inv

    return fn, invs


n = int(input())
MOD = 998244353
fn, invs = prepare(n, MOD)
ans = pow(3, n, MOD)
impossible = 0
mul = 2
for i in range(n // 2):
    tmp = fn * invs[i] * invs[n - i] % MOD * mul
    impossible = (impossible + tmp) % MOD
    mul = mul * 2 % MOD
print((ans - impossible) % MOD)

Submission status: Runtime Error

Solution code:
#include <iostream>
#include <vector>
#include <array>
#include <list>
#include <queue>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <string>
#include <sstream>
#include <algorithm>
#include <random>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <cmath>
#include <cassert>
#include <climits>
#include <bitset>
#include <functional>
#include <iomanip>

#define FOR_LT(i, beg, end) for (int i = beg; i < end; i++)
#define FOR_LE(i, beg, end) for (int i = beg; i <= end; i++)
#define FOR_DW(i, beg, end) for (int i = beg; end <= i; i--)

using namespace std;

static const int64_t kRem = 998244353;

int64_t pow_rem(int64_t x, int64_t m, int64_t rem)
{
	if (m == 0) {
		return 1;
	}
	if (m == 1) {
		return x;
	}

	if (m & 1) {
		int64_t val = pow_rem(x, m / 2, rem);
		val = val * val;
		val %= rem;
		val *= x;
		val %= rem;
		return val;
	}
	else {
		int64_t val = pow_rem(x, m / 2, rem);
		val = val * val;
		val %= rem;
		return val;
	}
}

int64_t pow_remdiv(int64_t val, int64_t rem)
{
	return pow_rem(val, rem - 2, rem);
}

int64_t divide_rem(int64_t divident, int64_t dividor, int64_t rem)
{
	int64_t ret = pow_remdiv(dividor, rem);
	ret *= divident;
	ret %= rem;

	return ret;
}

int64_t nCr(int64_t n, int64_t r, int64_t rem) {
	if (n == 0) return 0;
	if (r > n) return 0;

	if (n - r < r) r = n - r;

	int64_t ret = 1;
	for (int64_t i = 0; i < r; i++) {
		ret *= (n - i);
		ret %= kRem;
		ret = divide_rem(ret, i + 1, rem);
	}

	return ret;
}

vector<int64_t> ncr_arr;
void calc_nCr(int n, int64_t rem) {
	ncr_arr = vector<int64_t>(n + 1);
	int64_t num = 1;
	int64_t denom = 1;

	FOR_LE(i, 0, n) {
		ncr_arr[i] = divide_rem(num, denom, rem);

		num *= (n - i);
		num %= kRem;
		denom *= (i + 1);
		denom %= kRem;
	}
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	int64_t n; cin >> n;

	calc_nCr(n, kRem);

	int64_t ans = 0;
	FOR_LE(k, n / 2 + 1, n) {
		int64_t val = ncr_arr[k];
		val *= pow_rem(2, n - k, kRem);
		val %= kRem;
		ans += val;
		ans %= kRem;
	}

	ans *= 2;
	ans %= kRem;

	ans = pow_rem(3, n, kRem) - ans;
	if (ans < 0) ans += kRem;

	cout << ans << endl;

	return 0;
}

Submission status: Runtime Error

Solution code:
#include <iostream>
#include <vector>
#include <array>
#include <list>
#include <queue>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <string>
#include <sstream>
#include <algorithm>
#include <random>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <cmath>
#include <cassert>
#include <climits>
#include <bitset>
#include <functional>
#include <iomanip>

#define FOR_LT(i, beg, end) for (int i = beg; i < end; i++)
#define FOR_LE(i, beg, end) for (int i = beg; i <= end; i++)
#define FOR_DW(i, beg, end) for (int i = beg; end <= i; i--)
#define int int64_t

using namespace std;

static const int64_t kRem = 998244353;

int64_t pow_rem(int64_t x, int64_t m, int64_t rem)
{
	if (m == 0) {
		return 1;
	}
	if (m == 1) {
		return x;
	}

	if (m & 1) {
		int64_t val = pow_rem(x, m / 2, rem);
		val = val * val;
		val %= rem;
		val *= x;
		val %= rem;
		return val;
	}
	else {
		int64_t val = pow_rem(x, m / 2, rem);
		val = val * val;
		val %= rem;
		return val;
	}
}

int64_t pow_remdiv(int64_t val, int64_t rem)
{
	return pow_rem(val, rem - 2, rem);
}

int64_t divide_rem(int64_t divident, int64_t dividor, int64_t rem)
{
	int64_t ret = pow_remdiv(dividor, rem);
	ret *= divident;
	ret %= rem;

	return ret;
}

int64_t nCr(int64_t n, int64_t r, int64_t rem) {
	if (n == 0) return 0;
	if (r > n) return 0;

	if (n - r < r) r = n - r;

	int64_t ret = 1;
	for (int64_t i = 0; i < r; i++) {
		ret *= (n - i);
		ret %= kRem;
		ret = divide_rem(ret, i + 1, rem);
	}

	return ret;
}

vector<int64_t> ncr_arr;
void calc_nCr(int n, int64_t rem) {
	ncr_arr = vector<int64_t>(n + 1);
	int64_t num = 1;
	int64_t denom = 1;

	FOR_LE(i, 0, n) {
		ncr_arr[i] = divide_rem(num, denom, rem);

		num *= (n - i);
		num %= kRem;
		denom *= (i + 1);
		denom %= kRem;
	}
}

#undef int
int main()
{
#define int int64_t
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	int64_t n; cin >> n;

	calc_nCr(n, kRem);

	int64_t ans = 0;
	FOR_LE(k, n / 2 + 1, n) {
		int64_t val = ncr_arr[k];
		val *= pow_rem(2, n - k, kRem);
		val %= kRem;
		ans += val;
		ans %= kRem;
	}

	ans *= 2;
	ans %= kRem;

	ans = pow_rem(3, n, kRem) - ans;
	if (ans < 0) ans += kRem;

	cout << ans << endl;

	return 0;
}

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**8)
input = sys.stdin.readline

MOD = 998244353
MAX_N = 10**6 

fac = [1] + [0] * MAX_N
fac_inv = [1] + [0] * MAX_N
mod_pow2_n = [1] + [0] * MAX_N
f = 1
finv = 1
p2 = 1
for i in range(1, MAX_N+1):
    # fac[i] = fac[i-1] * i % MOD
    f *= i
    f %= MOD
    fac[i] = f
    # Fermat's little theorem says
    # a**(p-1) mod p == 1
    # then, a * a**(p-2) mod p == 1
    # it means a**(p-2) is inverse element
    # fac_inv[i] = fac_inv[i-1] * pow(i, MOD-2, MOD) % MOD
    finv *= pow(i, MOD-2, MOD)
    finv %= MOD
    fac_inv[i] = finv
    p2 *= 2
    p2 %= MOD
    mod_pow2_n[i] = p2

def mod_nCr(n, r):
    if n < r or n < 0 or r < 0:
        return 0
    tmp = fac_inv[n-r] * fac_inv[r] % MOD
    return tmp * fac[n] % MOD 
    
def single_mod_nCr(n, r):
    if n < r or n < 0 or r < 0:
        return 0
    if r > n - r:
        r = n - r
    ret = 1
    for i in range(r):
        ret *= n - i
        ret *= pow(i+1, MOD-2, MOD)
        ret %= MOD
    return ret

n = int(input())
ans = 0
for i in range(n//2+1, n+1):
    ans += mod_nCr(n, i) * mod_pow2_n[n-i]
    ans %= MOD
print((pow(3, n, MOD) - ans * 2 + MOD)%MOD)