結果
問題 | No.823 Many Shifts Easy |
ユーザー |
|
提出日時 | 2019-04-26 23:09:17 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 10,440 bytes |
コンパイル時間 | 2,135 ms |
コンパイル使用メモリ | 199,300 KB |
最終ジャッジ日時 | 2025-01-07 03:14:53 |
ジャッジサーバーID (参考情報) |
judge4 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 7 WA * 3 |
ソースコード
#include <bits/stdc++.h>#pragma GCC diagnostic ignored "-Wsign-compare"#pragma GCC diagnostic ignored "-Wsign-conversion"#define NDEBUG#define SHOW(...) static_cast<void>(0)//!===========================================================!////! dP dP dP !////! 88 88 88 !////! 88aaaaa88a .d8888b. .d8888b. .d888b88 .d8888b. 88d888b. !////! 88 88 88ooood8 88' '88 88' '88 88ooood8 88' '88 !////! 88 88 88. ... 88. .88 88. .88 88. ... 88 !////! dP dP '88888P' '88888P8 '88888P8 '88888P' dP !////!===========================================================!//using ld = long double;using uint = unsigned int;using ll = long long;using ull = unsigned long long;constexpr unsigned int MOD = 1000000007;template <typename T>constexpr T INF = std::numeric_limits<T>::max() / 4;template <typename F>constexpr F PI = static_cast<F>(3.1415926535897932385);std::mt19937 mt{std::random_device{}()};template <typename T>bool chmin(T& a, const T& b) { return a = std::min(a, b), a == b; }template <typename T>bool chmax(T& a, const T& b) { return a = std::max(a, b), a == b; }template <typename T>std::vector<T> Vec(const std::size_t n, T v) { return std::vector<T>(n, v); }template <class... Args>auto Vec(const std::size_t n, Args... args) { return std::vector<decltype(Vec(args...))>(n, Vec(args...)); }template <typename T>constexpr T popCount(const T u){#ifdef __has_builtinreturn u == 0 ? T(0) : (T)__builtin_popcountll(u);#elseunsigned long long v = static_cast<unsigned long long>(u);return v = (v & 0x5555555555555555ULL) + (v >> 1 & 0x5555555555555555ULL), v = (v & 0x3333333333333333ULL) + (v >> 2 & 0x3333333333333333ULL), v= (v + (v >> 4)) & 0x0F0F0F0F0F0F0F0FULL, static_cast<T>(v * 0x0101010101010101ULL >> 56 & 0x7f);#endif}template <typename T>constexpr T log2p1(const T u){#ifdef __has_builtinreturn u == 0 ? T(0) : T(64 - __builtin_clzll(u));#elseunsigned long long v = static_cast<unsigned long long>(u);return v = static_cast<unsigned long long>(v), v |= (v >> 1), v |= (v >> 2), v |= (v >> 4), v |= (v >> 8), v |= (v >> 16), v |= (v >> 32),popCount(v);#endif}template <typename T>constexpr T clog(const T v) { return v == 0 ? T(0) : log2p1(v - 1); }template <typename T>constexpr T msbp1(const T v) { return log2p1(v); }template <typename T>constexpr T lsbp1(const T v){#ifdef __has_builtinreturn __builtin_ffsll(v);#elsereturn v == 0 ? T(0) : popCount((v & (-v)) - T(1)) + T(1);#endif}template <typename T>constexpr bool ispow2(const T v) { return popCount(v) == 1; }template <typename T>constexpr T ceil2(const T v) { return v == 0 ? T(1) : T(1) << log2p1(v - 1); }template <typename T>constexpr T floor2(const T v) { return v == 0 ? T(0) : T(1) << (log2p1(v) - 1); }//!===============================================================!////! 88888888b dP .88888. a88888b. 888888ba !////! 88 88 d8' '88 d8' '88 88 '8b !////! a88aaaa dP. .dP d8888P 88 88 88 88 !////! 88 '8bd8' 88 88 YP88 88 88 88 !////! 88 .d88b. 88 Y8. .88 Y8. .88 88 .8P !////! 88888888P dP' 'dP dP '88888' Y88888P' 8888888P !////!===============================================================!//template <typename T>constexpr std::pair<T, T> extgcd(const T a, const T b){if (b == 0) { return std::pair<T, T>{1, 0}; }const auto p = extgcd(b, a % b);return {p.second, p.first - p.second * (a / b)};}template <typename T>constexpr T inverse(const T a, const T mod) { return (mod + extgcd((mod + a % mod) % mod, mod).first % mod) % mod; }//!========================================================!////! 8888ba.88ba dP dP dP !////! 88 '8b '8b 88 88 88 !////! 88 88 88 .d8888b. .d888b88 88 88d888b. d8888P !////! 88 88 88 88' '88 88' '88 88 88' '88 88 !////! 88 88 88 88. .88 88. .88 88 88 88 88 !////! dP dP dP '88888P' '88888P8 dP dP dP dP !////!========================================================!//template <uint mod>class ModInt{private:uint v;static uint norm(const uint& x) { return x < mod ? x : x - mod; }static ModInt make(const uint& x){ModInt m;return m.v = x, m;}static ModInt power(ModInt x, ll n){ModInt ans = 1;for (; n; n >>= 1, x *= x) {if (n & 1) { ans *= x; }}return ans;}static ModInt inv(const ModInt& x) { return ModInt{inverse((ll)x.v, (ll)mod)}; }public:ModInt() : v{0} {}ModInt(const ll val) : v{norm(uint(val % (ll)mod + (ll)mod))} {}ModInt(const ModInt<mod>& n) : v{n()} {}explicit operator bool() const { return v != 0; }ModInt<mod>& operator=(const ModInt<mod>& n) { return v = n(), (*this); }ModInt<mod>& operator=(const ll val) { return v = norm(uint(val % (ll)mod + (ll)mod)), (*this); }ModInt<mod> operator+() const { return *this; }ModInt<mod> operator-() const { return make(norm(mod - v)); }ModInt<mod> operator+(const ModInt<mod>& val) const { return make(norm(v + val())); }ModInt<mod> operator-(const ModInt<mod>& val) const { return make(norm(v + mod - val())); }ModInt<mod> operator*(const ModInt<mod>& val) const { return make((uint)((ll)v * val() % (ll)mod)); }ModInt<mod> operator/(const ModInt<mod>& val) const { return *this * inv(val()); }ModInt<mod>& operator+=(const ModInt<mod>& val) { return *this = *this + val; }ModInt<mod>& operator-=(const ModInt<mod>& val) { return *this = *this - val; }ModInt<mod>& operator*=(const ModInt<mod>& val) { return *this = *this * val; }ModInt<mod>& operator/=(const ModInt<mod>& val) { return *this = *this / val; }ModInt<mod> operator+(const ll val) const { return ModInt{v + val}; }ModInt<mod> operator-(const ll val) const { return ModInt{v - val}; }ModInt<mod> operator*(const ll val) const { return ModInt{(ll)v * (val % mod)}; }ModInt<mod> operator/(const ll val) const { return ModInt{(ll)v * inv(val)}; }template <typename I>ModInt<mod> operator^(const I n) const { return power(v, n); }ModInt<mod>& operator+=(const ll val) { return *this = *this + val; }ModInt<mod>& operator-=(const ll val) { return *this = *this - val; }ModInt<mod>& operator*=(const ll val) { return *this = *this * val; }ModInt<mod>& operator/=(const ll val) { return *this = *this / val; }template <typename I>ModInt<mod>& operator^=(const I n) { return (*this) = ((*this) ^ n); }bool operator==(const ModInt<mod>& val) const { return v == val.v; }bool operator!=(const ModInt<mod>& val) const { return not(*this == val); }bool operator==(const ll val) const { return v == norm(uint((ll)mod + val % (ll)mod)); }bool operator!=(const ll val) const { return not(*this == val); }uint operator()() const { return v; }};template <uint mod>inline ModInt<mod> operator+(const ll val, const ModInt<mod>& n) { return n + val; }template <uint mod>inline ModInt<mod> operator-(const ll val, const ModInt<mod>& n) { return ModInt<mod>{val - (ll)n()}; }template <uint mod>inline ModInt<mod> operator*(const ll val, const ModInt<mod>& n) { return n * val; }template <uint mod>inline ModInt<mod> operator/(const ll val, const ModInt<mod>& n) { return ModInt<mod>(val) / n; }template <uint mod>inline bool operator==(const ll val, const ModInt<mod>& n) { return n == val; }template <uint mod>inline bool operator!=(const ll val, const ModInt<mod>& n) { return not(val == n); }template <uint mod>inline std::istream& operator>>(std::istream& is, ModInt<mod>& n){uint v;return is >> v, n = v, is;}template <uint mod>std::ostream& operator<<(std::ostream& os, const ModInt<mod>& n) { return (os << n()); }//!============================================================================!////! 8888ba.88ba dP a88888b. dP !////! 88 '8b '8b 88 d8' '88 88 !////! 88 88 88 .d8888b. .d888b88 88 .d8888b. 88d8b.d8b. 88d888b. !////! 88 88 88 88' '88 88' '88 88 88' '88 88''88''88 88' '88 !////! 88 88 88 88. .88 88. .88 Y8. .88 88. .88 88 88 88 88. .88 !////! dP dP dP '88888P' '88888P8 Y88888P' '88888P' dP dP dP 88Y8888' !////!============================================================================!//template <uint mod>class ModComb{public:ModComb(const std::size_t N) : f(N + 1, ModInt<mod>(1)), in(N + 1, ModInt<mod>(1)), invf(N + 1, ModInt<mod>(1)){for (uint i = 2; i <= N; i++) { f[i] = f[i - 1] * i, in[i] = (mod - (mod / i)) * in[mod % i], invf[i] = invf[i - 1] * in[i]; }}ModInt<mod> fact(const std::size_t N) const { return f[N]; }ModInt<mod> inv(const std::size_t N) const { return in[N]; }ModInt<mod> invFact(const std::size_t N) const { return invf[N]; }ModInt<mod> perm(const std::size_t N, const std::size_t K) const { return N > f.size() or K > N ? ModInt<mod>(0) : f[N] * invf[N - K]; }ModInt<mod> comb(const std::size_t N, const std::size_t K) const { return N > f.size() or K > N ? ModInt<mod>(0) : f[N] * invf[K] * invf[N - K];}private:std::vector<ModInt<mod>> f, in, invf;};//!============================================!////! 8888ba.88ba oo !////! 88 '8b '8b !////! 88 88 88 .d8888b. dP 88d888b. !////! 88 88 88 88' '88 88 88' '88 !////! 88 88 88 88. .88 88 88 88 !////! dP dP dP '88888P8 dP dP dP !////!============================================!//int main(){int N, K;std::cin >> N >> K;using mint = ModInt<MOD>;ModComb<MOD> mod(N);mint ans = mod.perm(N, K) * N * (N + 1) / 2 - N * K * mod.fact(N - 1) * mod.invFact(N - K);for (int i = N - 1; i >= 1; i--) { ans -= i * (K * mod.fact(N - 1) * mod.invFact(N - K) - mod.comb(K, 2) * mod.fact(N - 2) * mod.invFact(N - K));}std::cout << ans << std::endl;return 0;}