We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
mod = 10**9+7
MAX = 1001
l1,l2,l3=[[0]*MAX for i in range(MAX)],[0]*MAX,[0]MAX
for j in range(MAX):
for k in range(j+1):
l1[j][k]=1 if k==0 or k==j else (l1[j-1][k-1]+l1[j-1][k])%mod
l2[j]=(pow(2, j(j-1), mod)-sum(l1[j][i]pow(2, (j-1)(j-i), mod)*l2[i] for i in range(1,j)))%mod
l3[j]=(l2[j]+sum(l1[j-1][i-1]*l3[i]*l2[j-i] for i in range(1,j)))%mod
for _ in range(int(input())):
print(l3[int(input())])
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Strongly Connected Digraphs
You are viewing a single comment's thread. Return to all comments →
mod = 10**9+7 MAX = 1001 l1,l2,l3=[[0]*MAX for i in range(MAX)],[0]*MAX,[0]MAX for j in range(MAX): for k in range(j+1): l1[j][k]=1 if k==0 or k==j else (l1[j-1][k-1]+l1[j-1][k])%mod l2[j]=(pow(2, j(j-1), mod)-sum(l1[j][i]pow(2, (j-1)(j-i), mod)*l2[i] for i in range(1,j)))%mod l3[j]=(l2[j]+sum(l1[j-1][i-1]*l3[i]*l2[j-i] for i in range(1,j)))%mod
for _ in range(int(input())): print(l3[int(input())])