QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#232708#959. Multiple?HunsterTL 1779ms3720kbC++143.6kb2023-10-30 20:21:342023-10-30 20:21:34

Judging History

你现在查看的是最新测评结果

  • [2023-10-30 20:21:34]
  • 评测
  • 测评结果:TL
  • 用时:1779ms
  • 内存:3720kb
  • [2023-10-30 20:21:34]
  • 提交

answer

#include <bits/stdc++.h>

template <bool flag, typename T1, typename T2>
struct TemplateIf;
template <typename T1, typename T2>
struct TemplateIf<true, T1, T2> { using Type = T1; };
template <typename T1, typename T2>
struct TemplateIf<false, T1, T2> { using Type = T2; };

using i32 = int32_t;
using i64 = int64_t;
using i128 = __int128_t;
using u32 = uint32_t;
using u64 = uint64_t;
using u128 = __uint128_t;
template <typename T>
using Vec = std::vector<T>;
template <typename T, size_t... other>
struct ArraySwitch;
template <typename T, size_t size, size_t... other>
struct ArraySwitch<T, size, other...> { using Result = std::array<typename ArraySwitch<T, other...>::Result, size>; };
template <typename T, size_t size>
struct ArraySwitch<T, size> { using Result = typename std::array<T, size>; };
template <typename T, size_t... size>
using Arr = typename ArraySwitch<T, size...>::Result;
template <typename T>
using MaxHeap = std::priority_queue<T, Vec<T>, std::less<T>>;
template <typename T>
using MinHeap = std::priority_queue<T, Vec<T>, std::greater<T>>;			

constexpr i32 inf32 = (i32)(1e9) + 9;
constexpr i64 inf64 = (i64)(1e18) + 18;

std::mt19937 rng { (std::random_device())() };

template <typename Arr, typename T>
void fill_arr(Arr &arr, const T &val) { std::fill_n((T*)(&arr), sizeof(arr) / sizeof(T), val); }

template <typename T>
inline T makeVec(T val) { return val; }
template <typename T, typename... Args>
inline auto makeVec(T val, size_t size, Args... rest) {
    auto t = makeVec<T>(val, rest...);
    return Vec<decltype(t)>(size, t);
}

inline i32 clz(u32 x) { return __builtin_clz(x); }
inline i32 clzll(u64 x) { return __builtin_clzll(x); }
inline i32 ctz(u32 x) { return __builtin_ctz(x); }
inline i32 ctzll(u64 x) { return __builtin_ctzll(x); }
inline i32 popcount(u32 x) { return __builtin_popcount(x); }
inline i32 popcountll(u64 x) { return __builtin_popcountll(x); }

template <typename T>
inline T _min(T a) { return a; }
template <typename T, typename... Args>
inline T _min(T a, T b, Args... args) { return _min<T>(std::min<T>(a, b), args...); }
template <typename T>
inline T _max(T a) { return a; }
template <typename T, typename... Args>
inline T _max(T a, T b, Args... args) { return _max<T>(std::max<T>(a, b), args...); }

constexpr i32 num_big_primes = 10;
constexpr Arr<i32, num_big_primes> big_primes { 99990571, 99990337, 99999941, 99999931, 99999847, 99999839, 99999827, 99999821, 99999787, 99999773, };
inline i32 get_big_prime() { return big_primes[std::uniform_int_distribution<i32>(0, num_big_primes - 1)(rng)]; }

constexpr i32 mod = 998244353;

i32 power(i32 n, i32 m) {
    i32 sum = 1;
    for (; m; m >>= 1, n = 1ll * n * n % mod)
        if (m & 1) sum = 1ll * sum * n % mod;
    return sum;
}
i32 get_inv(i32 n) { return power(n, mod - 2); }
i32 C(i32 n, i32 m) {
    if (n < 0 || m < 0 || n - m < 0) return 0;
    i32 sum0 = 1, sum1 = 1;
    for (i32 i = n; i > n - m; i--)
        sum0 = 1ll * sum0 * i % mod;
    for (i32 i = 1; i <= m; i++)
        sum1 = 1ll * sum1 * i % mod;
    return 1ll * sum0 * get_inv(sum1) % mod;
}

i32 phi(i32 n) {
    i32 sum = n;
    for (i32 i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            sum = sum / i * (i - 1);
            while (n % i == 0) n /= i;
        }
    }
    if (n > 1) sum = sum / n * (n - 1);
    return sum;
}

i32 main() {
    i32 n, k;
    std::cin >> n >> k;
    std::cout << 1ll * C(n - 1, n - k) * phi(n) % mod << std::endl;
    std::cerr << "use time: " << 1. * std::clock() / CLOCKS_PER_SEC << std::endl;
    return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 3720kb

input:

4 1

output:

2

result:

ok 1 number(s): "2"

Test #2:

score: 0
Accepted
time: 0ms
memory: 3668kb

input:

9 2

output:

48

result:

ok 1 number(s): "48"

Test #3:

score: 0
Accepted
time: 1779ms
memory: 3708kb

input:

222222222 222222

output:

851798824

result:

ok 1 number(s): "851798824"

Test #4:

score: -100
Time Limit Exceeded

input:

998244352 249561088

output:


result: