Submission #319304

#	Time	Username	Problem	Language	Result	Execution time	Memory
319304		mohamedsobhi777	Asceticism (JOI18_asceticism)	C++14	100 / 100	46 ms	492 KiB

asceticism

#include <bits/stdc++.h>

#pragma GCC optimize("-Ofast")
//#pragma GCC optimize("trapv")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse4.2,popcnt,abm,mmx,avx2,tune=native")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-funroll-loops")

#define I inline void
#define S struct
#define vi vector<int>
#define vii vector<pair<int, int>>
#define pii pair<int, int>
#define pll pair<ll, ll>

using namespace std;
using ll = long long;
using ld = long double;

const int N = 2e5 + 7, mod = 1e9 + 7;
const ll inf = 2e18;

// How interesting!

int n, m;

int faspow(int x, int y)
{
        if (!y)
                return 1;
        int ret = faspow(x, y / 2);
        ret = 1ll * ret * ret % mod;
        if (y & 1)
                ret = 1ll * ret * x % mod;
        return ret;
}

int eulerian(int n, int m)
{
        int ret = 0;
        int ncr = 1;
        for (int i = 0; i <= m; ++i)
        {
                int add = 1ll * ncr * faspow(m + 1 - i, n) % mod;
                ret = (ret + (i & 1 ? -add : add));
                ret = (ret % mod + mod) % mod;
                int mul = 1ll * (n + 1 - i) * faspow(i + 1, mod - 2) % mod;
                ncr = 1ll * ncr * mul % mod;
        }
        return ret;
}

int main()
{
        ios_base::sync_with_stdio(0);
        cin.tie(0);
        //freopen("in.in", "r", stdin);
        cin >> n >> m;
        m -- ; 
        cout << eulerian(n, m);
        return 0;
}

/*
        - bounds sir (segtree = 4N, eulerTour = 2N, ...)
        - a variable defined twice?
        - will overflow?
        - is it a good complexity?
        - don't mess up indices (0-indexed vs 1-indexed)
        - reset everything between testcases. 
*/

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