Submission #83920

#	Time	Username	Problem	Language	Result	Execution time	Memory
83920		RezwanArefin01	Asceticism (JOI18_asceticism)	C++17	100 / 100	25 ms	1808 KiB

asceticism

///usr/bin/g++ -O2 $0 -o ${0%.cpp} && echo "----------" && ./${0%.cpp}; exit;
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> ii; 

const int N = 1e5 + 10;
const int mod = 1e9 + 7;

int fact[N], inv[N]; 

inline int Pow(int a, int p) {
	int ret = 1; while(p) {
		if(p & 1) ret = (ll) ret * a % mod;
		a = (ll) a * a % mod;
		p >>= 1;
	} return ret;
}

int C(int n, int r) { 
    int ret = (ll) fact[n] * inv[r] % mod;
    return (ll) ret * inv[n - r] % mod; 
}

int main() {
    fact[0] = 1; 
    for(int i = 1; i < N; i++) 
        fact[i] = (ll) fact[i - 1] * i % mod; 
    inv[N - 1] = Pow(fact[N - 1], mod - 2); 
    for(int i = N - 2; i >= 0; i--) 
        inv[i] = (ll) inv[i + 1] * (i + 1) % mod;

    int n, k; scanf("%d %d", &n, &k); 

    int ans = 0; 
    for(int i = 0; i <= k; i++) {
        int add = C(n, i); 
        int x = Pow(k - i, n); 
        if(i <= k - 1) {
            x -= Pow(k - i - 1, n); 
            if(x < 0) x += mod; 
        }
        add = (ll) add * x % mod; 
        if(i & 1) ans -= add;
        else ans += add;
        if(ans >= mod) ans -= mod;
        if(ans < 0) ans += mod;
    }
    printf("%d\n", ans); 
}

Compilation message (stderr)

asceticism.cpp: In function 'int main()':
asceticism.cpp:34:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     int n, k; scanf("%d %d", &n, &k); 
               ~~~~~^~~~~~~~~~~~~~~~~

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