結果

問題 No.2025 Select $k$-th Submultiset
コンテスト
ユーザー None
提出日時 2022-07-24 02:54:53
言語 PyPy3
(7.3.15)
結果
TLE  
(最新)
AC  
(最初)
実行時間 -
コード長 4,034 bytes
コンパイル時間 172 ms
コンパイル使用メモリ 82,432 KB
実行使用メモリ 209,924 KB
最終ジャッジ日時 2024-07-05 23:50:30
合計ジャッジ時間 4,630 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other TLE * 1 -- * 41
権限があれば一括ダウンロードができます

ソースコード

diff # 

#####################################################################################################
##### 畳み込み
#####################################################################################################

"""
O(N log N)
"""

def gcd_inv(a, b):
    a %= b
    if a == 0: return b, 0
    s = b
    t = a
    m0 = 0
    m1 = 1
    while t:
        u = s // t
        s -= t * u
        m0 -= m1 * u
        s, t = t, s
        m0, m1 = m1, m0
    if m0 < 0: m0 += b // s
    return s, m0

def crt(Rs,MODs):
    """
    Find solution s.t.
    x = R1 (MOD1)
    x = R2 (MOD2)
    x = R3 (MOD3)
        .
        .
    up to MOD=MOD1*MOD2*MOD3*....
    """
    assert len(Rs)==len(MODs)
    n = len(Rs)
    r0 = 0
    m0 = 1
    for i in range(n):
        assert 1<=MODs[i]
        r1 =Rs[i]%MODs[i]
        m1 = MODs[i]
        if m0 < m1:
            r0, r1 = r1, r0
            m0, m1 = m1, m0
        if m0 % m1 == 0:
            if r0 % m1 != r1: return 0, 0
            continue
        g, im = gcd_inv(m0, m1)
        u1 = m1 // g
        if (r1 - r0) % g: return 0, 0
        x = (r1 - r0) // g * im % u1
        r0 += x * m0
        m0 *= u1
        if (r0 < 0): r0 += m0
    return r0, m0

def ntt(A, n):
    for i in range(n):
        m = 1<<(n-i-1)
        for s in range(1<<i):
            w = 1
            s *= m*2
            for j in range(m):
                A[s+j], A[s+j+m] = (A[s+j]+A[s+j+m])%mod, (A[s+j]-A[s+j+m])*w%mod
                w *= roots[n-i]
                w %= mod

def intt(A, n):
    for i in range(n):
        m = 1<<i
        for s in range(1<<(n-i-1)):
            w = 1
            s *= m*2
            for j in range(m):
                A[s+j], A[s+j+m] = (A[s+j]+A[s+j+m]*w)%mod, (A[s+j]-A[s+j+m]*w)%mod
                w *= inv_roots[i+1]
                w %= mod
    inv = pow((mod+1)//2, n, mod)
    for i in range(1<<n):
        A[i] *= inv
        A[i] %= mod

def convolution(A, B):
    A=A[:]
    B=B[:]
    la = len(A)
    lb = len(B)
    deg = la + lb - 2
    n = deg.bit_length()
    N = 1<<n
    A += [0]*(N-la)
    B += [0]*(N-lb)
    ntt(A, n)
    ntt(B, n)
    A = [a*b%mod for a, b in zip(A, B)]
    intt(A, n)
    return A[:deg+1]


#######################################################################
def example():
    global input
    example = iter(
        """
6 10000
1000 2000 3000 4000 5000 6000
10
65769569579799458
42608972886666190
76184379495896651
37112714773176682
26896988026260061
64809455699325470
29169480516878400
87070971017458999
66497403686690100
18875969223705697





        """
            .strip().split("\n"))
    input = lambda: next(example)


#######################################################################
import sys
input = sys.stdin.readline
from bisect import *

# example()

N,L=map(int, input().split())
C=list(map(int, input().split()))


MODs = [167772161,469762049,998244353]

tmp=[]
for mod in MODs:
    primitive_root = 3
    roots = [pow(primitive_root, (mod-1)>>i, mod) for i in range(24)]
    inv_roots = [pow(root, mod-2, mod) for root in roots]
    B=[1]+[0]*L
    CNT=[]
    for i in range(N)[::-1]:
        A=[1]*(C[i]+1)
        B = convolution(B, A)
        B = B[:L+1]
        CNT.append(B[::])
    CNT=CNT[:-1]
    CNT.reverse()
    S=[[0]*(L+2) for _ in range(N-1)]
    for k in range(N-1):
        for i in range(L+1): # 自由パラメタの個数
            S[k][i+1]+=S[k][i]+CNT[k][i]

    tmp.append(S)

S=[[0]*(L+2) for _ in range(N-1)]
for k in range(N-1):
    for i in range(L+2):
        S[k][i]=crt((tmp[0][k][i],tmp[1][k][i],tmp[2][k][i]),MODs)[0]



Q=int(input())
for _ in range(Q):
    k=int(input())
    res=[]
    l=L
    for p in range(N-1):
        i=bisect_left(S[p],k+S[p][max(l-C[p],0)])-1 # 自由パラメタ i個からi+1個のどこか
        k-=S[p][i]-S[p][max(l-C[p],0)]
        # print(i,k,l-i)
        res.append(l-i)
        l=i
    res.append(l)
    for i in range(N):
        if res[i]<0:
            print(-1)
            break
    else:
        print(*res)
0