CSES - Datatähti 2025 alku - Results
Submission details
Task:Kortit II
Sender:AH
Submission time:2024-10-31 10:32:40 +0200
Language:C++ (C++20)
Status:READY
Result:34
Feedback
groupverdictscore
#1ACCEPTED3
#2ACCEPTED5
#3ACCEPTED26
#40
#50
Test results
testverdicttimegroup
#1ACCEPTED0.00 s1, 2, 3, 4, 5details
#2ACCEPTED0.00 s2, 3, 4, 5details
#3ACCEPTED0.01 s3, 4, 5details
#40.03 s4, 5details
#5--5details
#6--5details

Code

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef vector<int> vi;

#define F first
#define S second
#define PB push_back
#define MP make_pair
#define FOR(i,a,b) for (ll i = a; i < b; i++)

ll mod=1e9+7;


ll fac(ll n) {

    ll f=1;
    FOR(i,1,n+1) {
        f = (f*i)%mod;
    }
    return f;
}

ll bin(ll n, ll k) {
    if (k > n)
        return 0;
    if (k==0) {
        return 1;
    }

    ll c = n;
    for (ll i = 1; i < k; i++)
    {
        c *= n - i;
        c /= i + 1;
    }
    return c;
}

vector<vector<ll>> im(ll n, ll r) {
    return vector<vector<ll>>(n + 1, vector<ll>(r + 1, -1));
}

ll h(ll n, ll r, vector<vector<ll>> &m) {
    if (n == 0 && r == 0) {
        return 1;
    }
    if (n < 0 || r < 0) {
        return 0;
    }
    if (r > n) {
        return 0;
    }

    if (m[n][r] != -1) {
        return m[n][r];
    }

    m[n][r] = (r%mod * h(n - 1, r, m)%mod + (n - r)%mod * h(n - 1, r - 1, m)%mod + (n - 1)%mod * h(n - 2, r - 1, m)%mod)%mod;

    return m[n][r]%mod;
}

void f() {
    ll n, a, b, t, tm, jm, vm, r;
    cin >> n >> a >> b;
    t = n-a-b;
    if (t<0) {
        cout << 0 << "\n";
        return;
    }
    tm = bin(n, t);
    jm = fac(n);
    vector<vector<ll>> m = im(n-t, a);
    vm = h(n-t, a, m);
    r=((tm%mod*jm%mod)%mod*vm%mod)%(mod);
    cout << r << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    FOR(i,0,t) {
        f();
    }
}

Test details

Test 1

Group: 1, 2, 3, 4, 5

Verdict: ACCEPTED

input
54
4 4 0
3 1 3
3 2 2
4 0 4
...

correct output
0
0
0
0
0
...

user output
0
0
0
0
0
...

Test 2

Group: 2, 3, 4, 5

Verdict: ACCEPTED

input
284
6 1 0
5 0 2
7 1 5
7 7 5
...

correct output
0
0
35280
0
36720
...

user output
0
0
35280
0
36720
...

Test 3

Group: 3, 4, 5

Verdict: ACCEPTED

input
841
19 3 12
19 19 13
19 7 13
20 11 15
...

correct output
40291066
0
0
0
0
...

user output
40291066
0
0
0
0
...

Test 4

Group: 4, 5

Verdict:

input
1000
15 12 6
7 1 6
44 4 26
6 6 5
...

correct output
0
5040
494558320
0
340694548
...

user output
0
5040
494558320
0
340694548
...

Test 5

Group: 5

Verdict:

input
1000
892 638 599
966 429 655
1353 576 1140
1403 381 910
...

correct output
0
0
0
249098285
0
...

user output
(empty)

Test 6

Group: 5

Verdict:

input
1000
2000 1107 508
2000 1372 249
2000 588 65
2000 1739 78
...

correct output
750840601
678722180
744501884
159164549
868115056
...

user output
(empty)