結果

問題 No.2966 Simple Plus Minus Problem
コンテスト
ユーザー lif4635
提出日時 2024-11-16 17:25:53
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,796 bytes
コンパイル時間 596 ms
コンパイル使用メモリ 82,008 KB
実行使用メモリ 113,444 KB
最終ジャッジ日時 2024-11-16 17:27:14
合計ジャッジ時間 7,970 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 6 WA * 48
権限があれば一括ダウンロードができます

ソースコード

diff # 

"""input"""
#int-input
# input = sys.stdin.readline
def II(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(MI())
#str-input
def SI(): return input()
def MSI(): return input().split()
def SI_L(): return list(SI())
def SI_LI(): return list(map(int, SI()))
#multiple-input
def LLI(n): return [LI() for _ in range(n)]
def LSI(n): return [SI() for _ in range(n)]
#1-indexを0-indexでinput
def MI_1(): return map(lambda x:int(x)-1, input().split())
def TI_1(): return tuple(MI_1())
def LI_1(): return list(MI_1())

from collections import deque,defaultdict,Counter
mod = 998244353

class fenwick_tree():
    n=1
    data=[0 for i in range(n)]
    def __init__(self,N):
        self.n=N
        self.data=[0 for i in range(N)]
    def add(self,p,x):
        assert 0<=p<self.n,"0<=p<n,p={0},n={1}".format(p,self.n)
        p+=1
        while(p<=self.n):
            self.data[p-1]+=x
            p+=p& -p
    def sum(self,l,r):
        assert (0<=l and l<=r and r<=self.n),"0<=l<=r<=n,l={0},r={1},n={2}".format(l,r,self.n)
        return self.sum0(r)-self.sum0(l)
    def sum0(self,r):
        s=0
        while(r>0):
            s+=self.data[r-1]
            r-=r&-r
        return s

#必ず入っている集合を見つける
#必ず以下マン、以上マンを見つける
#　上72回まで
# その後は8回

def doubling(nex:list, k:int = 1<<60 ,a:list = None) -> list:
    """nex:操作列 k:回数 a:初期列"""
    n = len(nex)
    #繰り返し回数の取得
    log = (k+1).bit_length()
    
    res = [nex[:]] #ダブリング配列
    
    #1,2,4,8...と入る
    p = [1,-1]
    for cnt in range(1,log):
        res.append([0]*n)
        for i in range(n):
            res[cnt][i] = res[cnt-1][i] + p[i%2] * res[cnt-1][res[cnt-1][i]]
            # 遷移先ではなく移動回数を保存しておくveri
            # res[cnt][i] = res[cnt-1][(res[cnt-1][i]+i)%n] + res[cnt-1][i]
            
    if k == 1<<60: return res
    
    #0回目の遷移(つまり初期状態)
    ans = ([*range(n)] if a is None else a[:])
    for cnt in range(log):
        if k & (1<<cnt) != 0:
            ans = [ans[res[cnt][i]] for i in range(n)]
            # ans = [res[cnt][(ans[i]+i)%n] + ans[i] for i in range(n)]
    
    return ans


n,k = MI()
a = LI()
if n == 1:
    print(*a)
    exit()

p = [1,-1]
if k%2 == 1:
    k -= 1
    na = [p[i%2]*a[i] for i in range(n)]
    for i in range(n-1):
        na[i+1] += na[i]
    a = na[:]
k //= 2 #回やる

# ans = doubling(a,k)
# print(ans)

na = [0]*n
ans = [0]*n
ans[0] = na[0] = a[0]%mod
ans[1] = na[1] = a[1]%mod

div2 = pow(2,-1,mod)
for i in range(2,n):
    na[i] = a[i] + na[i-2] #次のはじめ
    
    tmp = (ans[i-2] + na[i-2]) * k * div2 % mod
    ans[i] = (a[i] + tmp)%mod 

print(*ans)
0