Submission #65900164

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
mod=998244353
for _ in range(int(input())):
    n,k=map(int,input().split())
    binomal=list(map(int,bin(n)[2:]))
    dp_cnt=[[0,0]for _ in range(k+1)]
    dp_sum=[[0,0] for _ in range(k+1)]
    dp_cnt[0][1]=1
    for bit in binomal:
        ndp_cnt=[[0,0]for _ in range(k+1)]
        ndp_sum=[[0,0]for _ in range(k+1)]
        for c in range(k+1):
            for now in range(2):
                cnt=dp_cnt[c][now]
                s=dp_sum[c][now]
                if not cnt:continue
                for d in range(2):
                    if now and d>bit:continue
                    nt=now and d==bit
                    nc=c+d
                    if nc>k:continue
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

mod=998244353

for _ in range(int(input())):
    n,k=map(int,input().split())
    binomal=list(map(int,bin(n)[2:]))
    dp_cnt=[[0,0]for _ in range(k+1)]
    dp_sum=[[0,0] for _ in range(k+1)]
    dp_cnt[0][1]=1
    for bit in binomal:
        ndp_cnt=[[0,0]for _ in range(k+1)]
        ndp_sum=[[0,0]for _ in range(k+1)]
        for c in range(k+1):
            for now in range(2):
                cnt=dp_cnt[c][now]
                s=dp_sum[c][now]
                if not cnt:continue
                for d in range(2):
                    if now and d>bit:continue
                    nt=now and d==bit
                    nc=c+d
                    if nc>k:continue
                    ndp_cnt[nc][nt]+=cnt
                    ndp_cnt[nc][nt]%=mod
                    ndp_sum[nc][nt]+=s*2+d*cnt
                    ndp_sum[nc][nt]%=mod
        dp_cnt,dp_sum=ndp_cnt,ndp_sum
    print((dp_sum[k][0]+dp_sum[k][1])%mod)

Submission Info

Judge Result