Problem:


Score : 600 points

Problem Statement

There are N people, conveniently numbered 1 through N.
We want to divide them into some number of groups, under the following two conditions:

Every group contains between A and B people, inclusive.

Let F_i be the number of the groups containing exactly i people. Then, for all i, either F_i=0 or C≤F_i≤D holds.

Find the number of these ways to divide the people into groups.
Here, two ways to divide them into groups is considered different if and only if there exists two people such that they belong to the same group in exactly one of the two ways.
Since the number of these ways can be extremely large, print the count modulo 10^9+7.

Constraints

1≤N≤10^3

1≤A≤B≤N

1≤C≤D≤N

Input

The input is given from Standard Input in the following format:

N A B C D

Output

Print the number of ways to divide the people into groups under the conditions, modulo 10^9+7.

Sample Input 1

3 1 3 1 2

Sample Output 1

4

There are four ways to divide the people:

(1,2),(3)

(1,3),(2)

(2,3),(1)

(1,2,3)

The following way to divide the people does not count: (1),(2),(3). This is because it only satisfies the first condition and not the second.

Sample Input 2

7 2 3 1 3

Sample Output 2

105

The only ways to divide the people under the conditions are the ones where there are two groups of two people, and one group of three people.
There are 105 such ways.

Sample Input 3

1000 1 1000 1 1000

Sample Output 3

465231251

Sample Input 4

10 3 4 2 5

Sample Output 4

0

The answer can be 0.



Sample input:
3 1 3 1 2


Sample output:
4

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
from pprint import pprint

sys.setrecursionlimit(10 ** 7)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]




mod = 10 ** 9 + 7
n, a, b, c, d = LI()


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


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

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

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


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

inv2 = [0] * (n + 1)
for jj in range(1, n + 1):
    inv2[jj] = pow(jj, mod-2, mod)

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

dp = [0] * (n + 1)
dp[0] = 1

for k in range(a, b + 1):
    ndp = dp[:]
    for j in range(n + 1):
        loop = (n - j) // k + 1
        cc = 1
        if dp[j] == 0:
            continue

        for ci in range(c):
            cc = cc * comb(n-j-ci*k, k)
        for ci in range(c, min(d + 1, loop)):
            if j + ci * k > n: break
            ndp[j+ci*k] += dp[j] * cc * inv[ci] % mod
            ndp[j + ci * k] %= mod
            cc = cc * comb(n - j - ci * k, k)
    dp = ndp


print(dp[n])

Submission status: Time Limit Exceeded

Solution code:
def main():
    class combination():
        # 素数のmod取るときのみ　速い
        def __init__(self, n, mod):
            self.n = n
            self.mod = mod
            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):
            if r > n or n < 0 or r < 0:
                return 0
            return self.fac[n] * self.inv[n - r] * self.inv[r] % self.mod

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


    mod = 10 ** 9 + 7
    n, a, b, c, d = LI()
    com = combination(n, mod)

    dp = [0] * (n + 1)
    dp[0] = 1

    for k in range(a, b + 1):
        ndp = dp[:]
        for j in range(n + 1):
            loop = (n - j) // k + 1
            cc = 1
            if dp[j] == 0:
                continue
            for ci in range(c):
                cc = cc * com.comb(n-j-ci*k, k)
            for ci in range(c, min(d + 1, loop)):
                if j + ci * k > n: break
                ndp[j+ci*k] += dp[j] * cc * com.inv[ci] % mod
                ndp[j + ci * k] %= mod
                cc = cc * com.comb(n - j - ci * k, k)
        dp = ndp

    print(dp[n])
    return

import sys
def LI(): return list(map(int, sys.stdin.readline().split()))
mod = 10 ** 9 + 7

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
def LI(): return list(map(int, sys.stdin.readline().split()))


def main():
    class combination():
        # 素数のmod取るときのみ　速い
        def __init__(self, n, mod):
            self.n = n
            self.mod = mod
            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):
            if r > n or n < 0 or r < 0:
                return 0
            return self.fac[n] * self.inv[n - r] * self.inv[r] % self.mod

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


    mod = 10 ** 9 + 7
    n, a, b, c, d = LI()
    com = combination(n, mod)

    dp = [0] * (n + 1)
    dp[0] = 1

    for k in range(a, b + 1):
        ndp = dp[:]
        for j in range(n + 1):
            loop = (n - j) // k + 1
            cc = 1
            if dp[j] == 0:
                continue
            for ci in range(c):
                cc = cc * com.comb(n-j-ci*k, k)
            for ci in range(c, min(d + 1, loop)):
                if j + ci * k > n: break
                ndp[j+ci*k] += dp[j] * cc * com.inv[ci] % mod
                ndp[j + ci * k] %= mod
                cc = cc * com.comb(n - j - ci * k, k)
        dp = ndp

    print(dp[n])
    return


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
from pprint import pprint

sys.setrecursionlimit(10 ** 7)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]


def main():
    class combination():
        # 素数のmod取るときのみ　速い
        def __init__(self, n, mod):
            self.n = n
            self.mod = mod
            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):
            if r > n or n < 0 or r < 0:
                return 0
            return self.fac[n] * self.inv[n - r] * self.inv[r] % self.mod

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


    mod = 10 ** 9 + 7
    n, a, b, c, d = LI()
    com = combination(n, mod)

    dp = [0] * (n + 1)
    dp[0] = 1

    for k in range(a, b + 1):
        ndp = dp[:]
        for j in range(n + 1):
            loop = (n - j) // k + 1
            cc = 1
            if dp[j] == 0:
                continue
            for ci in range(c):
                cc = cc * com.comb(n-j-ci*k, k)
            for ci in range(c, min(d + 1, loop)):
                if j + ci * k > n: break
                ndp[j+ci*k] += dp[j] * cc * com.inv[ci] % mod
                ndp[j + ci * k] %= mod
                cc = cc * com.comb(n - j - ci * k, k)
        dp = ndp

    print(dp[n])
    return


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
from pprint import pprint

sys.setrecursionlimit(10 ** 7)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]



class combination():
    # 素数のmod取るときのみ　速い
    def __init__(self, n, mod):
        self.n = n
        self.mod = mod
        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):
        if r > n or n < 0 or r < 0:
            return 0
        return self.fac[n] * self.inv[n - r] * self.inv[r] % self.mod

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


mod = 10 ** 9 + 7
n, a, b, c, d = LI()
com = combination(n, mod)

dp = [0] * (n + 1)
dp[0] = 1

for k in range(a, b + 1):
    ndp = dp[:]
    for j in range(n + 1):
        loop = (n - j) // k + 1
        cc = 1
        if dp[j] == 0:
            continue
        for ci in range(c):
            cc = cc * com.comb(n-j-ci*k, k)
        for ci in range(c, min(d + 1, loop)):
            if j + ci * k > n: break
            ndp[j+ci*k] += dp[j] * cc * com.inv[ci] % mod
            ndp[j + ci * k] %= mod
            cc = cc * com.comb(n - j - ci * k, k)
    dp = ndp


print(dp[n])

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
from pprint import pprint

sys.setrecursionlimit(10 ** 7)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]



class combination():
    # 素数のmod取るときのみ　速い
    def __init__(self, n, mod):
        self.n = n
        self.mod = mod
        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):
        if r > n or n < 0 or r < 0:
            return 0
        return self.fac[n] * self.inv[n - r] * self.inv[r] % self.mod

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


mod = 10 ** 9 + 7
n, a, b, c, d = LI()
com = combination(n, mod)




dp = [0] * (n + 1)
dp[0] = 1

for k in range(a, b + 1):
    ndp = dp[:]
    for j in range(n + 1):
        loop = (n - j) // k + 1
        cc = 1
        if dp[j] == 0:
            continue
        for ci in range(c):
            cc = cc * com.comb(n-j-ci*k, k)
        for ci in range(c, min(d + 1, loop)):
            if j + ci * k > n: break
            ndp[j+ci*k] += dp[j] * cc * com.inv[ci] % mod
            ndp[j + ci * k] %= mod
            cc = cc * com.comb(n - j - ci * k, k)
    dp = ndp


print(dp[n])

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
from pprint import pprint

sys.setrecursionlimit(10 ** 7)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]



class combination():
    # 素数のmod取るときのみ　速い
    def __init__(self, n, mod):
        self.n = n
        self.mod = mod
        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):
        if r > n or n < 0 or r < 0:
            return 0
        return self.fac[n] * self.inv[n - r] * self.inv[r] % self.mod

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


mod = 10 ** 9 + 7
n, a, b, c, d = LI()
com = combination(n, mod)

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


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

inv2 = [0] * (n + 1)
for jj in range(1, n + 1):
    inv2[jj] = pow(jj, mod-2, mod)

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

dp = [0] * (n + 1)
dp[0] = 1

for k in range(a, b + 1):
    ndp = dp[:]
    for j in range(n + 1):
        loop = (n - j) // k + 1
        cc = 1
        if dp[j] == 0:
            continue

        for ci in range(c):
            cc = cc * comb(n-j-ci*k, k)
        for ci in range(c, min(d + 1, loop)):
            if j + ci * k > n: break
            ndp[j+ci*k] += dp[j] * cc * com.inv[ci] % mod
            ndp[j + ci * k] %= mod
            cc = cc * comb(n - j - ci * k, k)
    dp = ndp


print(dp[n])

Submission status: Time Limit Exceeded

Solution code:
N,A,B,C,D=map(int,input().split())
mod=10**9+7

factorial=[1]
for i in range(1,1001):
    factorial.append((factorial[-1]*i)%mod)

inverse=[pow(factorial[i],mod-2,mod) for i in range(1001)]

dp=[{i:0 for i in range(A-1,B+1)} for j in range(N+1)]

for i in range(A,B+1):
    dp[0][i]=1

dp[0][A-1]=1

for i in range(1,N+1):
    for j in range(A,B+1):
        dp[i][j]=dp[i][j-1]+sum(dp[i-k*j][j-1]*factorial[i]*pow(inverse[j],k,mod)*inverse[k]*inverse[i-j*k] for k in range(C,min(D,i//j)+1))
        dp[i][j]%=mod

print(dp[N][B])

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
N, A, B, C, D = map(int, input().split())
mod = 10 ** 9 + 7

class Factorial:
  def __init__(self, n, mod):
    self.f = [1]
    for i in range(1, n + 1):
      self.f.append(self.f[-1] * i % mod)
    self.i = [pow(self.f[-1], mod - 2, mod)]
    for i in range(1, n + 1)[: : -1]:
      self.i.append(self.i[-1] * i % mod)
    self.i.reverse()
  def factorial(self, i):
    return self.f[i]
  def ifactorial(self, i):
    return self.i[i]
  def combi(self, n, k):
    return self.f[n] * self.i[n - k] % mod * self.i[k] % mod

f = Factorial(N, mod)
dp = [0] * (N + 1)
dp[N] = 1
for x in range(A, B + 1):
  for i in range(N + 1):
    u = pow(f.ifactorial(x), C, mod)
    for y in range(C, D + 1):
      if i - x * y >= 0:
        dp[i - x * y] += dp[i] * u % mod * f.ifactorial(y) % mod
      u *= f.ifactorial(x)
      u %= mod
print(dp[0] * f.factorial(N) % mod)

Submission status: Time Limit Exceeded

Solution code:
class Combination:
    """階乗とその逆元のテーブルをO(N)で事前作成し、組み合わせの計算をO(1)で行う"""
    def __init__(self, n, MOD):
        self.fact = [1]
        for i in range(1, n + 1):
            self.fact.append(self.fact[-1] * i % MOD)
        self.inv_fact = [0] * (n + 1)
        self.inv_fact[n] = pow(self.fact[n], MOD - 2, MOD)
        for i in reversed(range(n)):
            self.inv_fact[i] = self.inv_fact[i + 1] * (i + 1) % MOD
        self.MOD = MOD

    def factorial(self, k):
        """k!を求める O(1)"""
        return self.fact[k]

    def inverse_factorial(self, k):
        """k!の逆元を求める O(1)"""
        return self.inv_fact[k]

    def permutation(self, k, r):
        """kPrを求める O(1)"""
        if k < r:
            return 0
        return (self.fact[k] * self.inv_fact[k - r]) % self.MOD

    def combination(self, k, r):
        """kCrを求める O(1)"""
        if k < r:
            return 0
        return (self.fact[k] * self.inv_fact[k - r] * self.inv_fact[r]) % self.MOD

    def combination2(self, k, r):
        """kCrを求める O(r) kが大きいが、r <= nを満たしているときに使用"""
        if k < r:
            return 0
        res = 1
        for l in range(r):
            res *= (k - l)
            res %= self.MOD
        return (res * self.inv_fact[r]) % self.MOD


n, a, b, c, d = map(int, input().split())
MOD = 10 ** 9 + 7
comb = Combination(10 ** 5, MOD)

dp = [[0] * (n + 1) for i in range(b - a + 2)]
dp[0][0] = 1

for i in range(b - a + 1):
    per_g = i + a
    for j in range(0, n + 1):
        dp[i + 1][j] = dp[i][j]
        for cnt_g in range(c, d + 1):
            if j - cnt_g * per_g < 0:
                break
            p = comb.factorial(per_g) ** cnt_g
            dp[i + 1][j] += dp[i][j - cnt_g * per_g] * comb.combination(j, cnt_g * per_g)\
                            * comb.factorial(cnt_g * per_g) * (pow(comb.inverse_factorial(per_g), cnt_g, MOD))\
                            * comb.inverse_factorial(cnt_g)
            dp[i + 1][j] %= MOD
print(dp[-1][-1])

Submission status: Time Limit Exceeded

Solution code:
class Combination:
    """階乗とその逆元のテーブルをO(N)で事前作成し、組み合わせの計算をO(1)で行う"""
    def __init__(self, n, MOD):
        self.fact = [1]
        for i in range(1, n + 1):
            self.fact.append(self.fact[-1] * i % MOD)
        self.inv_fact = [0] * (n + 1)
        self.inv_fact[n] = pow(self.fact[n], MOD - 2, MOD)
        for i in reversed(range(n)):
            self.inv_fact[i] = self.inv_fact[i + 1] * (i + 1) % MOD
        self.MOD = MOD

    def factorial(self, k):
        """k!を求める O(1)"""
        return self.fact[k]

    def inverse_factorial(self, k):
        """k!の逆元を求める O(1)"""
        return self.inv_fact[k]

    def permutation(self, k, r):
        """kPrを求める O(1)"""
        if k < r:
            return 0
        return (self.fact[k] * self.inv_fact[k - r]) % self.MOD

    def combination(self, k, r):
        """kCrを求める O(1)"""
        if k < r:
            return 0
        return (self.fact[k] * self.inv_fact[k - r] * self.inv_fact[r]) % self.MOD

    def combination2(self, k, r):
        """kCrを求める O(r) kが大きいが、r <= nを満たしているときに使用"""
        if k < r:
            return 0
        res = 1
        for l in range(r):
            res *= (k - l)
            res %= self.MOD
        return (res * self.inv_fact[r]) % self.MOD


n, a, b, c, d = map(int, input().split())
MOD = 10 ** 9 + 7
comb = Combination(10 ** 5, MOD)
# dp[i][j] := i番目のグループ(a~b)まで見たとき、j人がグループ分けされるときの通り数
dp = [[0] * (n + 1) for i in range(b - a + 2)]
dp[0][0] = 1

for i in range(b - a + 1):
    per_g = i + a
    for j in range(0, n + 1):
        dp[i + 1][j] = dp[i][j]
        for cnt_g in range(c, d + 1):
            if j - cnt_g * per_g >= 0:
                p = comb.factorial(per_g) ** cnt_g
                dp[i + 1][j] += dp[i][j - cnt_g * per_g] * comb.combination(j, cnt_g * per_g)\
                                * comb.factorial(cnt_g * per_g) * (comb.inverse_factorial(per_g) ** cnt_g)\
                                * comb.inverse_factorial(cnt_g)
                dp[i + 1][j] %= MOD
print(dp[-1][-1])

Submission status: Time Limit Exceeded

Solution code:
def main():
    mod = 10**9+7
    inv_n = [0]*1001
    nCr = [[1]*(i+1) for i in range(1001)]
    for i in range(1001):
        inv_n[i] = pow(i, mod-2, mod)
    for i in range(2, 1001):
        for j in range(1, i):
            nCr[i][j] = (nCr[i-1][j-1]+nCr[i-1][j]) % mod
    n, a, b, c, d = map(int, input().split())
    f = [[[0]*(N//A-c+1) for A in range(a, b+1)] for N in range(1, n+1)]
    for N in range(1, n+1):
        for A in range(a, min(N//c, b)+1):
            temp = 1
            for C in range(1, c):
                temp = temp*nCr[N-(C-1)*A][A]*inv_n[C] % mod
            for C in range(c, min(d, N//A)+1):
                temp = temp*nCr[N-(C-1)*A][A]*inv_n[C] % mod
                f[N-1][A-a][C-c] = temp

    dp = [0]*(n+1)
    dp[0] = 1

    for A in range(b, a-1, -1):
        dp2 = [i for i in dp]
        for i in range(n-c*A+1):
            e = dp[i]
            if e:
                for C in range(c, min(d, (n-i)//A)+1):
                    dp2[i+C*A] = (dp2[i+C*A]+f[n-i-1][A-a][C-c]*e) % mod
        dp = dp2
    print(dp[-1])


main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    mod = 10**9+7
    inv_n = [0]*1001
    nCr = [[0]*(i+1) for i in range(1001)]
    for i in range(1001):
        inv_n[i] = pow(i, mod-2, mod)
    for i in range(1001):
        nCr[i][0] = 1
        nCr[i][i] = 1
    for i in range(2, 1001):
        for j in range(1, i):
            nCr[i][j] = (nCr[i-1][j-1]+nCr[i-1][j]) % mod
    n, a, b, c, d = map(int, input().split())
    f = [[[0]*(N//A-c+1) for A in range(a, b+1)] for N in range(1, n+1)]
    for N in range(1, n+1):
        for A in range(a, min(N//c, b)+1):
            temp = 1
            for C in range(1, c):
                temp = temp*nCr[N-(C-1)*A][A]*inv_n[C] % mod
            for C in range(c, min(d, N//A)+1):
                temp = temp*nCr[N-(C-1)*A][A]*inv_n[C] % mod
                f[N-1][A-a][C-c] = temp

    dp = [0]*(n+1)
    dp[0] = 1

    for A in range(a, b+1):
        dp2 = [i for i in dp]
        for C in range(c, d+1):
            for i in range(n-C*A+1):
                dp2[i+C*A] = (dp2[i+C*A]+f[n-i-1][A-a][C-c]*dp[i]) % mod
        dp = dp2
    print(dp[-1])


main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    mod = 10**9+7
    inv_n = [0]*1001
    nCr = [[0]*(i+1) for i in range(1001)]
    for i in range(1001):
        inv_n[i] = pow(i, mod-2, mod)
    for i in range(1001):
        nCr[i][0] = 1
        nCr[i][i] = 1
    for i in range(2, 1001):
        for j in range(1, i):
            nCr[i][j] = (nCr[i-1][j-1]+nCr[i-1][j]) % mod

    n, a, b, c, d = map(int, input().split())
    f = dict()
    for N in range(1, n+1):
        for A in range(a, b+1):
            if N-c*A < 0:
                break
            temp = 1
            for C in range(1, c):
                temp = temp*nCr[N-(C-1)*A][A]*inv_n[C] % mod
            for C in range(c, d+1):
                if N-C*A < 0:
                    break
                temp = temp*nCr[N-(C-1)*A][A]*inv_n[C] % mod
                f[(N, A, C)] = temp

    dp = [0]*(n+1)
    dp[0] = 1

    for A in range(a, b+1):
        dp2 = [i for i in dp]
        for C in range(c, d+1):
            for i in range(n):
                N = n-i
                if i+C*A > n:
                    break
                dp2[i+C*A] = (dp2[i+C*A]+f[(N, A, C)]*dp[i]) % mod
        dp = dp2
    print(dp[-1])


main()

Submission status: Time Limit Exceeded

Solution code:

"""
Writer: SPD_9X2
https://atcoder.jp/contests/arc067/tasks/arc067_c

dpだろうなぁ
O(N^2)に頑張って抑えなくてはいけない

dp[i][x] = i人のグループの数まで決めて、合計x人いるときの通り数
とすると、各iについて各xから移行するのは高々n個→ N^3？

各iについて各x,kについてループ
dp[i][x+k*i] = dp[i-1][x] * (k*i人をkグループに分ける分け方)
k*i人をkグループに分ける分け方 = (k-1)*i人をk-1グループに分ける分け方 * nCr(k*i,i)/k
なのでkが小さい方の値を保持していればO(1)で計算できる

等比級数なので、iの部分はlogになるはず
O(N^2logN) → 10^7くらい　厳しめ…？
"""

def modfac(n, MOD):
 
    f = 1
    factorials = [1]
    for m in range(1, n + 1):
        f *= m
        f %= MOD
        factorials.append(f)
    inv = pow(f, MOD - 2, MOD)
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv *= m
        inv %= MOD
        invs[m - 1] = inv
    return factorials, invs


def modnCr(n,r,mod,fac,inv): 
    return fac[n] * inv[n-r] * inv[r] % mod

def inverse(a,mod): #aのmodを法にした逆元を返す
    return pow(a,mod-2,mod)


N,A,B,C,D = map(int,input().split())

mod = 10**9+7
fac,inv = modfac(10**6,mod)
dp = [0] * (N+1)
dp[0] = 1

for i in range(A,B+1):
    
    div = 1
    ndp = []
    for j in dp:
        ndp.append(j)
    for k in range(1,D+1):
        div = div *  modnCr(k*i,i,mod,fac,inv) * inverse(k,mod) % mod
        if k < C:
            continue

        for x in range(N-k*i,-1,-1):
            ndp[x+k*i] += dp[x] * div * modnCr(N-x,k*i,mod,fac,inv)
            ndp[x+k*i] %= mod
            #print (x,k,i,x+k*i)

    dp = ndp
    #print (i,dp)
print (dp[-1])

Submission status: Time Limit Exceeded

Solution code:
MAX = 10**6+100
MOD = 10**9+7
fact = [0]*MAX #fact[i]: i!
inv = [0]*MAX #inv[i]: iの逆元
finv = [0]*MAX #finv[i]: i!の逆元
fact[0] = 1
fact[1] = 1
finv[0] = 1
finv[1] = 1
inv[1] = 1
    
for i in range(2, MAX):
    fact[i] = fact[i-1]*i%MOD
    inv[i] = MOD-inv[MOD%i]*(MOD//i)%MOD
    finv[i] = finv[i-1]*inv[i]%MOD

def Com(n, r):
    if n<r:
        return 0
    if n<0 or r<0:
        return 0
    return fact[n]*(finv[r]*finv[n-r]%MOD)%MOD

N, A, B, C, D = map(int, input().split())
dp = [[0]*(N+1) for _ in range(B-A+2)]
dp[0][0] = 1

for i in range(B-A+1):
    for j in range(N+1):
        dp[i+1][j] += dp[i][j]
        dp[i+1][j] %= MOD
        
        for k in range(C, D+1):
            if j+(i+A)*k>N:
                break
            
            t = pow(pow(fact[i+A], k, MOD), MOD-2, MOD)*finv[k]
            dp[i+1][j+(i+A)*k] += Com(N-j, (i+A)*k)*fact[(i+A)*k]*t*dp[i][j]
            dp[i+1][j+(i+A)*k] %= MOD

print(dp[B-A+1][N])

Submission status: Time Limit Exceeded

Solution code:
import sys

def MI(): return map(int, sys.stdin.readline().split())

md = 10 ** 9 + 7

n_max = 1005
fac = [1]
for i in range(1, n_max + 1): fac.append(fac[-1] * i % md)
ifac = [1] * (n_max + 1)
ifac[n_max] = pow(fac[n_max], md - 2, md)
for i in range(n_max - 1, 1, -1): ifac[i] = ifac[i + 1] * (i + 1) % md

def main():
    n, a, b, c, d = MI()
    dp = [0] * (n + 1)
    # dp[j]...i番目の人数の班まで決めて全体でj人が決まったときの場合の数
    dp[0] = 1
    for p in range(a, b + 1):
        for j in range(n, -1, -1):
            dp[j] += sum(dp[j - p * g] * fac[n - j + p * g] * ifac[n - j] * ifac[g] * pow(ifac[p], g, md) for g in
                         range(c, min(j // p, d) + 1))
            dp[j] %= md
    print(dp[n])

main()

Submission status: Time Limit Exceeded

Solution code:
import sys

def MI(): return map(int, sys.stdin.readline().split())

md = 10 ** 9 + 7

n_max = 1005
fac = [1]
for i in range(1, n_max + 1): fac.append(fac[-1] * i % md)
ifac = [1] * (n_max + 1)
ifac[n_max] = pow(fac[n_max], md - 2, md)
for i in range(n_max - 1, 1, -1): ifac[i] = ifac[i + 1] * (i + 1) % md

def main():
    n, a, b, c, d = MI()
    pn = b - a + 1  # 班人数の種類数
    dp = [[0] * (n + 1) for _ in range(pn + 1)]
    # dp[i][j]...i番目の人数の班まで決めて全体でj人が決まったときの場合の数
    dp[0][0] = 1
    ps = 0
    for i in range(pn):
        p = i + a  # 班人数
        lim = n - (p + b) * (b - p + 1) * d // 2
        for j in range(max(lim, 0), min(n, ps * d) + 1):
            pre = dp[i][j]
            if pre == 0: continue
            dp[i + 1][j] += pre
            dp[i + 1][j] %= md
            r = n - j  # 残りの人数
            for g in range(c, d + 1):
                if j + p * g > n: break
                dp[i + 1][j + p * g] += pre * fac[r] * ifac[r - p * g] * ifac[g] * pow(ifac[p],g,md)
                dp[i + 1][j + p * g] %= md
        ps += p
    print(dp[pn][n])

main()