結果

問題 No.2058 Binary String
ユーザー taiga0629kyoprotaiga0629kyopro
提出日時 2022-08-16 01:47:18
言語 PyPy3
(7.3.15)
結果
RE  
実行時間 -
コード長 3,391 bytes
コンパイル時間 170 ms
コンパイル使用メモリ 82,284 KB
実行使用メモリ 86,504 KB
最終ジャッジ日時 2024-10-02 13:51:40
合計ジャッジ時間 3,029 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 RE -
testcase_01 RE -
testcase_02 RE -
testcase_03 RE -
testcase_04 RE -
testcase_05 RE -
testcase_06 RE -
testcase_07 RE -
testcase_08 RE -
testcase_09 RE -
testcase_10 RE -
testcase_11 RE -
testcase_12 RE -
testcase_13 RE -
testcase_14 RE -
testcase_15 RE -
testcase_16 RE -
testcase_17 RE -
testcase_18 RE -
testcase_19 RE -
testcase_20 RE -
testcase_21 RE -
testcase_22 RE -
testcase_23 RE -
testcase_24 RE -
testcase_25 RE -
権限があれば一括ダウンロードができます

ソースコード

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)
print(sol1(n+1,k))
0