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:
import sys
from collections import Counter
from functools import lru_cache

import numpy as np

sys.setrecursionlimit(2147483647)
INF = float('inf')

MOD = 10 ** 9 + 7
N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))


def get_factorials(max, mod=None):
    """
    階乗 0!, 1!, 2!, ..., max!
    :param int max:
    :param int mod:
    :return:
    """
    ret = [1]
    n = 1
    if mod:
        for i in range(1, max + 1):
            n *= i
            n %= mod
            ret.append(n)
    else:
        for i in range(1, max + 1):
            n *= i
            ret.append(n)
    return ret


factorials = get_factorials(N + 1, MOD)


@lru_cache(maxsize=None)
def inv(a, mod):
    """
    a の逆元
    :param a:
    :return:
    """
    return pow(a, mod - 2, mod)


def ncr(n, r, mod=None):
    """
    scipy.misc.comb または scipy.special.comb と同じ
    組み合わせの数 nCr
    :param int n:
    :param int r:
    :param int mod: 3 以上の素数であること
    :rtype: int
    """
    if n < r:
        return 0
    r = min(n - r, r)
    return factorials[n] * inv(factorials[r], mod) * inv(factorials[n - r], mod) % mod


# どことどこが一緒？
A = np.array(A)
dup, _ = Counter(A).most_common(1)[0]
L, r = np.where(A == dup)[0]

# dup より端から i 個選ぶ組み合わせ
sides = [ncr(L + N - r, i, MOD) for i in range(N + 2)]

# 全部選んで選びすぎを引く
# dup を 1 つ選び、その他を dup より端から選ぶ組み合わせが重複する
ans = [(ncr(N + 1, k, MOD) - sides[k - 1]) % MOD for k in range(1, N + 2)]

print('\n'.join(map(str, ans)))

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import Counter
from functools import lru_cache

import numpy as np

sys.setrecursionlimit(2147483647)
INF = float('inf')

MOD = 10 ** 9 + 7
N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))


def get_factorials(max, mod=None):
    """
    階乗 0!, 1!, 2!, ..., max!
    :param int max:
    :param int mod:
    :return:
    """
    ret = [1]
    n = 1
    if mod:
        for i in range(1, max + 1):
            n *= i
            n %= mod
            ret.append(n)
    else:
        for i in range(1, max + 1):
            n *= i
            ret.append(n)
    return ret


factorials = get_factorials(N + 1, MOD)


# @lru_cache(maxsize=None)
def ncr(n, r, mod=None):
    """
    scipy.misc.comb または scipy.special.comb と同じ
    組み合わせの数 nCr
    :param int n:
    :param int r:
    :param int mod: 3 以上の素数であること
    :rtype: int
    """
    if n < r:
        return 0

    def inv(a):
        """
        a の逆元
        :param a:
        :return:
        """
        return pow(a, mod - 2, mod)

    if mod:
        return factorials[n] * inv(factorials[r]) * inv(factorials[n - r]) % mod
    else:
        return factorials[n] // factorials[r] // factorials[n - r]


# どことどこが一緒？
A = np.array(A)
dup, _ = Counter(A).most_common(1)[0]
L, r = np.where(A == dup)[0]

# dup より端から i 個選ぶ組み合わせ
sides = np.array([ncr(L + N - r, i, MOD) for i in range(N + 2)])

for k in range(1, N + 2):
    c = ncr(N + 1, k, MOD)
    # 選びすぎを引く
    # dup を 1 つ選び、その他は全部 dup より端から選ぶ組み合わせ
    c -= sides[k - 1]
    print(c % MOD)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import Counter
from functools import lru_cache

import numpy as np

sys.setrecursionlimit(2147483647)
INF = float('inf')

MOD = 10 ** 9 + 7
N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))


def get_factorials(max, mod=None):
    """
    階乗 0!, 1!, 2!, ..., max!
    :param int max:
    :param int mod:
    :return:
    """
    ret = [1]
    n = 1
    if mod:
        for i in range(1, max + 1):
            n *= i
            n %= mod
            ret.append(n)
    else:
        for i in range(1, max + 1):
            n *= i
            ret.append(n)
    return ret


factorials = get_factorials(N + 1, MOD)


@lru_cache(maxsize=None)
def ncr(n, r, mod=None):
    """
    scipy.misc.comb または scipy.special.comb と同じ
    組み合わせの数 nCr
    :param int n:
    :param int r:
    :param int mod: 3 以上の素数であること
    :rtype: int
    """
    if n < r:
        return 0

    def inv(a):
        """
        a の逆元
        :param a:
        :return:
        """
        return pow(a, mod - 2, mod)

    if mod:
        return factorials[n] * inv(factorials[r]) * inv(factorials[n - r]) % mod
    else:
        return factorials[n] // factorials[r] // factorials[n - r]


# どことどこが一緒？
A = np.array(A)
dup, _ = Counter(A).most_common(1)[0]
L, r = np.where(A == dup)[0]

for k in range(1, N + 2):
    c = ncr(N + 1, k, MOD)
    # 選びすぎを引く
    for i in range(k):
        c -= ncr(L, i, MOD) * ncr(N - r, k - i - 1, MOD)

    print(c % MOD)

    # if k == 1:
    #     # d
    #     c -= 1
    # elif k == 2:
    #     # xd
    #     c -= ncr(L, 1, MOD)
    #     # dx
    #     c -= ncr(N - r, 1, MOD)
    # elif k >= 3:
    #     # xxdxx
    #     for i in range(k):
    #         c -= ncr(L, i, MOD) * ncr(N - r, k - i - 1, MOD)
    # print(c % MOD)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
li =  [ int(it) -1 for it in input().split() ] 

import sys
sys.setrecursionlimit(10000000)

from functools import lru_cache
MOD = 1000000007
def egcd(a, b):
    (x, lastx) = (0, 1)
    (y, lasty) = (1, 0)
    while b != 0:
        q = a // b
        (a, b) = (b, a % b)
        (x, lastx) = (lastx - q * x, x)
        (y, lasty) = (lasty - q * y, y)
    return (lastx, lasty, a)
@lru_cache(maxsize=None)
def modinv(a):
    (inv, q, gcd_val) = egcd(a, MOD)
    return inv % MOD
@lru_cache(maxsize=None)
def factorial(k):
  if (k<=1):
    return 1
  return (factorial(k-1)*k)%MOD
@lru_cache(maxsize=None)
def combination(n,m):
  return (factorial(n)*modinv(factorial(m))*modinv(factorial(n-m)))%MOD

#print ( factorial(5),factorial(3) )
#print ( combination(5,3) )

import collections as col
c = col.Counter( li ).items()
a = [ it for it in c if it[1] == 2][0][0]
p1 = li.index(a)
p2 = li[p1+1:].index(a) + 1 + p1
#print ( p1 , p2 )
H = p1 + (N-p2)
#print ( H )

li=[]
for i in range(1,N+2):
  a =  (combination(N+1,i) - (combination(H,i-1)if (i-1)<=H else 0))%MOD
  li.append(a)
print ( "\n".join( map(str,li) ) )

Submission status: Time Limit Exceeded

Solution code:
import functools, collections, sys

big = 10 ** 9 + 7
sys.setrecursionlimit(big)

@functools.lru_cache()
def c(n, k):
    if n < k:
        return 0

    if n == 0 or k == 0 or n == k:
        return 1
    else:
        return (c(n - 1, k - 1) + c(n - 1, k)) % big

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

d = collections.defaultdict(list)
for i, v in enumerate(a):
    d[v].append(i)
    if len(d[v]) == 2:
        l, r = d[v]
        break

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

Submission status: Time Limit Exceeded

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

mod = int(1e9+7)
def powermod(p,n,mod):
  #if n==0: return 1
  if n==1: return p%mod
  else:    return powermod(p,n//2,mod)**2 * (p**(n%2)) %mod


memo={}
for i, a in enumerate(A):
  if a in memo:
    L = memo[a]
    C = i - memo[a] -1
    R = len(A) - i-1
    break
  else:
    memo[a] = i
    
#print(L,C,R)
_LR = [0]*(n+3)
_LCR = [0] * (n+3) # _LCR[k] = (L+C+R)C(k)
_k = [0] * (n+3)
_LR[0] = _LCR[0] = _k[0] = 1

LR = [0]*(n+2) #LR[k] = (L+R)C(k)
LR[0] = 1
#LDR = [0]*(n+2)
#LDDR = [0]*(n+2)

LCR = [0] * (n+2) # LCR[k] = _LCR[k] - LR[k]
#LDCR = [0] * (n+2) #最後に*2を忘れないこと
#LDCDR = [0] * (n+2)

for k in range(1,n+2):
  _LR[k] = (_LR[k-1] * (L+R+1-k)) %mod
  _LCR[k] = (_LCR[k-1] * (L+C+R+1-k))% mod
  _k[k] = (_k[k-1] * powermod(k, mod-2, mod)) %mod
  
  LR[k] = (_LR[k] * _k[k])%mod
#  LDR[k] = LR[k-1]
#  LDDR[k] = LDR[k-1]
  
  LCR[k] = (_LCR[k] * _k[k])%mod - LR[k]
#  LDCR[k] = LCR[k-1]
#  LDCDR[k] = LDCR[k-1]
  #print(LR, LCR)
  print((LR[k] + LR[k-1] + LR[k-2] + LCR[k] + 2*LCR[k-1] + LCR[k-2])%mod)
  
#print(LR)
#print(LDR)
#print(LDDR)
#print(_LCR)
#print(LCR)
#print(LDCR)
#print(LDCDR)

Submission status: Time Limit Exceeded

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

mod = int(1e9+7)
def powermod(p,n,mod):
  if n==0: return 1
  if n==1: return p%mod
  else:    return powermod(p,n//2,mod)**2 * (p**(n%2)) %mod


memo={}
for i, a in enumerate(A):
  if a in memo:
    L = memo[a]
    C = i - memo[a] -1
    R = len(A) - i-1
    break
  else:
    memo[a] = i
    
#print(L,C,R)
_LR = [0]*(n+3)
_LCR = [0] * (n+3) # _LCR[k] = (L+C+R)C(k)
_k = [0] * (n+3)
_LR[0] = _LCR[0] = _k[0] = 1

LR = [0]*(n+2) #LR[k] = (L+R)C(k)
LR[0] = 1
#LDR = [0]*(n+2)
#LDDR = [0]*(n+2)

LCR = [0] * (n+2) # LCR[k] = _LCR[k] - LR[k]
#LDCR = [0] * (n+2) #最後に*2を忘れないこと
#LDCDR = [0] * (n+2)

for k in range(1,n+2):
  _LR[k] = (_LR[k-1] * (L+R+1-k)) %mod
  _LCR[k] = (_LCR[k-1] * (L+C+R+1-k))% mod
  _k[k] = (_k[k-1] * powermod(k, mod-2, mod)) %mod
  
  LR[k] = (_LR[k] * _k[k])%mod
#  LDR[k] = LR[k-1]
#  LDDR[k] = LDR[k-1]
  
  LCR[k] = (_LCR[k] * _k[k] - LR[k])%mod
#  LDCR[k] = LCR[k-1]
#  LDCDR[k] = LDCR[k-1]
  #print(LR, LCR)
  print((LR[k] + LR[k-1] + LR[k-2] + LCR[k] + 2*LCR[k-1] + LCR[k-2])%mod)
  
#print(LR)
#print(LDR)
#print(LDDR)
#print(_LCR)
#print(LCR)
#print(LDCR)
#print(LDCDR)

Submission status: Time Limit Exceeded

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

mod = int(1e9+7)
def powermod(p,n,mod):
  if n==0: return 1
  if n==1: return p%mod
  else:    return powermod(p,n//2,mod)**2 * (p**(n%2)) %mod


memo={}
for i, a in enumerate(A):
  if a in memo:
    L = memo[a]
    C = i - memo[a] -1
    R = len(A) - i-1
    break
  else:
    memo[a] = i
    
#print(L,C,R)
_LR = [0]*(n+3)
_LCR = [0] * (n+3) # _LCR[k] = (L+C+R)C(k)
_k = [0] * (n+3)
_LR[0] = _LCR[0] = _k[0] = 1

LR = [0]*(n+2) #LR[k] = (L+R)C(k)
LR[0] = 1
#LDR = [0]*(n+2)
#LDDR = [0]*(n+2)

LCR = [0] * (n+2) # LCR[k] = _LCR[k] - LR[k]
#LDCR = [0] * (n+2) #最後に*2を忘れないこと
#LDCDR = [0] * (n+2)

for k in range(1,n+2):
  _LR[k] = _LR[k-1] * (L+R+1-k) %mod
  _LCR[k] = (_LCR[k-1] * (L+C+R+1-k))% mod
  _k[k] = _k[k-1] * powermod(k, mod-2, mod) %mod
  
  LR[k] = (_LR[k] * _k[k])%mod
#  LDR[k] = LR[k-1]
#  LDDR[k] = LDR[k-1]
  
  LCR[k] = (_LCR[k] * _k[k])%mod - LR[k]
#  LDCR[k] = LCR[k-1]
#  LDCDR[k] = LDCR[k-1]
  #print(LR, LCR)
  print((LR[k] + LR[k-1] + LR[k-2] + LCR[k] + 2*LCR[k-1] + LCR[k-2])%mod)
  
#print(LR)
#print(LDR)
#print(LDDR)
#print(_LCR)
#print(LCR)
#print(LDCR)
#print(LDCDR)

Submission status: Time Limit Exceeded

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

mod = int(1e9+7)
def mulmod(p,q,mod):
  return ((p%mod)*(q%mod))%mod

powerdict = {}
def powermod(p,n,mod):
  if (p,n) in powerdict:
    return powerdict[(p,n)]
  if n==0:
    powerdict[(p,n)] = 1
  if n==1:
    powerdict[(p,n)]=p%mod
  else:
    powerdict[(p,n)] = powermod(p,n//2,mod)**2 * (p**(n%2)) %mod
  return powerdict[(p,n)]

def dividemod(p,q,mod):
  # modは素数
  return mulmod(p, powermod(q,mod-2,mod), mod)

memo={}
for i, a in enumerate(A):
  if a in memo:
    L = memo[a]
    C = i - memo[a] -1
    R = len(A) - i-1
    break
  else:
    memo[a] = i
    
#print(L,C,R)
_LR = [1]*(n+2)
_LCR = [1] * (n+2) # _LCR[k] = (L+C+R)C(k)
_k = [1] * (n+2)

LR = [1]*(n+2) #LR[k] = (L+R)C(k)
LDR = [0]*(n+2)
LDDR = [0]*(n+2)

LCR = [0] * (n+2) # LCR[k] = _LCR[k] - LR[k]
LDCR = [0] * (n+2) #最後に*2を忘れないこと
LDCDR = [0] * (n+2)

for k in range(1,n+2):
  _LR[k] = _LR[k-1] * (L+R+1-k) %mod
  _LCR[k] = (_LCR[k-1] * (L+C+R+1-k))% mod
  _k[k] = _k[k-1] * powermod(k, mod-2, mod) %mod
  
  LR[k] = (_LR[k] * _k[k])%mod
  LDR[k] = LR[k-1]
  LDDR[k] = LDR[k-1]
  
  LCR[k] = (_LCR[k] * _k[k])%mod - LR[k]
  LDCR[k] = LCR[k-1]
  LDCDR[k] = LDCR[k-1]
  
  print((LR[k] + LDR[k] + LDDR[k] + LCR[k] + 2*LDCR[k] + LDCDR[k])%mod)
  
#print(LR)
#print(LDR)
#print(LDDR)
#print(_LCR)
#print(LCR)
#print(LDCR)
#print(LDCDR)

Submission status: Time Limit Exceeded

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

mod = int(1e9+7)
def mulmod(p,q,mod):
  return ((p%mod)*(q%mod))%mod

powerdict = {}
def powermod(p,n,mod):
  if (p,n) in powerdict:
    return powerdict[(p,n)]
  if n==0:
    powerdict[(p,n)] = 1
  if n==1:
    powerdict[(p,n)]=p%mod
  else:
    powerdict[(p,n)] = powermod(p,n//2,mod)**2 * (p**(n%2)) %mod
  return powerdict[(p,n)]

def dividemod(p,q,mod):
  # modは素数
  return mulmod(p, powermod(q,mod-2,mod), mod)

memo={}
for i, a in enumerate(A):
  if a in memo:
    L = memo[a]
    C = i - memo[a] -1
    R = len(A) - i-1
    break
  else:
    memo[a] = i
    
#print(L,C,R)

LR = [1]*(n+2) #LR[k] = (L+R)C(k)
LDR = [0]*(n+2)
LDDR = [0]*(n+2)

_LCR = [1] * (n+2) # _LCR[k] = (L+C+R)C(k)

LCR = [0] * (n+2) # LCR[k] = _LCR[k] - LR[k]
LDCR = [0] * (n+2) #最後に*2を忘れないこと
LDCDR = [0] * (n+2)

for k in range(1,n+2):
  LR[k] = (LR[k-1] * (L+R+1-k)) %mod * powermod(k,mod-2,mod)
  LDR[k] = LR[k-1]
  LDDR[k] = LDR[k-1]
  
  _LCR[k] = (_LCR[k-1] * (L+C+R+1-k))% mod * powermod(k,mod-2,mod)
  
  LCR[k] = _LCR[k] - LR[k]
  LDCR[k] = LCR[k-1]
  LDCDR[k] = LDCR[k-1]
  
  print((LR[k] + LDR[k] + LDDR[k] + LCR[k] + 2*LDCR[k] + LDCDR[k])%mod)
  
#print(LR)
#print(LDR)
#print(LDDR)
#print(_LCR)
#print(LCR)
#print(LDCR)
#print(LDCDR)

Submission status: Time Limit Exceeded

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

mod = int(1e9+7)
def mulmod(p,q,mod):
  return ((p%mod)*(q%mod))%mod
def powermod(p,n,mod):
  if n==0: return 1
  if n==1: return p%mod
  else:    return powermod(p,n//2,mod)**2 * (p**(n%2)) %mod
def dividemod(p,q,mod):
  # modは素数
  return mulmod(p, powermod(q,mod-2,mod), mod)

memo={}
for i, a in enumerate(A):
  if a in memo:
    L = memo[a]
    C = i - memo[a] -1
    R = len(A) - i-1
    break
  else:
    memo[a] = i
    
#print(L,C,R)

LR = [1]*(n+2) #LR[k] = (L+R)C(k)
LDR = [0]*(n+2)
LDDR = [0]*(n+2)

_LCR = [1] * (n+2) # _LCR[k] = (L+C+R)C(k)

LCR = [0] * (n+2) # LCR[k] = _LCR[k] - LR[k]
LDCR = [0] * (n+2) #最後に*2を忘れないこと
LDCDR = [0] * (n+2)

for k in range(1,n+2):
  LR[k] = LR[k-1] * (L+R+1-k) // k
  LDR[k] = LR[k-1]
  LDDR[k] = LDR[k-1]
  
  _LCR[k] = _LCR[k-1] * (L+C+R+1-k) // k
  
  LCR[k] = _LCR[k] - LR[k]
  LDCR[k] = LCR[k-1]
  LDCDR[k] = LDCR[k-1]
  
  print((LR[k] + LDR[k] + LDDR[k] + LCR[k] + 2*LDCR[k] + LDCDR[k])%mod)
  
#print(LR)
#print(LDR)
#print(LDDR)
#print(_LCR)
#print(LCR)
#print(LDCR)
#print(LDCDR)

Submission status: Time Limit Exceeded

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

mod = int(1e9+7)
def mulmod(p,q,mod):
  return ((p%mod)*(q%mod))%mod
def powermod(p,n,mod):
  if n==0: return 1
  if n==1: return p%mod
  else:    return powermod(p,n//2,mod)**2 * (p**(n%2)) %mod
def dividemod(p,q,mod):
  # modは素数
  return mulmod(p, powermod(q,mod-2,mod), mod)

memo={}
for i, a in enumerate(A):
  if a in memo:
    L = memo[a]
    C = i - memo[a] -1
    R = len(A) - i-1
    break
  else:
    memo[a] = i
    
#print(L,C,R)

LR = [1]*(n+2) #LR[k] = (L+R)C(k)
LDR = [0]*(n+2)
LDDR = [0]*(n+2)

_LCR = [1] * (n+2) # _LCR[k] = (L+C+R)C(k)

LCR = [0] * (n+2) # LCR[k] = _LCR[k] - LR[k]
LDCR = [0] * (n+2) #最後に*2を忘れないこと
LDCDR = [0] * (n+2)

for k in range(1,n+2):
  LR[k] = dividemod(LR[k-1] * (L+R+1-k),k,mod)
  LDR[k] = LR[k-1]
  LDDR[k] = LDR[k-1]
  
  _LCR[k] = dividemod(_LCR[k-1] * (L+C+R+1-k),k,mod)
  
  LCR[k] = _LCR[k] - LR[k]
  LDCR[k] = LCR[k-1]
  LDCDR[k] = LDCR[k-1]
  
  print((LR[k] + LDR[k] + LDDR[k] + LCR[k] + 2*LDCR[k] + LDCDR[k])%mod)
  
#print(LR)
#print(LDR)
#print(LDDR)
#print(_LCR)
#print(LCR)
#print(LDCR)
#print(LDCDR)

Submission status: Time Limit Exceeded

Solution code:
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math

mod = 10**9+7

n = int(input())
a = [int(i) for i in input().split()]


factorial = [1]

for i in range(1,n+2):
    tmp = factorial[-1]*i
    factorial.append(tmp)

def combinations_count(n,r):
    if n-r < 0:
        return 0
    return factorial[n]//(factorial[n-r]*factorial[r])

A = copy.deepcopy(a)
A.sort()
for i in range(n+1):
    if A[i] == A[i+1]:
        double = A[i]
        break

cnt = 0
for i in range(n+1):
    if a[i] == double:
        if cnt == 0:
            l = i+1
            cnt += 1
        else:
            r = i+1
# print(l,r)
for k in range(1,n+2):
    # print(n+1,k,l+n-r,k-1)
    ans = (combinations_count(n+1,k)-combinations_count((l+n-r),(k-1)))%mod
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math


n = int(input())
a = [int(i) for i in input().split()]

def combinations_count(n,r):
    if n-r < 0:
        return 0
    return (math.factorial(n) // (math.factorial(n - r) * math.factorial(r)))%(10**9+7)

A = copy.deepcopy(a)
A.sort()
for i in range(len(A)-1):
    if A[i] == A[i+1]:
        double = A[i]
        break

cnt = 0
for i in range(n+1):
    if a[i] == double:
        if cnt == 0:
            l = i+1
            cnt += 1
        else:
            r = i+1
# print(l,r)
for k in range(1,n+2):
    ans = combinations_count(n+1,k)-combinations_count((l+n-r),(k-1))
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = [int(item) for item in input().split()]

nCk = [0] * (n+2)
nCk[1] = n + 1
for i in range(2,n+2):
    nCk[i] = (nCk[i-1] * (n+1-i+1) // i)

index = [-1] * (n+1)
l, r = 0, 0
for i, c in enumerate(a):
    if index[c] == -1:
        index[c] = i
    else:
        l = index[c]
        r = i

nb = n-r+l
nb1Ck = [0] * (n + 2)
nb1Ck[0] = 1
nb1Ck[1] = nb 
for i in range(2, nb+2):
    nb1Ck[i] = (nb1Ck[i-1] * ((nb+1)-i) // i)

for i in range(1, n+2):
    print((nCk[i] - nb1Ck[i-1])%(10**9 + 7))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = [int(item) for item in input().split()]

nCk = [0] * (n+2)
for i in range(1,n+2):
    if i == 1:
        nCk[1] = n+1
    else:
        nCk[i] = (nCk[i-1] * (n+1-i+1) // i) # % (10**9 + 7)

index = [-1] * (n+1)
l, r = 0, 0
for i, c in enumerate(a):
    if index[c] == -1:
        index[c] = i
    else:
        l = index[c]
        r = i

nb1Ck = [0] * (n + 2)
nb1Ck[0] = 1
for i in range(1,(n-r+l)+2):
    if i == 1:
        nb1Ck[1] = n-r+l
    else:
        nb1Ck[i] = (nb1Ck[i-1] * ((n-r+l+1)-i) // i) # % (10**9 + 7)

for i in range(1, n+2):
    print((nCk[i] - nb1Ck[i-1])%(10**9 + 7))

Submission status: Time Limit Exceeded

Solution code:
from math import factorial
n = int(input())
a = [int(item) for item in input().split()]

def combination(n, r):
    if n-r < 0:
        return 0
    return factorial(n) // (factorial(n-r) * factorial(r))

index = [-1] * (n+1)
l, r = 0, 0
for i, c in enumerate(a):
    if index[c] == -1:
        index[c] = i
    else:
        l = index[c]
        r = i

for i in range(1, n+2):
    print((combination(n+1, i) - combination(n+1 - (r-l) - 1, i-1))%(10**9 + 7))

Submission status: Time Limit Exceeded

Solution code:
import sys
import string
from collections import Counter
mo=10**9+7
sys.setrecursionlimit(10000000)
alp=string.ascii_uppercase

n=int(input())
a=[int(i) for i in input().split()]
#print(len(a),a)
c=Counter(a)
db=c.most_common()[0][0]
#print(db)
fst=a.index(db)
lst=a.index(db,fst+1)
x=n+1-(lst-fst+1)
#print(fst,lst)

cn=[0]*(n+1+1)
cn[0]=1
cx=[0]*(x+1)
cx[0]=1
def com1(k):
    if k>n+1 or k<0:
        return 0
    if cn[k]!=0:
        return cn[k]
    cn[k]=(n+1-k+1)*cn[k-1]//k
    return cn[k]
    
def com2(k):
    if k>x or k<0:
        return 0
    if cx[k]!=0:
        return cx[k]
    cx[k]=(x-k+1)*cx[k-1]//k
    return cx[k]
    
for i in range(1,n+2):
    ans=com1(i)-com2(i-1)
    print(ans%mo)#,com1(i),com2(i-1))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int, input().split()))
used = set()
for i, ai in enumerate(a):
    if ai in used:
        r = i
        l = a.index(ai)
        break
    else:
        used.add(ai)
MOD = 10 ** 9 + 7
total = n + 1
x = l + n - r + 1
d = 1
print(n)
for k in range(1, n + 1):
    total = total * (n + 1 - k) // (k + 1)
    d = d * (x - k) // k
    print((total - d) % MOD)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int, input().split()))
used = []
for i, ai in enumerate(a):
    if ai in used:
        r = i
        l = a.index(ai)
        break
    else:
        used.append(ai)
x = 10 ** 9 + 7
total = n + 1
d = 1
print(n)
for k in range(1, n + 1):
    total = total * (n + 1 - k) // (k + 1)
    d = d * (l + n - r - k + 1) // k
    print((total - d) % x)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int, input().split()))
l, r = [i for i in range(n + 1) if a.count(a[i]) > 1]
x = 10 ** 9 + 7
total = n + 1
d = 1
print(n)
for k in range(1, n + 1):
    total = total * (n + 1 - k) // (k + 1)
    d = d * (l + n - r - k + 1) // k
    print((total - d) % x)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int, input().split()))
l, r = [i for i in range(n + 1) if a.count(a[i]) > 1]
x = 10 ** 9 + 7
total = n + 1
d = 1
print(n)
for k in range(1, n + 1):
    total = total * (n + 1 - k) // (k + 1)
    d = d * (l + n - r - k + 1) // k
    print((total - d) % x)

Submission status: Time Limit Exceeded

Solution code:
import sys
try:
    from scipy.special import comb
except ImportError:
    from scipy.misc import comb

def main():
    input = sys.stdin.readline
    N = int(input())
    A = list(map(int, input().split()))
    MOD = 10**9 + 7

    used = set()
    first = 0
    second = 0
    for i in range(N+1):
        if A[i] in used:
            second = i
            first = A.index(A[i])
        else:
            used.add(A[i])

    m = first + (N - second)
    for i in range(1, N+2):
        ans = comb(N+1, i, exact=True) - comb(m, i-1, exact=True)
        print(int(ans) % MOD)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
try:
    from scipy.special import comb
except:
    from scipy.misc import comb

def main():
    input = sys.stdin.readline
    N = int(input())
    A = list(map(int, input().split()))
    MOD = 10**9 + 7

    used = set()
    first = 0
    second = 0
    for i in range(N+1):
        if A[i] in used:
            second = i
            first = A.index(A[i])
        else:
            used.add(A[i])

    """
    factrial = [1] * (N+2)
    for k in range(1, N+2):
        factrial[k] = (factrial[k-1] * k) % MOD

    fact_inv = [1] * (N+2)
    fact_inv[N+1] = pow(factrial[N+1], MOD - 2, MOD)
    for k in range(N, -1, -1):
        fact_inv[k] = (fact_inv[k+1] * (k+1)) % MOD

    def comb(n, r, MOD):
        if n < 0 or r < 0 or n < r:
            return 0
        else:
            return (factrial[n] * fact_inv[r] * fact_inv[n-r]) % MOD
    """

    m = first + (N - second)
    for i in range(1, N+2):
        ans = comb(N+1, i, exact=True) - comb(m, i-1, exact=True)
        print(int(ans) % MOD)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from scipy.misc import comb

def main():
    input = sys.stdin.readline
    N = int(input())
    A = list(map(int, input().split()))
    MOD = 10**9 + 7

    used = set()
    first = 0
    second = 0
    for i in range(N+1):
        if A[i] in used:
            second = i
            first = A.index(A[i])
        else:
            used.add(A[i])

    m = first + (N - second)
    for i in range(1, N+2):
        ans = comb(N+1, i, exact=True) - comb(m, i-1, exact=True)
        print(int(ans) % MOD)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from math import factorial

def main():
    input = sys.stdin.readline
    N = int(input())
    A = list(map(int, input().split()))
    MOD = 10**9 + 7

    used = set()
    first = 0
    second = 0
    for i in range(N+1):
        if A[i] in used:
            second = i
            first = A.index(A[i])
        else:
            used.add(A[i])

    factrial = [1] * (N+2)
    for k in range(1, N+2):
        factrial[k] = (factrial[k-1] * k) % MOD

    fact_inv = [1] * (N+2)
    fact_inv[N+1] = pow(factrial[N+1], MOD - 2, MOD)
    for k in range(N, -1, -1):
        fact_inv[k] = (fact_inv[k+1] * (k+1)) % MOD

    def comb(n, r, MOD):
        if n < 0 or r < 0 or n < r:
            return 0
        else:
            return (factrial[n] * fact_inv[r] * fact_inv[n-r]) % MOD

    for i in range(1, N+2):
        ans = comb(N+1, i, MOD)
        for j in range(i):
            m_f = first
            r_f = j

            m_b = N - second
            r_b = i - (j + 1)

            ans -= comb(m_f, r_f, MOD) * comb(m_b, r_b, MOD)

        print(int(ans) % MOD)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from math import factorial

def comb(n, r):
    if n - r < r:
        r = n - r
    if r < 0:
        return 0
    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():
    input = sys.stdin.readline
    N = int(input())
    A = list(map(int, input().split()))
    MOD = 10**9 + 7

    used = set()
    first = 0
    second = 0
    for i in range(N+1):
        if A[i] in used:
            second = i
            first = A.index(A[i])
        else:
            used.add(A[i])

    for i in range(1, N+2):
        ans = comb(N+1, i)
        for j in range(i):
            m_f = first
            r_f = j

            m_b = N - second
            r_b = i - (j + 1)

            ans -= comb(m_f, r_f) * comb(m_b, r_b)

        print(int(ans) % MOD)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def _11(N: int, A: list)->list:
    MOD = 10**9 + 7

    d = {}
    l, r = 0, 0
    for i, a in enumerate(A):
        if a in d:
            l, r = d[a], N-i
        else:
            d[a] = i

    c1, c2 = [1]*(N+2), [1]*(N+2)
    for i in range(N+1):
        c1[i+1] = c1[i] * (N+1-i) // (i+1)
        c2[i+1] = c2[i] * (l+r-i) // (i+1)

    return [(c1[k+1]-c2[k]+MOD) % MOD for k in range(N+1)]


if __name__ == "__main__":
    N = int(input())
    A = [int(s) for s in input().split()]
    ans = _11(N, A)
    print('\n'.join(map(str, ans)))

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
A=list(map(int,input().split()))
idx=dict()
mod=10**9+7
for i in range(1+n):
    if A[i] in idx:
        x=idx[A[i]]
        y=i
        break
    idx[A[i]]=i
gawa=n-1-(y-x-1)
zentai=n-1
gawa_conb=[1]
for i in range(1,1+gawa):
    if i<1+gawa//2:
        gawa_conb.append(gawa_conb[-1]*(gawa-i+1)//i)
    else:
        gawa_conb.append(gawa_conb[gawa-i])
gawa_conb+=[0]*(zentai-gawa)
zentai_conb=[1]
for i in range(1,1+zentai):
    if i<1+zentai//2:
        zentai_conb.append(zentai_conb[-1]*(zentai-i+1)//i)
    else:
        zentai_conb.append((zentai_conb[zentai-i]))
if n>1:
    print((zentai_conb[1]+zentai_conb[0]*2-gawa_conb[0])%mod)
    for i in range(2,n):
        print((zentai_conb[i-2]+zentai_conb[i]+zentai_conb[i-1]*2-gawa_conb[i-1])%mod)
    print((zentai_conb[n-2]+zentai_conb[n-1]*2-gawa_conb[n-1])%mod)
    print((zentai_conb[n-1])%mod)
else:
    print(1)
    print(1)

Submission status: Time Limit Exceeded

Solution code:
mod = int(1e9) + 7


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


fact = [1] * int(1e5+1)
for i in range(1, int(1e5+1)):
    fact[i] = (i * fact[i-1]) % mod
inv = [1] * int(1e5+1)
for i in range(0, int(1e5+1)):
    inv[i] = power(fact[i], mod-2) % mod


def combination(n, r):
    return fact[n] * inv[r] * inv[n-r] % mod


def main():
    N = int(input())
    A = list(map(int, input().split()))
    idx = [-1] * (N+1)
    x = 0
    for i in range(N+1):
        if idx[A[i]] == -1:
            idx[A[i]] = i
        else:
            x = i - idx[A[i]]
    for i in range(1, N+2):
        ans = combination(N+1, i)
        if i <= (N+1-x):
            ans = (ans - combination(N+1-(x+1), i-1)) % mod
        print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import math
import collections

mod = 10 ** 9 + 7

def nCr(n, r):
    return (math.factorial(n) // (math.factorial(n - r) * math.factorial(r))) % mod

n = int(input())
a = list(map(int, input().split()))
w = collections.Counter(a).most_common(1)[0][0]
w_index = []
for i in range(n + 1):
    if a[i] == w:
        w_index.append(i)
for i in range(1, n + 2):
    if w_index[0] + n - w_index[1] >= i - 1:
        print((nCr(n + 1, i) % mod - nCr(w_index[0] + n - w_index[1], i - 1) % mod) % mod)
    else:
        print(nCr(n + 1, i) % mod)

Submission status: Time Limit Exceeded

Solution code:
import math
import collections


def nCr(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

mod = 10 ** 9 + 7
n = int(input())
a = list(map(int, input().split()))
w = collections.Counter(a).most_common(1)[0][0]
w_index = []
for i in range(n + 1):
    if a[i] == w:
        w_index.append(i)
for i in range(1, n + 2):
    if w_index[0] + n - w_index[1] >= i - 1:
        print((nCr(n + 1, i) % mod - nCr(w_index[0] + n - w_index[1], i - 1) % mod) % mod)
    else:
        print(nCr(n + 1, i) % mod)