Problem:


Score : 600 points

Problem Statement

You are given an integer sequence of length n+1, a_1,a_2,...,a_{n+1}, which consists of the n integers 1,...,n.
It is known that each of the n integers 1,...,n appears at least once in this sequence.

For each integer k=1,...,n+1, find the number of the different subsequences (not necessarily contiguous) of the given sequence with length k, modulo 10^9+7.

Notes

If the contents of two subsequences are the same, they are not separately counted even if they originate from different positions in the original sequence.

A subsequence of a sequence a with length k is a sequence obtained by selecting k of the elements of a and arranging them without changing their relative order. For example, the sequences 1,3,5 and 1,2,3 are subsequences of 1,2,3,4,5, while 3,1,2 and 1,10,100 are not.

Constraints

1 \leq n \leq 10^5

1 \leq a_i \leq n

Each of the integers 1,...,n appears in the sequence.

n and a_i are integers.

Input

Input is given from Standard Input in the following format:

n
a_1 a_2 ... a_{n+1}

Output

Print n+1 lines.
The k-th line should contain the number of the different subsequences of the given sequence with length k, modulo 10^9+7.

Sample Input 1

3
1 2 1 3

Sample Output 1

3
5
4
1

There are three subsequences with length 1: 1 and 2 and 3.

There are five subsequences with length 2: 1,1 and 1,2 and 1,3 and 2,1 and 2,3.

There are four subsequences with length 3: 1,1,3 and 1,2,1 and 1,2,3 and 2,1,3.

There is one subsequence with length 4: 1,2,1,3.

Sample Input 2

1
1 1

Sample Output 2

1
1

There is one subsequence with length 1: 1.

There is one subsequence with length 2: 1,1.

Sample Input 3

32
29 19 7 10 26 32 27 4 11 20 2 8 16 23 5 14 6 12 17 22 18 30 28 24 15 1 25 3 13 21 19 31 9

Sample Output 3

32
525
5453
40919
237336
1107568
4272048
13884156
38567100
92561040
193536720
354817320
573166440
818809200
37158313
166803103
166803103
37158313
818809200
573166440
354817320
193536720
92561040
38567100
13884156
4272048
1107568
237336
40920
5456
528
33
1

Be sure to print the numbers modulo 10^9+7.



Sample input:
3
1 2 1 3


Sample output:
3
5
4
1

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

n=int(input())
a=list(map(int,input().split()))
mod=10**9+7

cho=Counter(a).most_common()[0][0] #重複してる数字。

temp=[]
for i,j in enumerate(a):
  if j==cho:
    temp.append(i)

#1つ目の重複数の位置
x=temp[0]

#2つ目の重複数の位置
y=temp[1]

from operator import mul
from functools import reduce

def cmb(n,r):
    if n<r: return 0
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under



#コンビネーションは事前に計算しておく
#たとえばcmb(2,5)とかだったら2行目5列を取り出す感じ。
cm=[]
for i in range(n+10):
  cm.append(cmb(x+n-y,i))

zenbu=[]
for i in range(n+10):
  zenbu.append(cmb(n+1, i))

#「xcomのそれぞれの値に、yから「k-1-(xの長さ)」個までの選び方の累積和をかける」と重複の総数が求まる…？



for i in range(1,n+2): #長さiの部分列
  #選び方全部は何通り？
  souwa=zenbu[i]
  #そこから、重複を引く。
  temp=cm[i-1]
  print((souwa-temp)%mod)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

n=int(input())
a=list(map(int,input().split()))
mod=10**9+7

cho=Counter(a).most_common()[0][0] #重複してる数字。

temp=[]
for i,j in enumerate(a):
  if j==cho:
    temp.append(i)

#1つ目の重複数の位置
x=temp[0]

#2つ目の重複数の位置
y=temp[1]

from operator import mul
from functools import reduce

def cmb(n,r):
    if n<r: return 0
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under



#コンビネーションは事前に計算しておく
#たとえばcmb(2,5)とかだったら2行目5列を取り出す感じ。
cm=[]
for i in range(n+10):
  cm.append(cmb(x+n-y,i))

#「xcomのそれぞれの値に、yから「k-1-(xの長さ)」個までの選び方の累積和をかける」と重複の総数が求まる…？



for i in range(1,n+2): #長さiの部分列
  #選び方全部は何通り？
  zenbu=cmb(n+1, i)
  #そこから、重複を引く。
  temp=cm[i-1]
  print((zenbu-temp)%mod)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

n=int(input())
a=list(map(int,input().split()))
mod=10**9+7

cho=Counter(a).most_common()[0][0] #重複してる数字。

temp=[]
for i,j in enumerate(a):
  if j==cho:
    temp.append(i)

#1つ目の重複数の位置
x=temp[0]

#2つ目の重複数の位置
y=temp[1]

from operator import mul
from functools import reduce

def cmb(n,r):
    if n<r: return 0
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under



#コンビネーションは事前に計算しておく
#たとえばcmb(2,5)とかだったら2行目5列を取り出す感じ。
xcom=[]
ycom=[]
for i in range(n+1):
  xcom.append(cmb(x,i))
  ycom.append(cmb((n+1)-y-1,i))

#「xcomのそれぞれの値に、yから「k-1-(xの長さ)」個までの選び方の累積和をかける」と重複の総数が求まる…？



for i in range(1,n+2): #長さiの部分列
  #選び方全部は何通り？
  zenbu=cmb(n+1, i)
  #そこから、重複を引く。
  temp=cmb(x+n-y,i-1)
  print((zenbu-temp)%mod)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

n=int(input())
a=list(map(int,input().split()))
mod=10**9+7

cho=Counter(a).most_common()[0][0] #重複してる数字。

temp=[]
for i,j in enumerate(a):
  if j==cho:
    temp.append(i)

#1つ目の重複数の位置
x=temp[0]

#2つ目の重複数の位置
y=temp[1]

from operator import mul
from functools import reduce

def cmb(n,r):
    if n<r: return 0
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under



#コンビネーションは事前に計算しておく
#たとえばcmb(2,5)とかだったら2行目5列を取り出す感じ。
xcom=[]
ycom=[]
for i in range(n+1):
  xcom.append(cmb(x,i))
  ycom.append(cmb((n+1)-y-1,i))


for i in range(1,n+2): #長さiの部分列
  #選び方全部は何通り？
  zenbu=cmb(n+1, i)

  #そこから、重複を引く。
  temp=0

  #左と右の配分の合計はi-1。
  for j in range(i):
    temp+=xcom[j]*ycom[i-1-j]
  print((zenbu-temp)%mod)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

n=int(input())
a=list(map(int,input().split()))
mod=10**9+7

cho=Counter(a).most_common()[0][0] #重複してる数字。

temp=[]
for i,j in enumerate(a):
  if j==cho:
    temp.append(i)

#1つ目の重複数の位置
x=temp[0]

#2つ目の重複数の位置
y=temp[1]

from operator import mul
from functools import reduce

def cmb(n,r):
    if n<r: return 0
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under

for i in range(1,n+2): #長さiの部分列
  #選び方全部は何通り？
  zenbu=cmb(n+1, i)

  #そこから、重複を引く。
  temp=0

  #左と右の配分の合計はi-1。
  for j in range(i):
    temp+=cmb(x,j)*cmb((n+1)-y-1, i-1-j)
    #print(i,j,cmb(x,j),cmb((n+1)-y-1, i-1-j))
  print((zenbu-temp)%mod)

Submission status: Time Limit Exceeded

Solution code:
from operator import mul
from functools import reduce

MOD = 1000000007

mod_mul = lambda a,b:(a*b)%MOD

def cmb(n,r):
  r = min(n-r,r)
  if r < 0: return 0
  if r == 0: return 1

  over = reduce(mul, range(n, n - r, -1))
  under = reduce(mul, range(1,r + 1))
  return over // under

def solve():
  N = int(input())
  A = list(map(int, input().split()))
  counter = [-1]*(N+2)
  multi_num = -1
  left_element_num = -1
  right_element_num = -1
  for i, a_i in enumerate(A):
    if counter[a_i] != -1:
      left_element_num = counter[a_i]
      right_element_num = N-i
      break
    else:
      counter[a_i] = i

  # print(left_element_num, right_element_num)
  for i in range(1, N+2):
    if i == 1:
      print(N)
    elif i == N+1:
      print(1)
    else:
      ret = cmb(N+1, i)%MOD
      ret = (ret-cmb(left_element_num+right_element_num, i-1)%MOD)%MOD
      print(ret)
      
solve()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int, input().split()))

from collections import Counter
c = Counter(a)
for k in c.keys():
    if c[k] == 2:
        break
l = []
for i in range(len(a)):
    if a[i] == k:
        l.append(i)
d = n - l[1] + l[0]

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//2)**2 * x % mod

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

mod = (10 ** 9 + 7)
tmp = 1
for k in range(1, n + 2):
    tmp = mul(tmp, n - k + 2)
    tmp = div(tmp, k)

    if k == 1:
        dc = 1
    elif d >= k - 1:
        dc = mul(dc, (d - k + 2))
        dc = div(dc, k - 1)
    else:
        dc = 0
    print((tmp - dc) % mod)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int, input().split()))

from collections import Counter
c = Counter(a)
for k in c.keys():
    if c[k] == 2:
        break
l = []
for i in range(len(a)):
    if a[i] == k:
        l.append(i)

ll = l[0]
rr = len(a) - 1 - l[1]
d =  ll + rr

tmp = 1
dc = 1
for k in range(1, n + 2):
    tmp = tmp * (n - k + 2) // k
    # print(tmp)

    if k == 1:
        dc = 1
    elif d >= k - 1:
        dc = dc * (d - k + 2) // (k - 1)
    else:
        dc = 0
    print((tmp - dc) % (10 ** 9 + 7))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int, input().split()))


import math

def framod(n, mod, a=1):
    for i in range(1,n+1):
        a=a * i % mod
    return a

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

def comb(n, k, mod):
    a=framod(n, mod)
    b=framod(k, mod)
    c=framod(n-k, mod)
    return (a * power(b, mod-2, mod) * power(c, mod-2, mod)) % mod


from collections import Counter
c = Counter(a)
for k in c.keys():
    if c[k] == 2:
        break
l = []
for i in range(len(a)):
    if a[i] == k:
        l.append(i)

ll = l[0]
rr = len(a) - 1 - l[1]

for k in range(1, n + 2):
    tmp = comb(n + 1, k, 10 ** 9 + 7)
    # print(tmp)

    if ll + rr >= k - 1:
        dc = comb(ll + rr, k - 1, 10 ** 9 + 7)
    else:
        dc = 0
    print(tmp - dc)

Submission status: Time Limit Exceeded

Solution code:
class combination():
    #素数のmod取るときのみ　速い
    def __init__(self, n, mod):
        self.n = n
        self.fac = [1] * (n + 1)
        self.inv = [1] * (n + 1)
        for j in range(1, n + 1):
            self.fac[j] = self.fac[j - 1] * j % mod

        self.inv[n] = pow(self.fac[n], mod - 2, mod)
        for j in range(n - 1, -1, -1):
            self.inv[j] = self.inv[j + 1] * (j + 1) % mod

    def comb(self, n, r, mod):
        if r > n or n < 0 or r < 0:
            return 0
        return self.fac[n] * self.inv[n - r] * self.inv[r] % mod

def examD(mod):
    N = I()
    a = LI()
    double = []
    for s in a:
        if s in double:
            cur = s
            break
        double.append(s)
    curL = a.index(cur); curR = a[curL+1:].index(cur) + (curL+1)
    L = curL; M = curR-curL-1;  R = N - curR
#    print(curL,curR)
#    print(L,M,R)
    C = combination(N+1,mod)
    ans = []
    ans.append(N)
    for i in range(2,N+2):
        cur = C.comb(N+1,i,mod)
        if N-1-M-(i-1)>=0:
            cur -= C.comb(N-1-M,i-1,mod)
        if cur<0:
            cur += mod
        ans.append(cur)
    for v in ans:
        print(v)

import sys
import copy
import bisect
import heapq
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

examD(mod)

Submission status: Time Limit Exceeded

Solution code:
from operator import mul
from functools import reduce

def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under

mod=10**9+7
n=int(input())
a=list(map(int,input().split()))
data=[0]*(n+1)
for i in range(n+1):
    data[a[i]]+=1
for i in range(1,n+1):
    if data[i]==2:
        b=i
        break
l=[]
for i in range(n+1):
    if a[i]==b:
        l.append(i)
c=l[1]-l[0]+1
for k in range(1,n+3-c):
    ans=cmb(n+1,k)%mod-cmb(n+1-c,k-1)
    print(ans%mod)
for k in range(n+3-c,n+2):
    ans=cmb(n+1,k)%mod
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
#66d
#import itertools
import collections
import math

from functools import lru_cache

import sys
sys.setrecursionlimit(100000)

mod_by = 7 + 10**9

@lru_cache(maxsize=None)
def get_num_of_permutations(n,k):
    if k==1:
        return n
    else:
        return get_num_of_permutations(n-1,k-1)*n
    
@lru_cache(maxsize=None)
def factorial(n):
    if n<=1:
        return 1
    else:
        return math.factorial(n)
    
@lru_cache(maxsize=None)
def get_num_of_combinations(n,k):
    return get_num_of_permutations(n,k)//factorial(k)

n = int(input())

a_list = [int(e) for e in input().split()]
index_list = [i for i in range(1,len(a_list)+1)]

a_dict = dict(zip(index_list,a_list)) #dictの入力順序付き

#重複している値のインデックスを求める
c = collections.Counter(a_list)
#print(c.most_common()[0][0])
keys = [k for k, v in a_dict.items() if v == c.most_common()[0][0]]

before_repeated = keys[0]-1
after_repeated = n+1-keys[1]

#print(keys,"→",keys[0]-1,n+1-keys[1])

for k in range(1,n+2,1):
    if k==1:
        print(n)
    elif k==n+1:
        print(1)
    else:
        all = get_num_of_combinations(n+1,k)%mod_by
        
        #愚直解
        #l = list(itertools.combinations(a_list, k))
        #repeated = [x for x in set(l) if l.count(x) > 1]
        #print(all-repeated)
        
        repeated = 0
        
        for i in range(k):
            if i!=0:
                before = get_num_of_combinations(before_repeated,i)%mod_by
            else:
                before = 1
                
            if k-1-i!=0:
                after = get_num_of_combinations(after_repeated,k-1-i)%mod_by
            else:
                after = 1
            
            repeated += before*after%mod_by
            
        if (all - repeated)%mod_by < 0:
            print((all - repeated)%mod_by + mod_by)
        else:
            print((all - repeated)%mod_by)

Submission status: Time Limit Exceeded

Solution code:
def main():
    MOD = 10 ** 9 + 7
    n = int(input())
    a = list(map(int, input().split()))
    lst = [-1] * n

    # O(N)
    for i in range(n + 1):
        if lst[a[i] - 1] != -1:
            first = lst[a[i] - 1]
            second = i
            break
        lst[a[i] - 1] = i

    # print (first, second)    
    left = first
    right = n - second
    # print (left, right)

    N = n + 1
    tmp1 = 1
    tmp2 = 1
    # O(N ^ 2)
    for i in range(1, n + 2):
        tmp1 = (tmp1 * (N + 1 - i))//i
        if i == 1:
            tmp2 = 1
        elif left + right < i - 1:
            tmp2 = 0
        else:
            tmp2 = (tmp2 * (left + right + 1 - (i - 1))) // (i - 1)
        print ((tmp1 % MOD - tmp2 % MOD) % MOD)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    MOD = 10 ** 9 + 7
    n = int(input())
    a = list(map(int, input().split()))
    lst = [-1] * n

    # O(N)
    for i in range(n + 1):
        if lst[a[i] - 1] != -1:
            first = lst[a[i] - 1]
            second = i
            break
        lst[a[i] - 1] = i

    # print (first, second)    
    left = first
    right = n - second
    # print (left, right)

    N = n + 1
    tmp1 = 1
    tmp2 = 1
    # O(N ^ 2)
    for i in range(1, n + 2):
        tmp1 = (tmp1 * (N + 1 - i))//i
        if i == 1:
            tmp2 = 1
        elif left + right < i - 1:
            tmp2 = 0
        else:
            tmp2 = (tmp2 * (left + right + 1 - (i - 1))) // (i - 1)
        print ((tmp1 - tmp2) % MOD)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
MOD = 10 ** 9 + 7
n = int(input())
a = list(map(int, input().split()))
lst = [-1] * n

# O(N)
for i in range(n + 1):
    if lst[a[i] - 1] != -1:
        first = lst[a[i] - 1]
        second = i
        break
    lst[a[i] - 1] = i

# print (first, second)    
left = first
right = n - second
# print (left, right)

N = n + 1
tmp1 = 1
tmp2 = 1
# O(N ^ 2)
for i in range(1, n + 2):
    tmp1 = (tmp1 * (N + 1 - i))//i
    if i == 1:
        tmp2 = 1
    elif left + right < i - 1:
        tmp2 = 0
    else:
        tmp2 = (tmp2 * (left + right + 1 - (i - 1))) // (i - 1)
    print ((tmp1 - tmp2) % MOD)

Submission status: Time Limit Exceeded

Solution code:
#TLEする
MOD = 10 ** 9 + 7
n = int(input())
a = list(map(int, input().split()))
lst = [-1] * n

# O(N)
for i in range(n + 1):
    if lst[a[i] - 1] != -1:
        first = lst[a[i] - 1]
        second = i
        break
    lst[a[i] - 1] = i

# print (first, second)    
left = first
right = n - second
# print (left, right)

# O(N)
left_lst = [1] * (left + 1) 
for i in range(1, left + 1):
    left_lst[i] = (left_lst[i - 1] * (left + 1 - i)) // i
# print (left_lst)

# O(N)
right_lst = [1] * (right + 1)
for i in range(1, right + 1):
    right_lst[i] = (right_lst[i - 1] * (right + 1 - i)) // i
# print (right_lst)

def calc(i): #1を含めてトータルi個選ぶ
    count = 0
    #左側からl個、右側からr個選ぶ
    start = max((i - 1) - right, 0) #左側から最低限選ばないといけない個数
    for l in range(start, min(i, left + 1)):
        count += left_lst[l] * right_lst[i - 1 - l]
        count %= MOD
    return count

N = n + 1
tmp = 1
for i in range(1, n + 2):
    tmp = (tmp * (N + 1 - i))//i
    if left + right < i - 1:
        print (tmp % MOD)
        continue
    print ((tmp - calc(i)) % MOD)

Submission status: Time Limit Exceeded

Solution code:
MOD = 10 ** 9 + 7
n = int(input())
a = list(map(int, input().split()))
lst = [-1] * n
for i in range(n + 1):
    if lst[a[i] - 1] != -1:
        first = lst[a[i] - 1]
        second = i
        break
    lst[a[i] - 1] = i

# print (first, second)    
left = first
right = n - second
# print (left, right)

left_lst = [1] * (left + 1) 
for i in range(1, left + 1):
    left_lst[i] = (left_lst[i - 1] * (left + 1 - i)) // i
# print (left_lst)

right_lst = [1] * (right + 1)
for i in range(1, right + 1):
    right_lst[i] = (right_lst[i - 1] * (right + 1 - i)) // i
# print (right_lst)


def calc(i): #1を含めてトータルi個選ぶ
    if i == 1:
        return 1
    count = 0
    #左側からl個、右側からr個選ぶ
    start = max((i - 1) - right, 0) #左側から最低限選ばないといけない個数
    for l in range(start, min(i, left + 1)):
        count += left_lst[l] * right_lst[i - 1 - l]
    return count

N = n + 1
tmp = 1
for i in range(1, n + 2):
    tmp = (tmp * (N + 1 - i))//i
    if left + right < i - 1:
        print (tmp % MOD)
        continue
    print ((tmp - calc(i)) % MOD)

Submission status: Time Limit Exceeded

Solution code:
# 逆数 x^(-1)
def inv(x):
    global p
    res=1
    prod=x
    e=p-2
    while e>0:
        if e%2==1:
            res=(res*prod)%p
        prod=(prod*prod)%p
        e//=2
    return res

# 階乗 x!
def fact(x):
    if x<1:
        return 1
    global p
    res=1
    for i in range(2, x+1):
        res=(res*i)%p
    return res

# 組合せ nCr
def combi(n,r):
    if r<0 or r>n:
        return 0
    else:
        a=fact(n)
        b=inv(fact(r))
        c=inv(fact(n-r))
        return(((a*b)%p)*c)%p

def ans(n,k,l,r):
    global p
    res=0
    # 長さkの部分列全ての個数
    m1=combi(n+1,k)
    # うち，区別することができないもの組数
    m2=combi((l-1)+(n+1-r),k-1)
    
    return (m1-m2)%p

p=10**9+7
n=int(input())
a=list(map(int,input().split()))

d={}
for i,ai in enumerate(a):
    if ai not in d:
        d[ai]=i+1 # 1-initial
    else:
        l=d[ai];r=i+1
        break

for k in range(1,n+2):
    print(ans(n,k,l,r))

Submission status: Time Limit Exceeded

Solution code:
import collections
mod = 10**9+7
fac = [1]
caf = [1]
n=int(input())

def pow(n,p):
    res=1
    while p >0:
        if p%2==0:
            n = n**2 % mod
            p //= 2
        else:
            res = res * n % mod
            p -= 1
    return res % mod

for i in range(1,n+2):
    fac.append((fac[i-1]*i)%mod)
    caf.append(pow(fac[i],mod-2)%mod)

def ncr(n,r):
    if n < r: return 0
    return fac[n]*caf[r]*caf[n-r]

def main():
    global n
    a=list(map(int,input().split()))

    ca= collections.Counter(a)
    tyo= ca.most_common()[0][0]
    kaburi=[i for i, x in enumerate(a) if x == tyo]

    for i in range(1,n+2):
        print((ncr(n+1,i)-ncr(n+1-(kaburi[1]-kaburi[0]+1),i-1))%mod)

main()

Submission status: Time Limit Exceeded

Solution code:
import collections
mod = 10**9+7
n=int(input())
kaijou = []
kaijou.append(1)
for i in range(1,n+3):
    kaijou.append(kaijou[i-1]*i)

lcom = [[0 for _ in range(n+3)] for _ in range(n+3)]

def cmb(n, r):
    if n<r:return 0
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

def main():
    global n
    a=list(map(int,input().split()))

    ca= collections.Counter(a)
    tyo= ca.most_common()[0][0]
    kaburi=[i for i, x in enumerate(a) if x == tyo]

    for i in range(1,n+2):
        print((cmb(n+1,i)-cmb(n+1-(kaburi[1]-kaburi[0]+1),i-1))%mod)

main()

Submission status: Time Limit Exceeded

Solution code:
import collections
mod = 10**9+7
n=int(input())
kaijou = []
kaijou.append(1)
for i in range(1,n+3):
    kaijou.append(kaijou[i-1]*i)

lcom = [[0 for _ in range(n+3)] for _ in range(n+3)]

def conb(p,r):
    if lcom[p][r] == 0:
        lcom[p][r] = kaijou[p]//(kaijou[r]*kaijou[p-r])
    return lcom[p][r]

def tyoufuku(i,a,b):
    global n
    ret = 0
    if i == 1:
        return 1
    else:
        for j in range(i):
            if a < j or n-b <i-j-1:
                continue
            else:
                ret += conb(a,j)*conb(n-b,i-j-1)
        return ret


def main():
    global n
    a=list(map(int,input().split()))

    ca= collections.Counter(a)
    tyo= ca.most_common()[0][0]

    kaburi=[i for i, x in enumerate(a) if x == tyo]

    for i in range(1,n+2):
        print((conb(n+1,i)-tyoufuku(i,kaburi[0],kaburi[1]))%mod)

main()

Submission status: Time Limit Exceeded

Solution code:
import collections
mod = 10**9+7
n=int(input())
kaijou = []
kaijou.append(1)
for i in range(1,n+3):
    kaijou.append(kaijou[i-1]*i)


def conb(p,r):
    return kaijou[p]//(kaijou[r]*kaijou[p-r])

def tyoufuku(i,a,b):
    global n
    ret = 0
    if i == 1:
        return 1
    else:
        for j in range(i):
            if a < j or n-b <i-j-1:
                continue
            else:
                ret += conb(a,j)*conb(n-b,i-j-1)
        return ret


def main():
    global n
    a=list(map(int,input().split()))

    ca= collections.Counter(a)
    tyo= ca.most_common()[0][0]

    kaburi=[i for i, x in enumerate(a) if x == tyo]

    for i in range(1,n+2):
        print((conb(n+1,i)-tyoufuku(i,kaburi[0],kaburi[1]))%mod)

main()

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter, defaultdict
import sys
sys.setrecursionlimit(10 ** 5 + 10)
# input = sys.stdin.readline
from math import factorial
import heapq, bisect
import math
import itertools

import queue
from collections import deque


def comb(n, r, mod):
    if n < r:
        return 0
    ans = 1
    for i in range(max(r, n - r) + 1, n + 1):
        ans *= i
        ans %= mod
    for i in range(1, min(r, n - r) + 1):
        ans *= pow(i, mod - 2, mod)
        ans %= mod
    return ans


def main():
    num = int(input())
    data = list(map(int, input().split()))

    mod = 10 ** 9 + 7

    count_data = Counter(data)
    count_data = sorted(count_data.items(), key=lambda x: -x[1])
    two_num = count_data[0][0]

    flg = 0
    left, mid, right = 0, 0, 0

    for i in range(num + 1):
        if data[i] == two_num:
            flg += 1
        elif flg == 0:
            left += 1
        elif flg == 1:
            mid += 1
        else:
            right += 1


    for now_num in range(1, num + 2):
        ans = 0
        if now_num == 1:
            ans += num
        elif now_num == 2:
            ans += comb(num - 1, 2, mod)
            ans += 1
            ans += left + right + mid * 2
        else:
            ans += comb(num - 1, now_num, mod)
            # print('uu', ans)
            ans += comb(num - 1, now_num - 2, mod)
            # kari = comb(left + right, now_num - 2, mod) - comb(left, now_num - 2, mod) - comb(right, now_num - 2, mod)
            # ans -= kari
            # print('uu', ans)
            ans += comb(num - 1, now_num - 1, mod) * 2 - comb(left, now_num - 1, mod) - comb(right, now_num - 1, mod)
            kari = comb(left + right, now_num - 1, mod) - comb(left, now_num - 1, mod) - comb(right, now_num - 1, mod)
            # print(kari, 'jjjj')
            ans -= kari
            # print(comb(num - 1, now_num - 1, mod), comb(num - 1, now_num - 1, mod), comb(num - 1, now_num - 1, mod))
            # print('uu', ans)
        # print(ans, left, mid, right)
        ans %= mod
        print(ans)


if __name__ == '__main__':
    main()
    # test()

Submission status: Time Limit Exceeded

Solution code:
from math import factorial as f
from collections import Counter as co
n=int(input())
a=list(map(int,input().split()))
mod=10**9+7
d=co(a)
keys=[k for k,v in d.items() if v==2]
dbl=keys[0]
ll=[i for i,x in enumerate(a) if x==dbl]
b=ll[1]-ll[0]-1
m=n-1-b
def pf(a,b,p):
  if b==0: return 1
  if b%2==0:
    d=pf(a,b//2,p)
    return d*d%p
  if b%2==1:
    return (a*pf(a,b-1,p))%p
def comb(n,k,p):
  if n<0 or k<0 or n<k: return 0
  if n==0 or k==0: return 1
  a=f(n)%p
  b=f(k)%p
  c=f(n-k)%p
  return (a*pf(b,p-2,p)*pf(c,p-2,p))%p
for k in range(1,n+2):
  print(comb(n+1,k,mod)-comb(m,k-1,mod))

Submission status: Time Limit Exceeded

Solution code:
def combination_modp(n, r, p): # nCr modpを求める
    r = min(n-r, r)
    result = 1
    for i in range(n, n-r, -1):
        result *= i
        result %=p
    for i in range(1, r+1):
        result *= pow(i,p-2,p)
        result %= p
    return result

n = int(input())
a = list(map(int,input().split()))
search = [-1 for i in range(n)]
l,r = -1,-1
for i,x in enumerate(a):
    if search[x-1] == -1:
        search[x-1] = i
    else:
        l = search[x-1]
        r = i
#print(l,r)
p = 10**9 + 7
for i in range(1,n+2):
    if l+n-r+1 >= i:
        ans = combination_modp(n+1,i,p)-combination_modp(l+n-r,i-1,p)
    else:
        ans = combination_modp(n+1,i,p)
    print(ans%p)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
#ABC66 D

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def f(a, b):
    if b == 0: 
        return 1
    if b % 2 == 0:
        d = f(a, b // 2)
        return d * d % mod
    if b % 2 == 1:
        return (a * f(a, b - 1)) % mod


def comb(n,r):
    if n - r < 0:
        return 0
    return fact[n] * invfact[r] * invfact[n-r] % mod

n = I()
a = LI()
cnt = [0]*(n+1)
for i in range(n+1):
    if cnt[a[i]]:
        a = cnt[a[i]]
        b = i+1
        break
    else:
        cnt[a[i]] = i+1

fact = [1]*(n+2)
invfact = [1]*(n+2)
for i in range(1,n+2):
    fact[i] = i*fact[i-1]
    invfact[i] = invfact[i-1] * f(i,mod-2) % mod
    
for i in range(n+1):
    res = 0
    res = (res + comb(n+1,i+1)) % mod
    res = (res - comb((a-1)+(n+1-b),i)) % mod
    print(res)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
#ABC66 D

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def f(a, b):
    if b == 0: 
        return 1
    elif b % 2 == 0:
        d = f(a, b // 2)
        return d * d % mod
    else:
        return (a * f(a, b - 1)) % mod


def comb(n,r):
    if n - r < 0:
        return 0
    return fact[n] * invfact[r] * invfact[n-r] % mod

n = I()
a = LI()
c = list(Counter(a).items())
c.sort(key = itemgetter(1),reverse = True)
x = c[0][0]

fact = [1]*(n+2)
invfact = [1]*(n+2)
for i in range(1,n+2):
    fact[i] = i*fact[i-1]
    invfact[i] = invfact[i-1] * f(i,mod-2) % mod

lst = []
for i in range(n+1):
    if a[i] == x:
        lst.append(i+1)
a,b = lst[0],lst[1]
for i in range(n+1):
    res = 0
    res = (res + comb(n+1,i+1)) % mod
    res = (res - comb((a-1)+(n+1-b),i)) % mod
    print(res)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
#ABC66 D

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

def comb(n,r):
    if n - r < 0:
        return 0
    return fact[n]*invfact[r]*invfact[n-r] % mod
n = I()
a = LI()
c = list(Counter(a).items())
c.sort(key = itemgetter(1),reverse = True)
x = c[0][0]

fact = [1]*(n+2)
invfact = [1]*(n+2)
for i in range(1,n+2):
    fact[i] = i*fact[i-1]
    invfact[i] = invfact[i-1]*pow(i,mod-2,mod)

lst = []
for i in range(n+1):
    if a[i] == x:
        lst.append(i+1)
a,b = lst[0],lst[1]
for i in range(n+1):
    res = 0
    res = (res + comb(n+1,i+1)) % mod
    res = (res - comb((a-1)+(n+1-b),i)) % mod
    print(res)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
#ABC66 D

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

def comb(n,r):
    if n - r < 0:
        return 0
    return fact[n]*pow(fact[r],mod-2,mod)*pow(fact[n-r],mod-2,mod) % mod
n = I()
a = LI()
c = list(Counter(a).items())
c.sort(key = itemgetter(1),reverse = True)
x = c[0][0]
fact = [0]*(n+2)
fact[0] = 1
for i in range(1,n+2):
    fact[i] = i*fact[i-1]

lst = []
for i in range(n+1):
    if a[i] == x:
        lst.append(i+1)
a,b = lst[0],lst[1]
for i in range(n+1):
    res = 0
    res = (res + comb(n+1,i+1)) % mod
    res = (res - comb((a-1)+(n+1-b),i)) % mod
    print(res)