結果

問題 No.2058 Binary String
コンテスト
ユーザー taiga0629kyopro
提出日時 2022-08-16 01:48:03
言語 PyPy3
(7.3.15)
結果
RE  
実行時間 -
コード長 3,373 bytes
コンパイル時間 160 ms
コンパイル使用メモリ 82,304 KB
実行使用メモリ 84,480 KB
最終ジャッジ日時 2024-10-02 13:52:03
合計ジャッジ時間 2,827 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 1 RE * 22
権限があれば一括ダウンロードができます

ソースコード

diff # 






#####################
mod=998244353
def mul(a,b):
    n=len(a)
    m=len(b[0])
    res=[[0]*m for i in range(n)]
    for i in range(n):
        for j in range(m):
            for k in range(len(a[0])):
                res[i][j]+=a[i][k]*b[k][j]
                res[i][j]%=mod
    return res
def add(a,b):
    res=[[0]*len(a[0]) for i in range(len(a))]
    for i in range(len(a)):
        for j in range(len(a[0])):
            res[i][j]=(a[i][j]+b[i][j])%mod
    return res
def mpow(a,n):
    N = len(a)
    if n == 0:
        res = [[0] * N for i in range(N)]
        for i in range(N):
            res[i][i] = 1
        return res
    if n==1:return a
    res=mpow(a,n//2)
    res=mul(res,res)
    if n%2==1:
        res=mul(res,a)
    return res


def det(A):
    a=[]
    for line in A:
        a.append(line[:])

    n=len(a)
    f=1
    for now in range(n):
        ind=-1
        for i in range(now,n):
            a[i][now]%=mod
            if a[i][now]>0:
                ind=i
                break
        if ind==-1:return 0
        a[now],a[ind]=a[ind],a[now]
        if now!=ind:f*=-1
        f=f*a[now][now]%mod
        inv=pow(a[now][now],mod-2,mod)
        for j in range(now,n):
            a[now][j]*=inv
            a[now][j]%=mod
        for i in range(now+1,n):
            x=a[i][now]
            for j in range(now,n):
                a[i][j]-=a[now][j]*x
                a[i][j]%=mod
    for i in range(n):
        f*=a[i][i]
        f%=mod
    return f


def minv(A):
    n=len(A)
    if det(A)==0:return -1
    a=[]
    for i in range(n):
        e=[0]*n
        e[i]=1
        a.append(A[i][:]+e)
    for now in range(n):
        ind = -1
        for i in range(now, n):
            a[i][now] %= mod
            if a[i][now] > 0:
                ind = i
                break
        if ind == -1: return -1
        a[now], a[ind] = a[ind], a[now]
        inv = pow(a[now][now], mod - 2, mod)
        for j in range(now, 2*n):
            a[now][j] *= inv
            a[now][j] %= mod
        for i in range(now + 1, n):
            x = a[i][now]
            for j in range(now, 2*n):
                a[i][j] -= a[now][j] * x
                a[i][j] %= mod
    for now in range(n-1,-1,-1):
        for i in range(now-1,-1,-1):
            x=a[i][now]
            for j in range(2*n):
                a[i][j]-=a[now][j]*x
                a[i][j]%=mod
    res=[]
    for l in a:res.append(l[n:])
    return res


#######################





#############################
#############
cnb_max=10**6
#############

kai=[1]*(cnb_max+1)
rkai=[1]*(cnb_max+1)
for i in range(cnb_max):
    kai[i+1]=kai[i]*(i+1)%mod

rkai[cnb_max]=pow(kai[cnb_max],mod-2,mod)
for i in range(cnb_max):
    rkai[cnb_max-1-i]=rkai[cnb_max-i]*(cnb_max-i)%mod

def cnb(x,y):
    if y>x:
        return 0
    if x<0:return 0
    if y<0:return 0
    return (kai[x]*rkai[y]%mod)*rkai[x-y]%mod


def inv(n):
    return kai[n-1]*rkai[n]%mod

##################################

n,k=map(int,input().split())
n-=1
if not (k<=100 and n>=k):
    print(aaa)
    exit()
M=[[0]*(k+1) for i in range(k+1)]
for i in range(1,k+1):
    M[i][i]=i
    if i>1:M[i][i-1]=1
a=[[0] for i in range(k+1)]
a[1][0]=1
M=mpow(M,k-1)
a=mul(M,a)
ans=0
for i in range(1,k+1):
    ai=a[i][0]
    res=ai*kai[n]*rkai[n-i]%mod
    res*=pow(2,n-i,mod)
    res%=mod
    ans+=res
    ans%=mod
print(ans)
0