Submission #83922

#	Time	Username	Problem	Language	Result	Execution time	Memory
83922		RezwanArefin01	Asceticism (JOI18_asceticism)	C++17	100 / 100	24 ms	1524 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; 
}

void add(int &a, int b) { a = a + b >= mod ? a + b - mod : a + b; }
void sub(int &a, int b) { a = a - b < 0 ? a - b + mod : a - b; }
int mul(int a, int b) { return (ll) a * b % mod; }

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

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

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

Compilation message (stderr)

asceticism.cpp: In function 'int main()':
asceticism.cpp:38: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