QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#232708 | #959. Multiple? | Hunster | TL | 1779ms | 3720kb | C++14 | 3.6kb | 2023-10-30 20:21:34 | 2023-10-30 20:21:34 |
Judging History
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