結果

問題 No.117 組み合わせの数
ユーザー sdfi13jfxsdfi13jfx
提出日時 2019-07-08 08:07:46
言語 C++11
(gcc 13.3.0)
結果
AC  
実行時間 83 ms / 5,000 ms
コード長 4,555 bytes
コンパイル時間 580 ms
コンパイル使用メモリ 63,260 KB
実行使用メモリ 18,856 KB
最終ジャッジ日時 2024-10-07 17:26:37
合計ジャッジ時間 1,349 ms
ジャッジサーバーID
(参考情報)
judge5 / judge2
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 1
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:128:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  128 |     scanf("%d\n", &T);
      |     ~~~~~^~~~~~~~~~~~
main.cpp:131:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  131 |         scanf("%c(%d,%d)\n", &c, &n, &k);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

ソースコード

diff #
プレゼンテーションモードにする

#include <iostream>
#include <vector>
// @require ./modular_arithmetics.cc 👇👇
template<typename T, T MOD>
struct ModType {
public:
using Int = T;
static constexpr Int mod = MOD;
ModType(long long _v = 0) : v(set(_v)) {}
ModType(const ModType &r) : v(set(r.v)) {}
Int get_val() const { return v; }
bool operator<(ModType r) const { return v < r.v; }
bool operator>(ModType r) const { return v > r.v; }
bool operator<=(ModType r) const { return v <= r.v; }
bool operator>=(ModType r) const { return v >= r.v; }
bool operator==(ModType r) const { return v == r.v; }
bool operator!= (ModType r) const { return v != r.v; }
ModType operator-() const { return ModInt(v ? mod - v : v); }
ModType &operator=(const ModType &r) { if (this != &r) v = set(r.v); return *this; }
ModType operator++(){ if (++v == mod) v = 0; return *this; }
ModType operator--(){ v = (v == 0 ? mod - 1 : v - 1); return *this; }
ModType &operator+=(ModType r) { (v += r.v) %= mod; return *this; }
ModType &operator-=(ModType r) { (v -= r.v - mod) %= mod; return *this; }
// ModType &operator*=(ModType r) { v = (__uint128_t(v) * r.v) % mod; return *this; }
ModType &operator*=(ModType r) { v = 1ULL * v * r.v % mod; return *this; }
ModType &operator/=(ModType r) { *this *= r.inv(); return *this; }
ModType operator+(ModType r) const { return ModType(*this) += r; }
ModType operator-(ModType r) const { return ModType(*this) -= r; }
ModType operator*(ModType r) const { return ModType(*this) *= r; }
ModType operator/(ModType r) const { return ModType(*this) /= r; }
ModType inv() const {
long long a = v, b = mod, u = 1, w = 0;
while (b) {
long long t = a / b;
std::swap(a -= t * b, b);
std::swap(u -= t * w, w);
}
return ModType(u);
}
ModType pow(Int e) {
ModType a = *this, x(1);
for ( ; 0 < e; e >>= 1) { if (e & 1) x *= a; a *= a; }
return x;
}
inline ModType pow(ModType &e) { return pow(e.v); }
friend std::ostream &operator<<(std::ostream &os, const ModType &r) { return os << r.v; }
friend std::istream &operator>>(std::istream &is, ModType &r) {
is >> r.v; r.set();return is;
}
static std::vector<ModType> Inverse(const Int n = mod - 1) {
std::vector<ModType> inv(n + 1);
inv[1].v = 1;
for (Int a = 2; a <= n; ++a)
inv[a] = inv[mod % a] * T(mod - mod / a);
return inv;
}
private:
Int v;
inline static Int set(const Int x) { return x < 0 ? (x % mod) + mod : x % mod; }
inline void set() { v = set(v); }
};
using ModInt = ModType<int, 1000000007>;
// -------------8<------- start of library -------8<------------------------
struct Combination {
const ModInt::Int mod = ModInt::mod;
ModInt::Int N = 0;
std::vector<ModInt> fact, inv_f;
// MultiChoose 使 N = 2 * _n
explicit Combination(int _n) : N(_n < mod ? _n : mod - 1), fact(N + 1), inv_f(N + 1) {
set();
}
void set() {
fact[0] = 1;
for (int i = 1; i <= N; ++i) fact[i] = fact[i - 1] * i;
inv_f[N] = fact[N].inv();
for (int i = N; 1 <= i; --i) inv_f[i - 1] = inv_f[i] * i;
}
void resize(int _n) {
N = (_n < mod ? _n : mod - 1);
fact.resize(N + 1);
inv_f.resize(N + 1);
set();
}
ModInt factorial(const int n) const { return fact[n]; }
ModInt invFactorial(const int n) const { return inv_f[n]; }
ModInt permutation(const int n, const int k) const {
if (k < 0 || n < k) return ModInt(0);
else return fact[n] * inv_f[n - k];
}
ModInt choose(const int n, const int k) const {
if (n < 0 || k < 0 || n < k) return ModInt(0);
else return fact[n] * inv_f[k] * inv_f[n - k];
}
ModInt multiChoose(const int n, const int k) const {
if (n < 0 || k < 0) return ModInt(0);
else return k == 0 ? 1 : choose(n + k - 1, k);
}
};
// -------------8<------- end of library ---------8-------------------------
int main() {
Combination cm(2 * 1e6);
int T, n, k;
char c;
scanf("%d\n", &T);
while (T--) {
scanf("%c(%d,%d)\n", &c, &n, &k);
if (c == 'C') printf("%d\n", cm.choose(n, k).get_val());
else if (c == 'P') printf("%d\n", cm.permutation(n, k).get_val());
else if (c == 'H') printf("%d\n", cm.multiChoose(n, k).get_val());
}
return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0