zerodedication's blog

By zerodedication, history, 2 months ago, In English

I tried to solve the problem but am getting 341102826 248150917 1 this answer for n=60 Clearly it is having one more than the expected answer for boris ! Attaching my code below ! NEED HELP

# cook your dish here
import math

mod = 998244353
def calc(n , r): 
    num = math.factorial(n)
    den = math.factorial(r)*math.factorial(n-r)
    return (num/den)
    
dp=[]
t = int(input())
for i in range(70):
    dp.append([0,0])
dp[2][0] = 1 
dp[2][1]=  0 
for i in range(4,70,2): 
    temp = i//2
    half = math.factorial(i-1)//(math.factorial(temp-1)*math.factorial(i-temp))
    dp[i][0] = dp[i-2][1]+half
    dp[i][1]=calc(i,i//2)-dp[i][0]-1

for test in range(0 , t) : 
    n = int(input())
    print(int(dp[n][0])%mod,int(dp[n][1])%mod,1)
 
 
 
 
  • Vote: I like it
  • -1
  • Vote: I do not like it

»
2 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

return num*modInverse(den) from calc function. modInverse can be calculated using fermats theorem modInverse(den) = den^(mod-2) under modulo mod when mod is prime.

For reference:

import math

mod = 998244353
def power(a, b):
    if b==0:
       return 1 
    if b%2==1:
        return a%mod*power(a,b-1)%mod
    return power(a%mod*a%mod,b/2)%mod

def calc(n , r): 
    num = math.factorial(n)
    den = math.factorial(r)*math.factorial(n-r)
    return (num*power(den,mod-2))
    
dp=[]
t = int(input())
for i in range(70):
    dp.append([0,0])
dp[2][0] = 1 
dp[2][1]=  0 
for i in range(4,70,2): 
    temp = i//2
    half = math.factorial(i-1)//(math.factorial(temp-1)*math.factorial(i-temp))
    dp[i][0] = dp[i-2][1]+half
    dp[i][1]=calc(i,i//2)-dp[i][0]-1

for test in range(0 , t) : 
    n = int(input())
    print(int(dp[n][0])%mod,int(dp[n][1])%mod,1)