oj.uz

Submission #574382

# Submission time Handle Problem Language Result Execution time Memory
574382 2022-06-08T13:01:33 Z urosk NoM (RMI21_nom) C++14
100 / 100
 394 ms 117556 KB 
#define here cerr<<"===========================================\n"
#include <bits/stdc++.h>
#define ld double
#define ll long long
#define llinf 100000000000000000LL // 10^17
#define pb push_back
#define popb pop_back
#define fi first
#define sc second
#define endl '\n'
#define pll pair<ll,ll>
#define pld pair<ld,ld>
#define sz(a) (ll)(a.size())
#define all(a) a.begin(),a.end()
#define ceri(a,l,r) {for(ll i_ = l;i_<=r;i_++) cerr<<a[i_]<< " ";cerr<<endl;}
#define daj_mi_malo_vremena ios_base::sync_with_stdio(false);cerr.tie(0);cout.tie(0);cin.tie(0);

using namespace std;
#define mod 1000000007
#define maxn 4005
ll n,m;
ll fact[maxn];
ll add(ll x,ll y){
    x+=y;
    if(x<0){
        x%=mod;
        x+=mod;
    }else{
        if(x>=mod) x%=mod;
    }
    return x;
}
ll mul(ll a,ll b){
	ll ans = (a*b)%mod;
	if(ans<0) ans+=mod;
	return ans;
}
ll mul(vector<ll> v){
    if(sz(v)==1) return v[0];
    if(sz(v)==0) return 1LL;
    ll ans = 1;
    for(ll x : v) ans = mul(ans,x);
    return ans;
}
ll po(ll x,ll y){
    if(y==0) return 1LL;
    if(y==1) return x;
    ll ans = po(x,y/2);
    ans = mul(ans,ans);
    if(y&1) ans = mul(ans,x);
    return ans;
}
ll inv(ll x){return po(x,mod-2);}
ll bin[maxn][maxn];
ll ch(ll x,ll y){
    if(x<y) return 0;
    return bin[x][y];
}
ll f(ll i){
    if((i&1)) return 1;
    return -1;
}
ll dp[maxn][maxn];
ll rem[maxn];
int main(){
	daj_mi_malo_vremena
	for(ll i = 1;i<maxn;i++) bin[i][0] = bin[i][i] = 1;
	for(ll i = 1;i<maxn;i++){
        for(ll j = 1;j<i;j++){
            bin[i][j] = add(bin[i-1][j],bin[i-1][j-1]);
        }
	}
    fact[0] = 1;
    for(ll i = 1;i<=maxn-1;i++) fact[i] = mul(fact[i-1],i);
    cin >> n >> m;
    for(ll i = 1;i<=2*n;i++) rem[i%m]++;
    rem[m] = rem[0];
    dp[0][0] = 1;
    for(ll i = 1;i<=m;i++){
        ll ni = rem[i];
        for(ll j = 0;j<=n;j++){
            for(ll k = 0;2*k<=ni&&j>=k;k++){
                dp[i][j] = add(dp[i][j],mul({dp[i-1][j-k],ch(ni,k),ch(ni-k,k),fact[k]}));
            }
        }
    }
    ll ans = 0;
    for(ll i = 1;i<=n;i++) ans = add(ans,mul({ch(n,i),fact[2*n-2*i],dp[m][i],fact[i],f(i)}));
    ans = add(fact[2*n],-ans);
    cout<<ans<<endl;
	return 0;
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 78224 KB Output is correct
2 Correct 63 ms 78236 KB Output is correct
3 Correct 67 ms 78164 KB Output is correct
4 Correct 63 ms 78336 KB Output is correct
5 Correct 76 ms 78208 KB Output is correct
6 Correct 76 ms 78176 KB Output is correct
7 Correct 66 ms 78156 KB Output is correct
8 Correct 62 ms 78156 KB Output is correct
9 Correct 62 ms 78224 KB Output is correct
10 Correct 63 ms 78164 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 78224 KB Output is correct
2 Correct 63 ms 78236 KB Output is correct
3 Correct 67 ms 78164 KB Output is correct
4 Correct 63 ms 78336 KB Output is correct
5 Correct 76 ms 78208 KB Output is correct
6 Correct 76 ms 78176 KB Output is correct
7 Correct 66 ms 78156 KB Output is correct
8 Correct 62 ms 78156 KB Output is correct
9 Correct 62 ms 78224 KB Output is correct
10 Correct 63 ms 78164 KB Output is correct
11 Correct 69 ms 78500 KB Output is correct
12 Correct 65 ms 78392 KB Output is correct
13 Correct 64 ms 78236 KB Output is correct
14 Correct 77 ms 78300 KB Output is correct
15 Correct 66 ms 78532 KB Output is correct
16 Correct 70 ms 78188 KB Output is correct
17 Correct 63 ms 78316 KB Output is correct
18 Correct 65 ms 78460 KB Output is correct
19 Correct 64 ms 78240 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 78224 KB Output is correct
2 Correct 63 ms 78236 KB Output is correct
3 Correct 67 ms 78164 KB Output is correct
4 Correct 63 ms 78336 KB Output is correct
5 Correct 76 ms 78208 KB Output is correct
6 Correct 76 ms 78176 KB Output is correct
7 Correct 66 ms 78156 KB Output is correct
8 Correct 62 ms 78156 KB Output is correct
9 Correct 62 ms 78224 KB Output is correct
10 Correct 63 ms 78164 KB Output is correct
11 Correct 69 ms 78500 KB Output is correct
12 Correct 65 ms 78392 KB Output is correct
13 Correct 64 ms 78236 KB Output is correct
14 Correct 77 ms 78300 KB Output is correct
15 Correct 66 ms 78532 KB Output is correct
16 Correct 70 ms 78188 KB Output is correct
17 Correct 63 ms 78316 KB Output is correct
18 Correct 65 ms 78460 KB Output is correct
19 Correct 64 ms 78240 KB Output is correct
20 Correct 71 ms 78232 KB Output is correct
21 Correct 69 ms 78648 KB Output is correct
22 Correct 71 ms 79736 KB Output is correct
23 Correct 64 ms 78284 KB Output is correct
24 Correct 70 ms 79100 KB Output is correct
25 Correct 84 ms 79692 KB Output is correct
26 Correct 67 ms 78316 KB Output is correct
27 Correct 73 ms 80028 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 78224 KB Output is correct
2 Correct 63 ms 78236 KB Output is correct
3 Correct 67 ms 78164 KB Output is correct
4 Correct 63 ms 78336 KB Output is correct
5 Correct 76 ms 78208 KB Output is correct
6 Correct 76 ms 78176 KB Output is correct
7 Correct 66 ms 78156 KB Output is correct
8 Correct 62 ms 78156 KB Output is correct
9 Correct 62 ms 78224 KB Output is correct
10 Correct 63 ms 78164 KB Output is correct
11 Correct 69 ms 78500 KB Output is correct
12 Correct 65 ms 78392 KB Output is correct
13 Correct 64 ms 78236 KB Output is correct
14 Correct 77 ms 78300 KB Output is correct
15 Correct 66 ms 78532 KB Output is correct
16 Correct 70 ms 78188 KB Output is correct
17 Correct 63 ms 78316 KB Output is correct
18 Correct 65 ms 78460 KB Output is correct
19 Correct 64 ms 78240 KB Output is correct
20 Correct 71 ms 78232 KB Output is correct
21 Correct 69 ms 78648 KB Output is correct
22 Correct 71 ms 79736 KB Output is correct
23 Correct 64 ms 78284 KB Output is correct
24 Correct 70 ms 79100 KB Output is correct
25 Correct 84 ms 79692 KB Output is correct
26 Correct 67 ms 78316 KB Output is correct
27 Correct 73 ms 80028 KB Output is correct
28 Correct 79 ms 78356 KB Output is correct
29 Correct 92 ms 81172 KB Output is correct
30 Correct 96 ms 83480 KB Output is correct
31 Correct 84 ms 78256 KB Output is correct
32 Correct 97 ms 81508 KB Output is correct
33 Correct 101 ms 84388 KB Output is correct
34 Correct 131 ms 88184 KB Output is correct

Subtask #5
48.0 / 48.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 78224 KB Output is correct
2 Correct 63 ms 78236 KB Output is correct
3 Correct 67 ms 78164 KB Output is correct
4 Correct 63 ms 78336 KB Output is correct
5 Correct 76 ms 78208 KB Output is correct
6 Correct 76 ms 78176 KB Output is correct
7 Correct 66 ms 78156 KB Output is correct
8 Correct 62 ms 78156 KB Output is correct
9 Correct 62 ms 78224 KB Output is correct
10 Correct 63 ms 78164 KB Output is correct
11 Correct 69 ms 78500 KB Output is correct
12 Correct 65 ms 78392 KB Output is correct
13 Correct 64 ms 78236 KB Output is correct
14 Correct 77 ms 78300 KB Output is correct
15 Correct 66 ms 78532 KB Output is correct
16 Correct 70 ms 78188 KB Output is correct
17 Correct 63 ms 78316 KB Output is correct
18 Correct 65 ms 78460 KB Output is correct
19 Correct 64 ms 78240 KB Output is correct
20 Correct 71 ms 78232 KB Output is correct
21 Correct 69 ms 78648 KB Output is correct
22 Correct 71 ms 79736 KB Output is correct
23 Correct 64 ms 78284 KB Output is correct
24 Correct 70 ms 79100 KB Output is correct
25 Correct 84 ms 79692 KB Output is correct
26 Correct 67 ms 78316 KB Output is correct
27 Correct 73 ms 80028 KB Output is correct
28 Correct 79 ms 78356 KB Output is correct
29 Correct 92 ms 81172 KB Output is correct
30 Correct 96 ms 83480 KB Output is correct
31 Correct 84 ms 78256 KB Output is correct
32 Correct 97 ms 81508 KB Output is correct
33 Correct 101 ms 84388 KB Output is correct
34 Correct 131 ms 88184 KB Output is correct
35 Correct 169 ms 78580 KB Output is correct
36 Correct 325 ms 108548 KB Output is correct
37 Correct 200 ms 78528 KB Output is correct
38 Correct 230 ms 92108 KB Output is correct
39 Correct 276 ms 102756 KB Output is correct
40 Correct 394 ms 117556 KB Output is correct