ARC116 D I wanna win the game.

内容

• ARC116のD問題 I wanna win the game をpythonで解説AC (解説というよりは、自分用のメモ)

  問題

• atcoder.jp

• editorial解と　youtube解説の解の二つでといた。

考えたこと

ポイント

実装

youtube liveの解法(桁ごとにDPしてく)

• 多分 O(logM*N**2)
• 定数倍改善しないと、TLEした。

# -*- coding: utf-8 -*-
class FactMod():
    '''
    modの値が素数の時のfactと組み合わせを求める
    フェルマーの小定理を用いているため、modが素数以外の時は使えない

    NとかRの値が固定なら、combとか、複数回呼び出すより先に、計算してしまってlistとかで持っておく方が良い。(TLE対策)
    '''

    def __init__(self, n, mod):
        '''
        コンストラクタ
        f:nまでの i!の値を　配列に入れる
        inv_f: (i!)^-1　の値を配列に入れる
        '''
        self.mod = mod
        self.f = [1]*(n+1)
        for i in range(1, n+1):
            self.f[i] = self.f[i-1]*i % mod

        self.inv_f = [pow(self.f[-1], mod-2, mod)]
        for i in range(1, n+1)[::-1]:
            self.inv_f.append(self.inv_f[-1]*i % mod)
        self.inv_f.reverse()

    def fact(self, n):
        '''
        n!の値を返す
        '''
        assert n>=0
        return self.f[n]

    def comb(self, n, r):
        '''
        nCrの値を返す
        '''
        #assert n>=r>=0
        if r==0:
            return 1
        ret = self.f[n] * self.inv_f[n-r]*self.inv_f[r]
        ret %= self.mod
        return ret

    def perm(self, n, r):
        """
        nPrの値を返す
        """
        assert n>=r>=0
        ret = self.f[n] * self.inv_f[n-r]
        ret %= self.mod
        return ret

    def div(self,x,y):
        """
        x/yの値を返す
        このclassにいるべきじゃないな
        """
        return (x*pow(y,self.mod-2,self.mod))%self.mod

    def comb_low_r(self,n,r,MOD):
        """
        nCr=\frac{\Pi_{i=0}^{i=r-1}(n-i)}{\Pi_{i=1}^{i=r}(i)}
            FactMod(N,MOD)のNの値が大きいと、前計算が重くて、動かない。
            nCrのrが小さいという保証があるなら、以下のコードでも、十分早いはず
        """
        ret=1
        for i in range(r):#分子の計算
            ret*=(n-i)
            ret%=MOD
        for i in range(2,r+1):#分母の計算(powでinv(i)を求める。)
            ret*=pow(i,MOD-2,MOD)
            ret%=MOD
        return ret

N,M = map(int,input().split())
MOD=998244353

F = FactMod(N,MOD)

#下から見ていくからreverseしとく
bit_M = bin(M)[2:][::-1]
bit_len_M = len(bit_M)


max_carry=2501
max_carry=N//4*2+10
max_carry=2501+2

#一個前の情報しかいらないから、prevDPとnxDPの二つの一次元配列でいい
DP=[0]*max_carry
DP[0]=1

#毎回F.combを呼び出すとneckになるから、先に
combs=[0]*(N+1)
for i in range(N+1):
    combs[i]=F.comb(N,i)

for i in range(bit_len_M):
    nxDP=[0]*max_carry
    cur_digit=int(bit_M[i])
    for j in range(max_carry):#DPの遷移先
        tmp=0
        for k in range(int(cur_digit),max_carry,2):#DPの遷移元
            cur_sum=(j*2-k+1)//2*2

            if not(0<=cur_sum<=N):
                continue
            tmp+=DP[k]*combs[cur_sum]
            tmp%=MOD
        nxDP[j]=tmp
    DP=nxDP
print(DP[0]%MOD)

editorialの解法(sum(A)の値ごとにDPしてく)

# -*- coding: utf-8 -*-
class FactMod():
    '''
    modの値が素数の時のfactと組み合わせを求める
    フェルマーの小定理を用いているため、modが素数以外の時は使えない
    '''

    def __init__(self, n, mod):
        '''
        コンストラクタ
        f:nまでの i!の値を　配列に入れる
        inv_f: (i!)^-1　の値を配列に入れる
        '''
        self.mod = mod
        self.f = [1]*(n+1)
        for i in range(1, n+1):
            self.f[i] = self.f[i-1]*i % mod

        self.inv_f = [pow(self.f[-1], mod-2, mod)]
        for i in range(1, n+1)[::-1]:
            self.inv_f.append(self.inv_f[-1]*i % mod)
        self.inv_f.reverse()

    def fact(self, n):
        '''
        n!の値を返す
        '''
        return self.f[n]

    def comb(self, n, r):
        '''
        nCrの値を返す
        '''
        ret = self.f[n] * self.inv_f[n-r]*self.inv_f[r]
        ret %= self.mod
        return ret

    def perm(self, n, r):
        """
        nPrの値を返す
        """
        ret = self.f[n] * self.inv_f[n-r]
        ret %= self.mod
        return ret

    def div(self,x,y):
        """
        x/yの値を返す
        """
        return (x*pow(y,self.mod-2,self.mod))%self.mod



N,M = map(int,input().split())
MOD=998244353
F = FactMod(N,MOD)

#DP[i]: sum(A)=iの時に、条件を満たす配列の数
DP=[0]*(M+1)
DP[0]=1
for i in range(1,M+1):
    if i%2==1:
        continue
    else:
        for j in range(N):
            if 2*j>N or 2*j>i:
                continue
            DP[i] += F.comb(N,2*j)*DP[(i-2*j)//2]
            DP[i]%=MOD
print(DP[-1])

終わりに

• editorial解は　絶対思いつけない気がした。
• 典型化しときたい。