Problem:


Score : 700 points

Problem Statement

Takahashi throws N dice, each having K sides with all integers from 1 to K. The dice are NOT pairwise distinguishable.
For each i=2,3,...,2K, find the following value modulo 998244353:

The number of combinations of N sides shown by the dice such that the sum of no two different sides is i.

Note that the dice are NOT distinguishable, that is, two combinations are considered different when there exists an integer k such that the number of dice showing k is different in those two.

Constraints

1 \leq K \leq 2000

2 \leq N \leq 2000

K and N are integers.

Input

Input is given from Standard Input in the following format:

K N

Output

Print 2K-1 integers. The t-th of them (1\leq t\leq 2K-1) should be the answer for i=t+1.

Sample Input 1

3 3

Sample Output 1

7
7
4
7
7

For i=2, the combinations (1,2,2),(1,2,3),(1,3,3),(2,2,2),(2,2,3),(2,3,3),(3,3,3) satisfy the condition, so the answer is 7.

For i=3, the combinations (1,1,1),(1,1,3),(1,3,3),(2,2,2),(2,2,3),(2,3,3),(3,3,3) satisfy the condition, so the answer is 7.

For i=4, the combinations (1,1,1),(1,1,2),(2,3,3),(3,3,3) satisfy the condition, so the answer is 4.

Sample Input 2

4 5

Sample Output 2

36
36
20
20
20
36
36

Sample Input 3

6 1000

Sample Output 3

149393349
149393349
668669001
668669001
4000002
4000002
4000002
668669001
668669001
149393349
149393349



Sample input:
3 3


Sample output:
7
7
4
7
7

Submission status: Runtime Error

Solution code:
mod=998244353
k,n=map(int,input().split())

def modinv(n):
    return pow(n,mod-2,mod)
m=n+k
Fact=[1]
for i in range(1,m+1):
    Fact.append(Fact[i-1]*i%mod)
Finv=[0]*(m+1)
Finv[-1]=modinv(Fact[-1])
for i in range(m-1,-1,-1):
    Finv[i]=Finv[i+1]*(i+1)%mod
def comb(n,r):
    if n<r:
        return 0
    return Fact[n]*Finv[r]*Finv[n-r]%mod
def hcomb(n,r):
    return comb(n+r-1,r)
Pow=[1]*(n+1)
for i in range(n):
    Pow[i+1]=Pow[i]*2%mod
def solve(x):
    ret=0
    if x%2:
        p=x//2
        for q in range(p+1):
            ret+=Pow[q]*comb(p,q)*hcomb(k-2*p+q,n-q)
            ret%=mod
    else:
        p=x//2-1
        for q in range(p+1):
            ret+=Pow[q]*comb(p,q)*(hcomb(k-2*p+q-1,n-q)+hcomb(k-2*p+q-1,n-q-1))
            ret%=mod
    return ret

Ans=[]
for i in range(2,k+2):
    Ans.append(solve(i))
print(*Ans, sep="\n")
print(*reversed(Ans[:-1]),sep="\n")

Submission status: Runtime Error

Solution code:
from collections import Counter
K, N = map(int, input().split())
mod = 998244353
frac = [1]*2010
for i in range(2,2010):
    frac[i] = i * frac[i-1]%mod
def comb(a, b):
    if not a >= b >= 0:
        return 0
    return frac[a]*pow(frac[b], mod-2, mod)*pow(frac[a-b], mod-2, mod)%mod
A = Counter()
def calc(x):
    if A[x]:
        return A[x]
    res = 0
    for i in range(N//2+1):
        res = (res + (-1)**i*comb(x, i)*comb(N+K-1-2*i, N-2*i))%mod
    A[x] = res
    return res
for j in range(2, 2*K+1):
    print(calc(min(j, (2*K+2-j))//2))

Submission status: Runtime Error

Solution code:
def check(Ncount,min,K,not_this,i):
  count=0
  if Ncount==0:
    return 1

  for x in range(min,K+1):
    if x in not_this:
      continue
    elif K>=(i-x)>=1:
      not_this.append(i-x)
      count+=check(Ncount-1,x,K,not_this,i)
      not_this.pop()
    else:
      count+=check(Ncount-1,x,K,not_this,i)
  
  return count
    


K,N=[int(x) for x in input().split()]

for i in range(2,2*K+1):
  not_this=[]
  print(check(N,1,K,not_this,i))

Submission status: Runtime Error

Solution code:
def check(Ncount,min,K,not_this,i):
  count=0
  if Ncount==0:
    return 1

  for x in range(min,K+1):
    if x in not_this:
      continue
    elif K>=(i-x)>=1:
      not_this.append(i-x)
      count+=check(Ncount-1,x,K,not_this,i)
      not_this.pop()
    else:
      count+=check(Ncount-1,x,K,not_this,i)
  
  return count
    


K,N=[int(x) for x in input().split()]

for i in range(2,2*K):
  not_this=[]
  print(check(N,1,K,not_this,i))

Submission status: Runtime Error

Solution code:
def check(Ncount,min,K,not_this,i):
  count=0
  if Ncount==0:
    return 1

  for x in range(min,K+1):
    if x in not_this:
      continue
    elif K>=(i-x)>=1:
      not_this.append(i-x)
      count+=check(Ncount-1,x,K,not_this,i)
      not_this.pop()
    else:
      count+=check(Ncount-1,x,K,not_this,i)
  
  return count
    


K,N=[int(x) for x in input().split()]
print (K,N)

for i in range(2,2*K):
  not_this=[]
  print(check(N,1,K,not_this,i))

Submission status: Runtime Error

Solution code:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vi;
typedef pair<ll,ll> pi;
typedef vector<pi> vpi;
typedef long double ld;
#define mp make_pair
#define pb push_back
#define f first
#define s second
ll MOD = 998244353;
ll INF = 1e15;
#define lb lower_bound
#define ub upper_bound
#define SZ(x) (ll)x.size()
#define ALL(x) x.begin(),x.end()

ll mod(ll a, ll m){
  return (a+m)%m;
}

ll inverse(ll a, ll m){
  a = mod(a, m);
  if (a <= 1)return a;
  return mod((1 - inverse(m, a) * m) / a,m);
}

ll N,K,tmp,l;
ll memo[2020][2020][2];
stack<ll> st;

ll ask(ll a, ll b, ll c){
  // cout<<"Ask " << a << ' ' << b << '\n';
  if (memo[a][b][c] != -1)return memo[a][b][c];
  assert(b);
  return memo[a][b][c] = (2*ask(a-1,b-1,c) - ask(a-2,b-1,c)) % MOD;
}

int main(){
  // freopen("input.txt","r",stdin);
  cin>>K>>N;
  memset(memo,-1,sizeof(memo));
  tmp = 1;
  memo[0][0][0] = 0;
  memo[1][0][0] = 1;
  for (int i=2;i<=K;++i){
    tmp = (tmp * (i+N-1)) % MOD;
    tmp = (tmp * inverse(i-1, MOD)) % MOD;
    memo[i][0][0] = tmp;
  }
  tmp = 1;
  memo[0][0][1] = 0;
  memo[1][0][1] = 1;
  for (int i=2;i<=K;++i){
    tmp = (tmp * (i+N-2)) % MOD;
    tmp = (tmp * inverse(i-1, MOD)) % MOD;
    memo[i][0][1] = tmp;
  }

  for (int i=2;i<=K+1;++i){
    if (i % 2 == 0){
      l = ask(K-1,(i-1)/2,0) + ask(K-1,(i-1)/2,1);
    }
    else l = ask(K,i/2,0);
    cout<<l<<'\n';
    st.push(l);
  }
  st.pop();
  while(SZ(st)){cout<<st.top()<<'\n';st.pop();}
}

Submission status: Runtime Error

Solution code:
K,N=map(int,input().split())
mod=998244353
table=[1]*(2*N+5)
t=1
for i in range(1,2*N+5):
    t*=i
    t%=mod
    table[i]=t
rtable=[1]*(2*N+5)
t=1
for i in range(1,2*N+5):
    t*=pow(i,mod-2,mod)
    t%=mod
    rtable[i]=t
ans=[]
for k in range(2,K+2):
    num=0
    if k%2==1:
        l=k//2
        p=l
        r=K-2*l
        for q in range(l+1):
            if N-q>=0 and r+q-1>=0:
                s=(table[l]*rtable[q]*rtable[l-q])%mod
                s=(s*pow(2,q,mod))%mod
                t=(table[N+r-1]*rtable[N-q]*rtable[r+q-1])%mod
                s=(s*t)%mod
                num+=s
                num=num%mod
                #print(10,q,k,l,p,num,s)
        ans.append(num)
    else:
        l=k//2
        p=l-1
        r=K-k+1
        for q in range(p+1):
            if N-q-1>=0 and r+q-1>=0:
                s=(table[p]*rtable[q]*rtable[p-q])%mod
                s=(s*pow(2,q,mod))%mod
                t=(table[N+r-2]*rtable[N-q-1]*rtable[r+q-1])%mod
                s=(s*t)%mod
                num+=s
                num%=mod
                #print(9,q,k,l,p,num,s)
            if N-q>=0 and r+q-1>=0:
                s=(table[p]*rtable[q]*rtable[p-q])%mod
                s=(s*pow(2,q,mod))%mod
                t=(table[N+r-1]*rtable[N-q]*rtable[r+q-1])%mod
                s=(s*t)%mod
                num+=s
                num%=mod 
                #print(10,q,k,l,p,num,s)
        ans.append(num)
print('\n'.join(map(str,ans)))
ans=ans[::-1]
print('\n'.join(map(str,ans[1:])))

Submission status: Runtime Error

Solution code:
import math
import sys
K, N = [int(i) for i in input().split(' ')]
mod = 998244353
sys.setrecursionlimit(100000)

def mul(a, b):
    return ((a % mod) * (b % mod)) % mod

def power(x, y):
    if   y == 0     : return 1
    elif y == 1     : return x % mod
    elif y % 2 == 0 : return power(x, y//2)**2 % mod
    else            : return power(x, (y-1)//2)**2 * x % mod

def div(a, b):
    return mul(a, power(b, mod-2))

def C(n, r):
    if r < 0:
        return 0
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

olist = [C(N+K-2, N) % mod]

def EE(i):
    k2 = int((K - abs(K - int((i-1)/2) * 2) )/2)
    k1 = K - k2*2 - (1 if i % 2 == 0 else 0)
    result = 0
    for j in range(min(k2, N+1)):
        if i % 2 == 1:
            olist[j] = div(olist[j] * k2, k2-j)
        olist[j] = div(olist[j] * (k1+j) , N+k1)
        result = (result + olist[j]) % mod
        if i % 2 == 0 and j != N:
            result = (result + div(olist[j] * (N-j), N+k1-1)) % mod

    if N >= k2:
        if i % 2 == 1:
            olist.append((C(k2, k2) * C(N+k1-1, N-k2) * pow(2, k2)) % mod)
        else:
            if i != 2:
                olist[k2] = div(olist[k2] * (k1+k2), N+k1)
            result = (result + div(olist[k2] * (N-k2), N+k1-1)) % mod
        result = (result + olist[k2]) % mod
    return result

result = []
for i in range(K):
    alist = []
    result.append(str(EE(i+2)))
print("\n".join(result + result[:-1][::-1]))

Submission status: Runtime Error

Solution code:
def prepare(k, n, MOD):
    def get_factorials(m):
        f = 1
        factorials = [1]
        for m in range(1, m + 1):
            f *= m
            f %= MOD
            factorials.append(f)
        inv = pow(f, MOD - 2, MOD)
        invs = [1] * (m + 1)
        invs[m] = inv
        for m in range(m, 1, -1):
            inv *= m
            inv %= MOD
            invs[m - 1] = inv

        return factorials, invs

    def solve(p):
        """Number of patterns where no pair of p appears when n dices are rolled"""
        if cache[p] > -1:
            return cache[p]

        ret = 0
        fp = factorials[p]
        for q in range(1, min(p, n // 2) + 1):
            tmp1 = (fp * invs[q] % MOD) * invs[p - q] % MOD
            tmp2 = (factorials[k + n - 2 * q - 1] * invs[n - 2 * q] % MOD) * ik % MOD
            if q % 2 == 1:
                ret += tmp1 * tmp2
            else:
                ret -= tmp1 * tmp2
            ret %= MOD

        cache[p] = ret = (all_patterns - ret) % MOD
        return ret

    factorials, invs = get_factorials(k + n)
    ik = invs[k - 1]
    all_patterns = factorials[k + n - 1] * invs[n] * ik % MOD
    cache = [-1] * (k // 2 + 1)

    return solve


MOD = 998244353
k, n = map(int, input().split())
if k == 1:
    print(0)
else:
    solve = prepare(k, n, MOD)
    ans = [solve(i // 2 - max(0, i - k - 1)) for i in range(2, k + 2)]
    print('\n'.join(map(str, ans)))
    print('\n'.join(map(str, ans[-2::-1])))

Submission status: Runtime Error

Solution code:
from math import factorial

def C(n,r):
    return factorial(n)/factorial(r)/factorial(n-r)

def H(n,r):
    return C(n+r-1,r)

K,N=map(int,input().split())

for t in range(2,K+1):
    ans=0
    if t%2:
        for q in range((t+1)//2):
            使う数字の場合の数=C((t-1)/2,q)*(2**((t-1)/2-q))
            選び方=H(K-(t-1)/2-q,N-((t-1)/2-q))
            ans+=使う数字の場合の数*選び方
            
    else:
        for q in range(t//2):
            使う数字の場合の数=C((t-2)/2,q)*(2**((t-2)/2-q))
            選び方=H(K-(t-2)/2-q-1,N-((t-2)/2-q))+H(K-(t-2)/2-q-1,N-((t-2)/2-q)-1)
            ans+=使う数字の場合の数*選び方
    print(ans%998244353)
    
t=K+1
ans=0
if t%2:
    for q in range((K+1)//2):
        使う数字の場合の数=C((t-1)/2,q)*(2**((t-1)/2-q))
        選び方=H(K-(t-1)/2-q,N-((t-1)/2-q))
        ans+=使う数字の場合の数*選び方
else:
    for q in range(K//2):
        使う数字の場合の数=C((t-2)/2,q)*(2**((t-2)/2-q))
        選び方=H(K-(t-2)/2-q-1,N-((t-2)/2-q))+H(K-(t-2)/2-q-1,N-((t-2)/2-q)-1)
        ans+=使う数字の場合の数*選び方
    
for t in range(K,1,-1):
    ans=0
    if t%2:
        for q in range((t+1)//2):
            使う数字の場合の数=C((t-1)/2,q)*(2**((t-1)/2-q))
            選び方=H(K-(t-1)/2-q,N-((t-1)/2-q))
            ans+=使う数字の場合の数*選び方
            
    else:
        for q in range(t//2):
            使う数字の場合の数=C((t-2)/2,q)*(2**((t-2)/2-q))
            選び方=H(K-(t-2)/2-q-1,N-((t-2)/2-q))+H(K-(t-2)/2-q-1,N-((t-2)/2-q)-1)
            ans+=使う数字の場合の数*選び方
    print(ans%998244353)

Submission status: Runtime Error

Solution code:
K,N = map(int,input().split())

MOD = 998244353

fact = [1]*3000
t = 1
for i in range(1,3000):
    t = (t*i)%MOD
    fact[i] = t

def ncr(n,r):
    return (fact[n] * pow(fact[r],MOD-2,MOD) % MOD) * pow(fact[n-r],MOD-2,MOD) % MOD

for i in range(2,2*K+1):
    t1,t2 = 0,0
    Ans = 0
    # p : 足して i になる整数の組の数
    np = i//2 - max(i-1-K,0)
    # p組からq組, 片方を使用する場合の数を足し合わせる
    # 偶奇で場合分け
    if i%2==0:
        # 偶数の場合 : 1組だけ同じ数の組があるため特別扱いする
        np -= 1
        for nq in range(np+1):
            # 同じ数の組の数字を全く含まない場合
            t1 = ncr(np,nq)*(2**nq)
            t1 %= MOD
            nr = K - np*2 - 1
            t2 = ncr(N+nr-1,N-nq) if N+nr-1>=N-nq else 0
            t2 %= MOD
            Ans += t1*t2
            # 同じ数の組の数字を1つ含む場合
            t2 = ncr(N-1+nr-1,N-1-nq) if N-1+nr-1>=N-1-nq else 0
            t2 %= MOD
            Ans += t1*t2
    else:
        # 奇数の場合 : p組全て互いに異なる数
        for nq in range(np+1):
            t1 = ncr(np,nq)*(2**nq)
            t1 %= MOD
            nr = K - np*2
            t2 = ncr(N+nr-1,N-nq) if N-1+nr-1>=N-1-nq else 0
            t2 %= MOD
            Ans += t1*t2
    print(Ans%MOD)

Submission status: Runtime Error

Solution code:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 998244353
eps = 10**-7
def inp(): return int(input())
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())

K,N = inpl()
MAX = K+N+10
fac = [1]*(MAX+1)
for i in range(1,MAX+1):
	fac[i] = (fac[i-1]*i)%mod

gyakugen = [1]*(MAX+1)
gyakugen[MAX] = pow(fac[MAX],mod-2,mod)
for i in range(MAX,0,-1):
	gyakugen[i-1] = (gyakugen[i]*i)%mod

def Comb(n,k):#nCk
	return (fac[n]*gyakugen[k]*gyakugen[n-k])%mod

#K=k,N=n,0pair = 0
def calc(k,n,i):
	#i=2に帰着させる
	pairs = (i-2)//2
	k -= pairs
	n -= pairs

	#色々と例外処理
	if n < 0 or k <= 0:
		return 0
	elif k == 1 and n >= 2:
		return 0

	if n == 0: 	 #球が0個なら1通り
		ans = 1
	elif n == 1: #球が1個ならそれぞれ1個ずつ入れてn通り
		ans = n 
	else:
		ans = 0
		#i=2の時の数え上げ
		for x in range(2):
			ball = n-x	#球
			box = k-1	#箱
			ans += Comb(box-1+ball,ball)%mod
			
	ans *= pow(2,x,mod)	#0pairの選び方
	return ans % mod

ans = []
for i in range(2,K+2):
	if i%2 == 0:
		pairs = (i-2)//2
		tmp = 0
		for p0 in range(pairs+1): #p0 = 0pairの数
			tmp += calc(K-p0*2,N,i-p0*2)*Comb(pairs,p0)%mod
			tmp %= mod
	ans.append(tmp)
	print(tmp)

ans = ans[::-1]
for i in range(1,K):
	print(ans[i])

Submission status: Runtime Error

Solution code:
from math import factorial

def C(n,r):
    return factorial(n)/factorial(r)/factorial(n-r)

def H(n,r):
    return C(n+r-1,r)

K,N=map(int,input().split())
answer=[]
for t in range(2,K+1):
    ans=0
    if t%2:
        for q in range((t+1)//2):
            使う数字の場合の数=C((t-1)/2,q)*(2**((t-1)/2-q))
            選び方=H(K-(t-1)/2-q,N-((t-1)/2-q))
            ans+=使う数字の場合の数*選び方
            
    else:
        for q in range(t//2):
            使う数字の場合の数=C((t-2)/2,q)*(2**((t-2)/2-q))
            選び方=H(K-(t-2)/2-q-1,N-((t-2)/2-q))+H(K-(t-2)/2-q-1,N-((t-2)/2-q)-1)
            ans+=使う数字の場合の数*選び方
    answer.append(ans%998244353)
t=K+1
ans=0
if t%2:
    for q in range((K+1)//2):
        使う数字の場合の数=C((t-1)/2,q)*(2**((t-1)/2-q))
        選び方=H(K-(t-1)/2-q,N-((t-1)/2-q))
        ans+=使う数字の場合の数*選び方
else:
    for q in range(K//2):
        使う数字の場合の数=C((t-2)/2,q)*(2**((t-2)/2-q))
        選び方=H(K-(t-2)/2-q-1,N-((t-2)/2-q))+H(K-(t-2)/2-q-1,N-((t-2)/2-q)-1)
        ans+=使う数字の場合の数*選び方
        
for a in answer:
    print(a)
print(ans%998244353)
for a in reversed(answer):
    print(a)

Submission status: Runtime Error

Solution code:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 998244353
eps = 10**-7
def inp(): return int(input())
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())

K,N = inpl()

MAX = 1000*3
fac = [1]*(MAX+1)
for i in range(1,MAX+1):
	fac[i] = (fac[i-1]*i)%mod

gyakugen = [1]*(MAX+1)
gyakugen[MAX] = pow(fac[MAX],mod-2,mod)
for i in range(MAX,0,-1):
	gyakugen[i-1] = (gyakugen[i]*i)%mod

def Comb(n,k):#nCk
	return (fac[n]*gyakugen[k]*gyakugen[n-k])%mod

#K=k,N=n,0pair = 0
def calc(k,n,i):
	x = (i-2)//2
	k -= x
	n -= x
	if k == 1:
		if n <= 1:
			return n
		else:
			return 0
	tmp = 0
	for j in range(2):
		zb = n-j
		zm = k-2
		tmp += Comb(zb+zm,zb)%mod
	tmp %= mod
	tmp *= (2**x)%mod
	return tmp

ans = []
for i in range(2,K+2):
	if i%2 == 0:
		pairs = (i-2)//2
		tmp = 0
		for p0 in range(pairs+1):
			tmp += calc(K-p0*2,N,i-p0*2)*Comb(pairs,p0)%mod
			tmp %= mod
	ans.append(tmp)
	print(tmp)

ans = ans[::-1]

for i in range(1,K):
	print(ans[i])

Submission status: Runtime Error

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**13
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    l = I()
    if l < 60:
        r = ["2 {}".format(l)]
        for i in range(l):
            r.append("1 2 {}".format(i))
        return '\n'.join(r)
    n = 1
    while 2**n <= l:
        n += 1
    a = [2**(n-i-1) for i in range(n)] + [0]
    r = []
    for i in range(1,n):
        r.append("{} {} 0".format(i,i+1))
        r.append("{} {} {}".format(i,i+1,a[i]))
    t = sum(a) - a[0]
    l -= t
    for i in range(0,n):
        if l >= a[i]:
            r.append("1 {} {}".format(i+1,t+1))
            t += a[i]
            l -= a[i]

    return "{} {}\n".format(n,len(r)) + '\n'.join(r)


print(main())

Submission status: Runtime Error

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**13
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    l = I()
    if l < 60:
        r = ["2 {}".format(l)]
        for i in range(l):
            r.append("1 2 {}".format(i))
        return '\n'.join(r)
    n = 1
    while 2**n <= l:
        n += 1
    a = [2**(n-i-1) for i in range(n)] + [0]
    r = []
    for i in range(1,n):
        r.append("{} {} 0".format(i,i+1))
        r.append("{} {} {}".format(i,i+1,a[i]))
    t = sum(a[1:])
    l -= t
    for i in range(n):
        if l >= a[i]:
            r.append("1 {} {}".format(i+1,t+1))
            t += a[i]
            l -= a[i]

    return "{} {}\n".format(n,len(r)) + '\n'.join(r)


print(main())

Submission status: Runtime Error

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**13
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    l = I()
    if l < 60:
        r = ["2 {}".format(l)]
        for i in range(l):
            r.append("1 2 {}".format(i))
        return '\n'.join(r)
    n = 1
    while 2**n <= l:
        n += 1
    a = [2**(n-i-1) for i in range(n)] + [0]
    r = []
    for i in range(1,n):
        r.append("{} {} 0".format(i,i+1))
        r.append("{} {} {}".format(i,i+1,a[i]))
    t = sum(a[1:])
    l -= t
    # print('s',t,l)
    for i in range(0,n):
        if l >= a[i]:
            r.append("1 {} {}".format(i+1,t+1))
            t += a[i]
            l -= a[i]
            # print('ai',a[i],t,l)

    return "{} {}\n".format(n,len(r)) + '\n'.join(r)


print(main())