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: Wrong Answer

Solution code:
n=int(input());l=[0,1];a=0;b=c=1;p=998244353
for i in range(2,n):l+=[l[p%i]*(p-int(p/i))%p]
for i in range(n,n//2,-1):a+=b*c%p;b+=b%p;c=c*i*l[n+1-i]%p
print(pow(3,n,p)-2*a%p)

Submission status: Wrong Answer

Solution code:
n=int(input());l=[0,1];a=0;b=c=1;p=998244353
for i in range(2,n):
 l+=[l[p%i]*(p-int(p/i))%p]
for i in range(n,n//2,-1):
 a+=b*c%p;b+=b%p;c=c*i*l[n+1-i]%p
print(pow(3,n,p)-2*a%p)

Submission status: Wrong Answer

Solution code:
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
    for k in range(n//2+1,n+1):
        impossible+=comb(n,k)*pow(2,n-k,mod)
        impossible%=mod
    print(pow(3,n,mod)-impossible*2)

if __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
mod=998244353

ans=pow(3,n,mod)
rmv=0
f = [1, 1]  
inv = [1, 1]  
finv=[1,1]
for i in range(2, n+1):
    f.append((f[-1] * i) % mod)
    inv.append((-inv[mod % i] * (mod // i)) % mod)
    finv.append(finv[-1]*inv[-1]%mod)

k=n//2
if k*2<=n:
    k+=1
tmp=pow(2,n-k+1,mod)
inv2=pow(2,mod-2,mod)
for i in range(k,n+1):
    ans -= f[n]*finv[n-i]*finv[i]*tmp
    tmp*=inv2
    tmp%=mod
print(ans%mod)

Submission status: Time Limit Exceeded

Solution code:
#解説参照
#言い換えが困難

n=int(input())
mod=998244353

ans=pow(3,n,mod)
rmv=0
f = [1, 1]  
inv = [1, 1]  
finv=[1,1]
for i in range(2, n+1):
    f.append((f[-1] * i) % mod)
    inv.append((-inv[mod % i] * (mod // i)) % mod)
    finv.append(finv[-1]*inv[-1]%mod)

def ch(a,b):
    return f[a]*finv[a-b]*finv[b]
k=n//2
if k*2<=n:
    k+=1

for i in range(k,n+1):
    ans -= ch(n,i)*pow(2,n-i+1,mod)
print(ans%mod)

Submission status: Time Limit Exceeded

Solution code:
LARGE = 998244353


def solve(n):
    r = 0
    mck = 1
    factorial_n = 1
    factorial_inv = [0] * (n + 1)
    factorial_inv[0] = 1
    for i in range(1, n + 1):
        factorial_n *= i
        factorial_n %= LARGE
    factorial_inv[-1] = pow(factorial_n, LARGE - 2, LARGE)
    for i in range(n):
        factorial_inv[n - i - 1] = (factorial_inv[n - i] * (n - i)) % LARGE
    pow_2 = 1
    for k in range(n // 2):
        r += factorial_n * factorial_inv[n - k] * factorial_inv[k] * pow_2
        r %= LARGE
        pow_2 *= 2
        pow_2 %= LARGE
    res = (pow(3, n, LARGE) - (2 * r)) % LARGE
    return res


def main():
    n = int(input())
    res = solve(n)
    print(res)


def test():
    assert solve(2) == 7
    assert solve(10) == 50007
    # assert solve(1000000) == 210055358


if __name__ == "__main__":
    test()
    main()

Submission status: Time Limit Exceeded

Solution code:
LARGE = 998244353


def solve(n):
    r = 0
    mck = 1
    for k in range(n // 2):
        r += mck * pow(2, k, LARGE)
        r %= LARGE
        mck *= n - k
        mck %= LARGE
        mck *= pow(k + 1, LARGE - 2, LARGE)
        mck %= LARGE
    res = (pow(3, n, LARGE) - (2 * r)) % LARGE
    return res


def main():
    n = int(input())
    res = solve(n)
    print(res)


def test():
    assert solve(2) == 7
    assert solve(10) == 50007
    # assert solve(1000000) == 210055358


if __name__ == "__main__":
    test()
    main()

Submission status: Time Limit Exceeded

Solution code:
LARGE = 998244353


def solve(n):
    r = 0
    mck = 1
    for k in range(n // 2):
        r += mck * pow(2, k, LARGE)
        r %= LARGE
        mck *= n - k
        mck *= pow(k + 1, LARGE - 2, LARGE)
        mck %= LARGE
    res = (pow(3, n, LARGE) - (2 * r)) % LARGE
    return res


def main():
    n = int(input())
    res = solve(n)
    print(res)


def test():
    assert solve(2) == 7
    assert solve(10) == 50007
    # assert solve(1000000) == 210055358


if __name__ == "__main__":
    test()
    main()

Submission status: Time Limit Exceeded

Solution code:
LARGE = 998244353


def solve(n):
    r = 0
    mck = 1
    for k in range(n // 2):
        r += mck * pow(2, k, LARGE)
        r %= LARGE
        mck *= n - k
        mck *= pow(k + 1, LARGE - 2, LARGE)
    res = (pow(3, n, LARGE) - (2 * r)) % LARGE
    return res


def main():
    n = int(input())
    res = solve(n)
    print(res)


def test():
    assert solve(2) == 7
    assert solve(10) == 50007
    # assert solve(1000000) == 210055358


if __name__ == "__main__":
    test()
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np


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

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

    return fn, invs


n = int(input())
MOD = 998244353
fn, invs = prepare(n, MOD)

n2 = n // 2

# mul = 1
# muls = [0] * n2
# for i in range(n2):
#     mul = muls[i] = mul * 2 % MOD

# mul = 1
# muls = np.zeros(n2, dtype=np.int64)
# for i in range(n2):
#     mul = muls[i] = mul * 2 % MOD

muls = np.zeros(1, dtype=np.int64)
muls[0] = 2
while muls.size < n2:
    muls = np.append(muls, muls * muls[-1] % MOD)
muls = muls[:n2]

impossibles = invs[:n2] * invs[n:n2:-1] % MOD
impossibles = impossibles * muls % MOD
impossible = sum(list(impossibles)) % MOD * fn

print((pow(3, n, MOD) - impossible) % MOD)

Submission status: Time Limit Exceeded

Solution code:
import itertools
import os
import sys
from functools import lru_cache

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 998244353

N = int(sys.stdin.readline())


@lru_cache(maxsize=None)
# @debug
def is_ok(s):
    if len(s) == 0:
        return True
    if len(s) == 2:
        return s not in ['AB', 'BA']
    for i in range(len(s) - 2):
        if s[i:i + 2] not in ['AB', 'BA'] and is_ok(s[:i] + s[i + 2:]):
            return True
    return False


def test(N):
    ret = 0
    for s in itertools.product('ABC', repeat=N):
        s = ''.join(s)
        ret += is_ok(s)
    return ret


def mod_invs(max, mod):
    """
    逆元のリスト 0 から max まで
    :param int max:
    :param int mod:
    """
    invs = [1] * (max + 1)
    for x in range(2, max + 1):
        invs[x] = (-(mod // x) * invs[mod % x]) % mod
    return invs


# print(test(N))
# N = 10 ** 7

# 解説AC
# 偶数番目のAとBを反転して、AAとBB以外を取り除く
# AまたはBが半分より多いときダメなので全体から引く
ans = pow(3, N, MOD)

invs = mod_invs(max=N, mod=MOD)
ncr = 1  # NCr
p2r = 1  # pow(2, N - r, MOD)
for r in range(N, N // 2, -1):
    # ans -= comb.ncr(N, r) * pow(2, N - r, MOD) * 2 % MOD
    ans -= ncr * p2r * 2 % MOD
    ans %= MOD
    ncr *= r * invs[N - r + 1]
    ncr %= MOD
    p2r *= 2
    p2r %= MOD
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools
import os
import sys
from functools import lru_cache

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 998244353

N = int(sys.stdin.readline())


@lru_cache(maxsize=None)
# @debug
def is_ok(s):
    if len(s) == 0:
        return True
    if len(s) == 2:
        return s not in ['AB', 'BA']
    for i in range(len(s) - 2):
        if s[i:i + 2] not in ['AB', 'BA'] and is_ok(s[:i] + s[i + 2:]):
            return True
    return False


def test(N):
    ret = 0
    for s in itertools.product('ABC', repeat=N):
        s = ''.join(s)
        ret += is_ok(s)
    return ret


def get_factorials(max, mod=None):
    """
    階乗 0!, 1!, 2!, ..., max!
    :param int max:
    :param int mod:
    :return:
    """
    ret = [1]
    n = 1
    if mod:
        for i in range(1, max + 1):
            n *= i
            n %= mod
            ret.append(n)
    else:
        for i in range(1, max + 1):
            n *= i
            ret.append(n)
    return ret


def mod_invs(max, mod):
    """
    逆元のリスト 0 から max まで
    :param int max:
    :param int mod:
    """
    invs = [1] * (max + 1)
    for x in range(2, max + 1):
        invs[x] = (-(mod // x) * invs[mod % x]) % mod
    return invs


def factorial_invs(max, mod):
    """
    階乗 0!, 1!, 2!, ..., max! の逆元
    :param int max:
    :param int mod:
    """
    ret = []
    r = 1
    for inv in mod_invs(max, mod):
        r = r * inv % mod
        ret.append(r)
    return ret


class Combination:
    def __init__(self, max, mod):
        """
        :param int max:
        :param int mod: 3 以上の素数であること
        """
        self._factorials = get_factorials(max, mod)
        self._finvs = factorial_invs(max, mod)
        self._mod = mod

    def ncr(self, n, r):
        """
        :param int n:
        :param int r:
        :rtype: int
        """
        if n < r:
            return 0
        return self._factorials[n] * self._finvs[r] % self._mod * self._finvs[n - r] % self._mod


# print(test(N))

# 解説AC
# 偶数番目のAとBを反転して、AAとBB以外を取り除く
# AまたはBが半分より多いときダメなので全体から引く
ans = pow(3, N, MOD)
comb = Combination(max=N, mod=MOD)
for r in range(N // 2 + 1, N + 1):
    ans -= comb.ncr(N, r) * pow(2, N - r, MOD) * 2 % MOD
    ans %= MOD
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
mod=998244353
Combi=1
SC=0
for i in range(N,N//2,-1):
    SC=(SC+Combi*pow(2,N-i,mod))%mod
    Combi=Combi*(i)*pow(N-i+1,mod-2,mod)%mod
print((pow(3,N,mod)-SC*2)%mod)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
mod=998244353
Combi=1
for i in range(1,N//2+1):
    Combi=Combi*(N-i+1)*pow(i,mod-2,mod)%mod
SC=0
for i in range(N//2+1,N+1):
    Combi=Combi*(N-i+1)*pow(i,mod-2,mod)%mod
    SC=(SC+Combi*pow(2,N-i,mod))%mod  
print((pow(3,N,mod)-SC*2)%mod)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
mod=998244353
Combi=[1]
for i in range(1,N+1):
    Combi.append(Combi[-1]*(N-i+1)*pow(i,mod-2,mod)%mod)
SC=0
for i in range(N//2+1,N+1):
    SC=(SC+Combi[i]*pow(2,N-i,mod))%mod
print((pow(3,N,mod)-SC*2)%mod)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
mod=998244353
Combi=[1]
for i in range(1,N+1):
    Combi.append(Combi[-1]*(N-i+1)*pow(i,mod-2,mod)%mod)
SC=0
for i in range(N//2+1,N+1):
    SC+=Combi[i]*pow(2,N-i,mod)
print((pow(3,N,mod)-SC*2)%mod)

Submission status: Time Limit Exceeded

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

FACT=[1]
for i in range(1,N+1):
    FACT.append(FACT[-1]*i%mod)

FACT_INV=[pow(FACT[-1],mod-2,mod)]
for i in range(N,0,-1):
    FACT_INV.append(FACT_INV[-1]*i%mod)

FACT_INV.reverse()

def Combi(a,b):
    if 0<=b<=a:
        return FACT[a]*FACT_INV[b]*FACT_INV[a-b]%mod

SC=0
for i in range(N//2+1,N+1):
    SC+=Combi(N,i)*pow(2,N-i,mod)

print((pow(3,N,mod)-SC*2)%mod)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**8)
input = sys.stdin.readline
 
MOD = 998244353
MAX_N = 10**7 
 
fac = [1] + [0] * MAX_N
fac_inv = [1] + [0] * MAX_N
mod_pow2_n = [1] + [0] * MAX_N
for i in range(1, MAX_N+1):
    fac[i] = fac[i-1] * i % MOD
    mod_pow2_n[i] = mod_pow2_n[i-1] * 2 % MOD
 
fac_inv[MAX_N] = pow(fac[MAX_N], MOD-2, MOD)
for i in range(MAX_N, 1, -1):
    fac_inv[i-1] = fac_inv[i] * i % MOD
 
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 
    
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)

Submission status: Time Limit Exceeded

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

MOD = 998244353
MAX_N = 10**7 

fac = [1] + [0] * MAX_N
fac_inv = [1] + [0] * MAX_N
mod_pow2_n = [1] + [0] * MAX_N
for i in range(1, MAX_N+1):
    fac[i] = fac[i-1] * i % MOD
    mod_pow2_n[i] = mod_pow2_n[i-1] * 2 % MOD

fac_inv[MAX_N] = pow(fac[MAX_N], MOD-2, MOD)
for i in range(MAX_N, 1, -1):
    fac_inv[i-1] = fac_inv[i] * i % MOD

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 
    
n = int(input())
ans = 0
for i in range(n//2+1, n+1):
    ans += mod_nCr(n, i) * pow(2, n - i, MOD)
    ans %= MOD
print((pow(3, n, MOD) - ans * 2 + MOD)%MOD)

Submission status: Time Limit Exceeded

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

n = int(input())

MOD = 998244353
MAX_N = n 

fac_inv = [1] + [0] * MAX_N
mod_pow2_n = [1] + [0] * MAX_N
fn = 1
finv = 1
p2 = 1
for i in range(1, MAX_N+1):
    fn *= i
    fn %= MOD

    finv *= pow(i, MOD-2, MOD)
    finv %= MOD
    fac_inv[i] = finv
    p2 *= 2
    p2 %= MOD
    mod_pow2_n[i] = p2

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

Submission status: Time Limit Exceeded

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

n = int(input())

MOD = 998244353
MAX_N = n 

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

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

Submission status: Time Limit Exceeded

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

MOD = 998244353
MAX_N = 10**7 

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

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

Submission status: Time Limit Exceeded

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

MOD = 998244353
MAX_N = 10**7 

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)

Submission status: Time Limit Exceeded

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

MOD = 998244353
MAX_N = 10**7 

fac = [1] + [0] * MAX_N
fac_inv = [1] + [0] * MAX_N
for i in range(1, MAX_N+1):
    fac[i] = fac[i-1] * (i) % MOD
    # 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

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) * pow(2, n - i, MOD)
    ans %= MOD
print((pow(3, n, MOD) - ans * 2 + MOD)%MOD)

Submission status: Time Limit Exceeded

Solution code:

n=int(input())
pre=[1]*(n//2+200)
pp=[1]*(n+1)
mod=998244353
for i in range(1,n//2+100):
    pre[i]=((pre[i-1]*2)%mod)
    
p=[1]*(n+1)
for i in range(n):
    p[i+1]=((p[i]*(i+1))%mod)
    pp[i+1]=pow(p[i+1],mod-2,mod)
tot=1
for i in range(n):
    tot*=3
    tot%=mod
#print(1)
#print(tot)
cc=0
for i in range(n//2+1,n+1):
    c=(((((p[n]*pp[i])%mod)*pp[n-i])%mod)*pre[n-i])%mod
    c%=mod
    cc+=c
tot-=cc
tot-=cc
tot%=mod
print(tot)

Submission status: Time Limit Exceeded

Solution code:
def e(a,b,c):
    if b==0:
        return 1
    aa=1
    if b%2==1:
        aa=a
    return (aa*(e(a,b//2,c)**2))%mod
n=int(input())
pre=[1]
mod=998244353
for i in range(n//2+100):
    pre.append((pre[-1]*2)%mod)
p=[1]
for i in range(n):
    p.append((p[-1]*(i+1))%mod)
tot=1
for i in range(n):
    tot*=3
    tot%=mod
#print(1)
#print(tot)
for i in range(n//2+1,n+1):
    c=(p[n]*e(p[i],mod-2,mod)*e(p[n-i],mod-2,mod)*pre[n-i])%mod
    c%=mod
    tot-=c
    tot-=c
    tot%=mod
print(tot)

Submission status: Time Limit Exceeded

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

ans = 0
d = 1
b = 1
for i in range((N//2)):
    ans += d * b
    b *= 2
    b %= MOD
    ans %= MOD
    d = ((N-i)*d)%MOD
    d = (d*pow(i+1,MOD-2,MOD))%MOD

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

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
MOD = 998244353
def func(x):
    a = [23,26]
    out = 1
    for i in range(30):
        if not i in a:
            out = (out*x)%MOD
        x *= x
        x %= MOD
    return out

def func2(x):
    x = bin(x)[2:]
    out = 1
    b = 3
    for i in range(len(x)):
        if x[-1-i] == "1":
            out *= b
            out %= MOD
        b *= b
        b %= MOD
    return out

ans = 0
d = 1
b = 1
for i in range((N//2)):
    ans += d * b
    b *= 2
    b %= MOD
    ans %= MOD
    d = ((N-i)*d)%MOD
    d = (d*func(i+1))%MOD

print((func2(N)-ans*2)%MOD)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
MOD = 998244353
def func(x):
    a = [23,26]
    out = 1
    for i in range(30):
        if not i in a:
            out = (out*x)%MOD
        x *= x
        x %= MOD
    return out

def func2(x):
    x = bin(x)[2:]
    out = 1
    b = 3
    for i in range(len(x)):
        if x[-1-i] == "1":
            out *= b
            out %= MOD
        b *= b
        b %= MOD
    return out

ans = 0
d = 1
for i in range((N//2)):
    ans += d * 2**i
    ans %= MOD
    d = ((N-i)*d)%MOD
    d = (d*func(i+1))%MOD

print((func2(N)-ans*2)%MOD)

Submission status: Time Limit Exceeded

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
for i in range(n // 2):
    tmp = fn * invs[i] * invs[n - i] % MOD * pow(2, i, MOD)
    impossible = (impossible + 2 * tmp) % MOD
print((ans - impossible) % MOD)

Submission status: Accepted

Solution code:
n=int(input());l=[0,1];a=0;b=c=1;p=998244353
for i in range(2,n):l+=[l[p%i]*(p-p//i)%p]
for i in range(n,n//2,-1):a+=b*c;b+=b%p;c=c*i*l[n+1-i]%p
print((pow(3,n,p)-2*a)%p)

Submission status: Accepted

Solution code:
n=int(input());l=[0,1];a=0;b=c=1;p=998244353
for i in range(2,n):l+=[l[p%i]*(p-p//i)%p]
for i in range(n,n//2,-1):a+=b*c%p;b+=b%p;c=c*i*l[n+1-i]%p
print((pow(3,n,p)-2*a)%p)

Submission status: Accepted

Solution code:
n=int(input());l=[0,1];a=0;b=c=1;p=998244353
for i in range(2,n):l+=[l[p%i]*(p-int(p/i))%p]
for i in range(n,n//2,-1):a+=b*c%p;b+=b%p;c=c*i*l[n+1-i]%p
print((pow(3,n,p)-2*a)%p)

Submission status: Accepted

Solution code:
n=int(input());l=[0,1];a=0;b=c=1;p=998244353
for i in range(2,n):
 l+=[l[p%i]*(p-int(p/i))%p]
for i in range(n,n//2,-1):
 a+=b*c%p;b+=b%p;c=c*i*l[n+1-i]%p
print((pow(3,n,p)-2*a)%p)

Submission status: Accepted

Solution code:
N = int(input())

nn = N + 10
P = 998244353

fa = [1] * (nn+1)
fainv = [1] * (nn+1)
for i in range(nn):
    fa[i+1] = fa[i] * (i+1) % P
fainv[-1] = pow(fa[-1], P-2, P)
for i in range(nn)[::-1]:
    fainv[i] = fainv[i+1] * (i+1) % P
C = lambda a, b: fa[a] * fainv[b] % P * fainv[a-b] % P if 0 <= b <= a else 0

ans = pow(3, N, P)
p2 = 2
for i in range(N, N // 2, -1):
    ans = (ans - C(N, i) * p2) % P
    p2 = p2 * 2 % P

print(ans)

Submission status: Accepted

Solution code:
N = int(input())

nn = N + 10
P = 998244353

fa = [1] * (nn+1)
fainv = [1] * (nn+1)
for i in range(nn):
    fa[i+1] = fa[i] * (i+1) % P
fainv[-1] = pow(fa[-1], P-2, P)
for i in range(nn)[::-1]:
    fainv[i] = fainv[i+1] * (i+1) % P
C = lambda a, b: fa[a] * fainv[b] % P * fainv[a-b] % P if 0 <= b <= a else 0

ans = pow(3, N, P)
for i in range(N//2 + 1, N + 1):
    ans = (ans - 2 * C(N, i) * pow(2, N - i, P)) % P

print(ans)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

MOD = 998244353

N = int(read())

import numpy as np

def cumprod(arr,MOD):
    L = len(arr); Lsq = int(L**.5+1)
    arr = np.resize(arr,Lsq**2).reshape(Lsq,Lsq)
    for n in range(1,Lsq):
        arr[:,n] *= arr[:,n-1]; arr[:,n] %= MOD
    for n in range(1,Lsq):
        arr[n] *= arr[n-1,-1]; arr[n] %= MOD
    return arr.ravel()[:L]

def make_fact(U,MOD):
    x = np.arange(U,dtype=np.int64); x[0] = 1
    fact = cumprod(x,MOD)
    x = np.arange(U,0,-1,dtype=np.int64); x[0] = pow(int(fact[-1]),MOD-2,MOD)
    fact_inv = cumprod(x,MOD)[::-1]
    return fact,fact_inv

U = 10**7 + 10
fact, fact_inv = make_fact(U,MOD)

x = np.full(U,2,dtype=np.int64); x[0] = 1
pow2 = cumprod(x,MOD)

n = N//2
comb = fact_inv[:n] * fact_inv[N:N-n:-1] % MOD * fact[N] % MOD

x = (comb * pow2[:n] % MOD).sum()
answer = pow(3,N,MOD) - x - x
answer %= MOD
print(answer)

Submission status: Accepted

Solution code:
n=int(input());l=[0,1];a=0;b=c=1;p=998244353
for i in range(2,n):
 l+=[l[p%i]*(p-int(p/i))%p]
for i in range(n,n//2,-1):
 a+=b*c%p;b=2*b%p;c=c*i*l[n+1-i]%p
print((pow(3,n,p)-2*a)%p)

Submission status: Accepted

Solution code:
n=int(input());l=[0,1];a=0;b=c=1;p=998244353
for i in range(2,n):
 l+=[l[p%i]*(p-int(p/i))%p]
for i in range(n,n//2,-1):
 a+=b*c%p;b=2*b%p;c=c*i*l[n+1-i]%p
print((pow(3,n,p)-2*a+p)%p)

Submission status: Accepted

Solution code:
n=int(input());l=[0,1];a=0;b=c=1;p=998244353
for i in range(2,n//2+1):
 l+=[l[p%i]*(p-int(p/i))%p]
for i in range(n,n//2,-1):
 a+=b*c%p;b=2*b%p;c=c*i*l[n+1-i]%p
print((pow(3,n,p)-2*a+p)%p)

Submission status: Accepted

Solution code:
def cmb(n,r,mod):
  if r<0 or r>n:
    return 0
  r=min(r,n-r)
  return g1[n]*g2[r]*g2[n-r]%mod
 
n=int(input())
mod=998244353

g1=[1,1]
g2=[1,1]
inverse=[0,1]
 
for i in range(2,n+1):
  g1.append((g1[-1]*i)%mod)
  inverse.append((-inverse[mod%i]*(mod//i))%mod)
  g2.append((g2[-1]*inverse[-1])%mod)

a=0
b=1
for i in range(n,n//2,-1):
  a+=cmb(n,i,mod)*b
  a%=mod
  b*=2
  b%=mod
ans=(pow(3,n,mod)-2*a)%mod
print((ans+mod)%mod)

Submission status: Accepted

Solution code:
def calc(n, mod):
	f = 1
	fac = [1]
	for i in range(1, n + 1):
		f *= i
		f %= mod
		fac.append(f)
	inv = pow(f, mod - 2, mod)
	invs = [1] * (n + 1)
	invs[n] = inv
	for i in range(n, 1, -1):
		inv *= i
		inv %= mod
		invs[i - 1] = inv
	return fac, invs

def cnk(n, r, mod, fac, inv):
	return fac[n] * inv[n - r] * inv[r] % mod


n = int(input())

mod = 998244353

f, inv = calc(n + 10, mod)
ans = pow(3, n, mod)
p = [1]

for i in range(n // 2 + 10):
	p.append(p[-1] * 2 % mod)
for k in range(n // 2 + 1, n + 1):
	cur = 2 * cnk(n, k, mod, f, inv) * p[n - k]
	ans -= cur
	ans %= mod
print(ans)

Submission status: Accepted

Solution code:

"""
Writer: SPD_9X2
https://atcoder.jp/contests/agc040/tasks/agc040_c

奇数文字目と偶数文字目がセットで消える
奇数文字目のABを反転すると、AB or BA or AC or BC or CC で消えていいことになる

すなわち、異なる文字の切れ目では必ず消せる
異なる切れ目は必ず存在するので、Cを適当にABに割り振った時に全て消せるかどうかが問題になる

A,Bのみの時に全て消せる条件は 両者の数が等しい事
Cを適切に割り振った時に両者の数を等しくできる必要十分条件は max(a,b) <= N//2
あとはこれを数えればよい→どうやって？

全ての並び方は 3**N　ここから補集合を引く？
Aが半数を超える(k個)の時のおき方は、 NCk * (2**(N-k))で求まる
Bの時も同様に。

"""

def modfac(n, MOD):
 
    f = 1
    factorials = [1]
    for m in range(1, n + 1):
        f *= m
        f %= MOD
        factorials.append(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 factorials, invs


def modnCr(n,r,mod,fac,inv):
    return fac[n] * inv[n-r] * inv[r] % mod


N = int(input())
mod = 998244353

fac,inv = modfac(N+10,mod)
ans = pow(3,N,mod)

tpow = [1]
for i in range(N//2+10):
    tpow.append(tpow[-1]*2%mod)

for k in range(N//2+1,N+1):

    now = 2 * modnCr(N,k,mod,fac,inv) * tpow[N-k]
    ans -= now
    ans %= mod

print (ans)

Submission status: Accepted

Solution code:
def xgcd(a, b):
    x0, y0, x1, y1 = 1, 0, 0, 1
    while b != 0:
        q, a, b = a // b, b, a % b
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return a, x0, y0

def modinv(a, m):
    g, x, y = xgcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m

MOD = 998244353
N = int(input())
#N = 10 ** 7
n = N // 2
ansx = 1
tmp2 = 1
tmpc = 1
for i in range(1, n):
    tmp2 = (tmp2 * 2)%MOD
    tmpc = (tmpc * (2 * n - i + 1) * modinv(i, MOD)) % MOD
    ansx = (ansx + tmp2 * tmpc)%MOD

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

Submission status: Accepted

Solution code:
MOD = 998244353

N = int(input())

ans = pow(3, N, MOD)

def getInvs(n, MOD):
    invs = [1] * (n+1)
    for x in range(2, n+1):
        invs[x] = (-(MOD//x) * invs[MOD%x]) % MOD
    return invs

def getCombNs(n, invs, MOD):
    combNs = [1] * (n//2+1)
    for x in range(1, n//2+1):
        combNs[x] = (combNs[x-1] * (n-x+1) * invs[x]) % MOD
    return combNs + combNs[:(n+1)//2][::-1]

invs = getInvs(N, MOD)
combNs = getCombNs(N, invs, MOD)

pow2 = 1
for i in range((N-1)//2+1):
    num = combNs[i] * pow2
    ans -= num*2 % MOD
    ans %= MOD
    pow2 *= 2
    pow2 %= MOD

print(ans)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

MOD = 998244353

N = int(read())

import numpy as np

def cumprod(arr,MOD):
    L = len(arr); Lsq = int(L**.5+1)
    arr = np.resize(arr,Lsq**2).reshape(Lsq,Lsq)
    for n in range(1,Lsq):
        arr[:,n] *= arr[:,n-1]; arr[:,n] %= MOD
    for n in range(1,Lsq):
        arr[n] *= arr[n-1,-1]; arr[n] %= MOD
    return arr.ravel()[:L]

def make_fact(U,MOD):
    x = np.arange(U,dtype=np.int64); x[0] = 1
    fact = cumprod(x,MOD)
    x = np.arange(U,0,-1,dtype=np.int64); x[0] = pow(int(fact[-1]),MOD-2,MOD)
    fact_inv = cumprod(x,MOD)[::-1]
    return fact,fact_inv

U = 10**7 + 10
fact, fact_inv = make_fact(U,MOD)

x = np.full(U,2,dtype=np.int64); x[0] = 1
pow2 = cumprod(x,MOD)

n = N//2
comb = fact_inv[:n] * fact_inv[N:N-n:-1] % MOD * fact[N] % MOD

x = (comb * pow2[:n] % MOD).sum()
answer = pow(3,N,MOD) - x - x
answer %= MOD
print(answer)

Submission status: Accepted

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

FACT=[1]
for i in range(1,N+1):
    FACT.append(FACT[-1]*i%mod)

FACT_INV=[pow(FACT[-1],mod-2,mod)]
for i in range(N,0,-1):
    FACT_INV.append(FACT_INV[-1]*i%mod)

FACT_INV.reverse()

POW=[1]
for i in range(N):
    POW.append(POW[-1]*2%mod)

def Combi(a,b):
    return FACT[a]*FACT_INV[b]*FACT_INV[a-b]%mod

SC=0
for i in range(N//2+1,N+1):
    SC+=Combi(N,i)*POW[N-i]

print((pow(3,N,mod)-SC*2)%mod)

Submission status: Accepted

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

MOD = 998244353
MAX_N = 10**7 

fac = [1] + [0] * MAX_N
fac_inv = [1] + [0] * MAX_N
mod_pow2_n = [1] + [0] * MAX_N
for i in range(1, MAX_N+1):
    fac[i] = fac[i-1] * i % MOD
    mod_pow2_n[i] = mod_pow2_n[i-1] * 2 % MOD

fac_inv[MAX_N] = pow(fac[MAX_N], MOD-2, MOD)
for i in range(MAX_N, 1, -1):
    fac_inv[i-1] = fac_inv[i] * i % MOD

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 
    
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)

Submission status: Accepted

Solution code:

n=int(input())
pre=[1]*(n//2+200)
pp=[1]*(n+1)
mod=998244353
for i in range(1,n//2+100):
    pre[i]=((pre[i-1]*2)%mod)
    
p=[1]*(n+1)
for i in range(n):
    p[i+1]=((p[i]*(i+1))%mod)
pp[-1] = pow(p[-1], mod - 2, mod)
 
for i in range(2, n + 1):
	pp[-i] = int((pp[-i + 1] * (n + 2 - i)) % mod)
tot=1
for i in range(n):
    tot*=3
    tot%=mod
#print(1)
#print(tot)
cc=0
for i in range(n//2+1,n+1):
    c=(((((p[n]*pp[i])%mod)*pp[n-i])%mod)*pre[n-i])%mod
    c%=mod
    cc+=c
tot-=cc
tot-=cc
tot%=mod
print(tot)

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 comb(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 += comb(N,i) * pow(2,i,MOD)
    ans %= MOD

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