Участник:Kozlinskii/ADACAROT

Материал из DISCOPAL
Перейти к: навигация, поиск

https://www.spoj.com/problems/ADACAROT/ c++14(gcc 8.3)

#include <iostream>
#include <vector>
using namespace std;
const int module = 1000000007;
const int max_n = 200010;
 
int64_t power (int a, int deg) {
    a %= module;
    int64_t res = 1;
    for (int iter_deg = deg; iter_deg > 0; iter_deg >>= 1) {
        if (iter_deg & 1)
            res = (1LL * res * a) % module;
        a = (1LL * a * a) % module;
    }
    return res;
}
 
int64_t cases(int k, int m) {
    return 1LL * power(k, m-1) * power(m, k-1) % module;
}
 
int main()
{
    std::vector<int64_t> factorial(max_n, 0);
    factorial[0] = 1;
    for (int i=1; i < max_n; ++i) {
        factorial[i] = (1LL * factorial[i-1] * i) % module;
    }
 
    int n;
    while (cin >> n) {
        int64_t sum = 0;
        for (int k=0; k < n; ++k) {
            sum = (sum + cases(k, n-k)) % module;
        }
        cout << (sum * factorial[n]) % module << "\n";
    }
 
    return 0;
}