Submission #717237

#	Time	Username	Problem	Language	Result	Execution time	Memory
717237		fatemetmhr	Asceticism (JOI18_asceticism)	C++17	49 / 100	55 ms	39896 KiB

asceticism

// ~ Be Name Khoda ~

#include <bits/stdc++.h>
//#pragma GCC optimize ("Ofast")
//#pragma GCC target("avx2")
//#pragma GCC optimize("unroll-loops,O3")

using namespace std;

typedef long long ll;

#define pb       push_back
#define mp       make_pair
#define all(x)   x.begin(), x.end()
#define fi       first
#define se       second

const int maxn  =  3e3   + 10;
const int maxn5 =  3e3   + 10;
const int maxnt =  1.2e6 + 10;
const int maxn3 =  1e3   + 10;
const int mod   =  1e9   +  7;
const ll  inf   =  1e18;

int ent[maxn][maxn], pw[maxn][maxn];
int f[maxn];

inline void fix(int &a){
    if(a < 0)
        a += mod;
    if(a >= mod)
        a -= mod;
}

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(0);

    int n, k; cin >> n >> k;
    if(n > 3000)
        return 0;
    ent[0][0] = 1;
    for(int i = 1; i < maxn; i++){
        ent[i][0] = 1;
        for(int j = 1; j <= i; j++)
            fix(ent[i][j] = ent[i - 1][j] + ent[i - 1][j - 1]);
    }
    for(ll i = 0; i <= n; i++){
        pw[i][0] = 1;
        for(int j = 1; j < maxn; j++)
            pw[i][j] = pw[i][j - 1] * i % mod;
    }

    for(int i = 1; i <= k; i++) for(int j = 1; j <= i; j++)
        fix(f[i] += (ll(ent[i][j]) * pw[j][n] % mod) * (i % 2 == j % 2 ? 1 : -1));
    int ans = 0;
    for(int i = 1; i <= k; i++){
        fix(ans += (ll(f[i]) * ent[n - i][k - i] % mod) * (i % 2 == k % 2 ? 1 : -1));
        //cout << i << ' ' << f[i] << endl;
    }
    cout << ans << endl;
}

• Subtask 1: 4 / 4
• Subtask 2: 20 / 20
• Subtask 3: 25 / 25
• Subtask 4: 0 / 51