Submission #5,024

2023-04-09 22:07:47

cpp17

Accepted 100/100

458ms

68864 KiB

#include <iostream>
#include <vector>
using namespace std;
using ll = long long;

ll n, s, o, a, MOD = 1e9 + 7, ans = 1;
vector <vector <ll>> dp(2001, vector <ll>(2001, 0));
vector <vector <bool>> b(2001, vector <bool>(2001, false));

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> s >> o;
    dp[0][0] = 1;
    for (int i = 1; i <= n; i++) {
        dp[i][0] = (dp[i - 1][0] * i) % MOD;
        for (int j = 1; j <= i; j++) {
            dp[i][j] = (MOD + dp[i][j - 1] - dp[i - 1][j - 1]) % MOD;
        }
    }
    fill(b[0].begin(), b[0].end(), true);
    for (int i = 1; i <= s; i++) {
        for (int j = 0; j < o; j++) {
            cin >> a;
            b[i][a] = true;
        }
        a = 0;
        for (int j = 1; j <= n; j++) if (!b[i][j] && !b[i - 1][j]) a++;
        ans *= dp[n - o][a];
        ans %= MOD;
    }
    for (int i = 0; i < n - s; i++) {
        ans *= dp[n][n];
        ans %= MOD;
    }
    cout << ans;
}

	Sum	Test	Verdict	Time	Memory
subtask1	0/0
		1	Accepted	25ms	65780 KiB
		2	Accepted	24ms	66104 KiB
		3	Accepted	202ms	66056 KiB
subtask2	5/5
		4	Accepted	416ms	66400 KiB
		5	Accepted	439ms	66736 KiB
		6	Accepted	453ms	66612 KiB
		7	Accepted	446ms	66820 KiB
subtask3	9/9
		8	Accepted	28ms	67028 KiB
		9	Accepted	29ms	67376 KiB
		10	Accepted	437ms	67468 KiB
		11	Accepted	448ms	67684 KiB
subtask4	15/15
		12	Accepted	24ms	67888 KiB
		13	Accepted	28ms	67852 KiB
		14	Accepted	24ms	67852 KiB
		15	Accepted	28ms	67980 KiB
		16	Accepted	25ms	68068 KiB
		17	Accepted	24ms	68064 KiB
		18	Accepted	28ms	68064 KiB
		19	Accepted	25ms	68160 KiB
subtask5	16/16
		20	Accepted	24ms	68408 KiB
		21	Accepted	24ms	68376 KiB
		22	Accepted	446ms	68356 KiB
		23	Accepted	71ms	68276 KiB
		24	Accepted	193ms	68192 KiB
subtask6	25/25
		25	Accepted	27ms	68160 KiB
		26	Accepted	27ms	68080 KiB
		27	Accepted	34ms	68084 KiB
		28	Accepted	29ms	68076 KiB
		29	Accepted	27ms	68076 KiB
		30	Accepted	32ms	68080 KiB
		31	Accepted	27ms	68284 KiB
		32	Accepted	32ms	68368 KiB
subtask7	30/30
		33	Accepted	104ms	68384 KiB
		34	Accepted	96ms	68504 KiB
		35	Accepted	458ms	68500 KiB
		36	Accepted	75ms	68588 KiB
		37	Accepted	194ms	68504 KiB
		38	Accepted	326ms	68584 KiB
		39	Accepted	266ms	68708 KiB
		40	Accepted	87ms	68716 KiB
		41	Accepted	231ms	68724 KiB
		42	Accepted	344ms	68864 KiB