結果
| 問題 | No.117 組み合わせの数 |
| ユーザー |
 gurualo
|
| 提出日時 | 2019-04-30 14:35:21 |
| 言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
AC
|
| 実行時間 | 332 ms / 5,000 ms |
| コード長 | 8,199 bytes |
| コンパイル時間 | 1,961 ms |
| コンパイル使用メモリ | 220,508 KB |
| 実行使用メモリ | 34,420 KB |
| 最終ジャッジ日時 | 2024-06-09 12:29:27 |
| 合計ジャッジ時間 | 3,175 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge4 |
（要ログイン）
ソースコード
#include <vector>
#include <list>
#include <map>
#include <set>//2分探索木
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <queue>// キュー 優先度付きキュー
#include <stack>
#include <complex>
#include <memory>
#include <assert.h>
#ifdef LOCAL
#include "UnionFind.h"//同じグループに属するか
#include "Prime.h"//素数判定
#include "RMQ.h"//区間最小値
#include "BIT.h"//累積和
#include "Dijkstra.h"//単一始点最短経路(負の辺があるときは動作しない) O(ElogV)
#include "Kruskal.h"//最小全域木 O(ElogV)
#include "Factorial.h"//階乗 組み合わせ
#endif
using namespace std;
//conversion
//------------------------------------------
inline long long toInt(string s) { long long v; istringstream sin(s); sin >> v; return v; }
template<class T> inline string toString(T x) { ostringstream sout; sout << x; return sout.str(); }
//math
//-------------------------------------------
template<class T> inline T sqr(T x) { return x * x; }
//typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;
typedef vector<LL> VLL;
typedef vector<PII> VPII;
//container util
//------------------------------------------
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(t,c) for(typeof((c).begin()) t=(c).begin(); t!=(c).end(); ++t)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())
//split
std::vector<std::string> split(std::string str, set<char> del) {
std::vector<std::string> result;
std::string subStr;
for (const char c : str) {
if (EXIST(del, c)) {
result.push_back(subStr);
subStr.clear();
}
else {
subStr += c;
}
}
result.push_back(subStr);
return result;
}
//repetition
//------------------------------------------
#define FOR(t,a,b) for(int t=(a);t<(b);++t)
#define REP(t,n) FOR(t,0,n)
//constant
//------------------------------------------
const double EPS = 1e-10;
const double PI = acos(-1.0);
//clear memory
//------------------------------------------
#define CLR(a) memset((a), 0 ,sizeof(a))
//debug
//------------------------------------------
#if defined(__GNUC__)
#include <assert.h>
#define ASSERT_(x) assert(x)
#else
#include <assert.h>
#define ASSERT_(x) assert(x)
#endif
#ifdef _DEBUG
#define dump(x) cerr << #x << '=' << (x) << endl;
#define debug(x) cerr << #x << '=' << (x) << '('<<'L' << __LINE__ << ')' << ' ' << __FILE__ << endl;
#define ASSERT(x) {if (!(x)){std::cerr << "\nError!!\n" << "info string file:" << __FILE__ << " line:" << __LINE__ <<" "<< #x<< std::endl;ASSERT_(x);}}
#else
#define ASSERT(x) ((void)0)
#define debug(x) ((void)0)
#define dump(x) ((void)0)
#endif // _DEBUG
template<class T> void showVector(vector<T>& v) {
for (int i = 0; i < v.size(); ++i)
cerr << v[i] << " ";
cerr << endl;
}
//mod
//-------------------------------------------
const LL mod = 1000000007;
LL mod_pow(LL x, LL n, LL mod) {
if (n == 0) { return 1; }
LL res = mod_pow(x * x % mod, n / 2, mod);
if (n & 1) { res = res * x % mod; }
return res;
}
//組み合わせ数
LL conbination(LL n, LL r) {
if (r > n || r < 0LL) { return 0LL; }
LL i;
LL s = 1LL;
for (i = 1LL; i <= r; i++) { s = s * (n + 1LL - i) / i; }
return s;
}
//bitop
//-------------------------------------------
#if defined(__GNUC__)
#include <immintrin.h>
int popcount(int a) {
return __builtin_popcount(a);
}
#elif defined(_MSC_VER)
#include <intrin.h>
int popcount(int a) {
return __popcnt(a);
}
#endif
//gcd lcm
//-------------------------------------------
LL gcd(LL a, LL b) { if (a % b == 0) { return b; } else return gcd(b, a % b); }
LL lcm(LL a, LL b) { return a / gcd(a, b) * b; }
//YES_NO
//------------------------------------------
#define Yes_ cout<<"Yes"<<endl; return 0;
#define No_ cout<<"No"<<endl; return 0;
#define YES_ cout<<"YES"<<endl; return 0;
#define NO_ cout<<"NO"<<endl; return 0;
#define POSSIBLE cout<<"POSSIBLE"<<endl; return 0;
#define IMPOSSIBLE cout<<"IMPOSSIBLE"<<endl; return 0;
//matrix
//------------------------------------------
template <class T> class matrix : public vector< vector<T> > {
private:
int tate_, yoko_;
public:
matrix(const int tate__, const int yoko__) {
ASSERT(tate__ > 0); ASSERT(yoko__ > 0);
this->resize(tate__); for (size_t i = 0; i < this->size(); i++) { (*this)[i].resize(yoko__); }tate_ = tate__; yoko_ = yoko__;
}
matrix() {};
int tate() const { return tate_; } int yoko() const { return yoko_; }
void resizematrix(const int tate__, const int yoko__) {
ASSERT(tate__ > 0); ASSERT(yoko__ > 0);
this->resize(tate__); for (size_t i = 0; i < this->size(); i++) { (*this)[i].resize(yoko__); }tate_ = tate__; yoko_ = yoko__;
}
void setzero() { for (int i = 0; i < tate(); i++) for (int j = 0; j < yoko(); j++) { (*this)[i][j] = 0; } }
};
template<class T> std::ostream& operator<<(std::ostream & os, const matrix<T> & m)
{
for (int j = 0; j < m.tate(); j++) { for (int i = 0; i < m.yoko(); i++) { os << (int)m[j][i]; }os << endl; }
return os;
}
#if 1
//time
//------------------------------------------
#if defined(__GNUC__)
#include <sys/time.h>
#include <immintrin.h>
#include <string.h>
LL starttime;
inline LL now() {
struct timeval tv;
gettimeofday(&tv, NULL);
LL t = tv.tv_sec * 1000LL + tv.tv_usec / 1000LL;
return t;
}
inline LL elapsed() { return now() - starttime; }
#else
#include <chrono>
#include <intrin.h>
typedef std::chrono::milliseconds::rep TimePoint;
inline TimePoint now() { return std::chrono::duration_cast<std::chrono::milliseconds>(std::chrono::steady_clock::now().time_since_epoch()).count(); }
TimePoint starttime;
inline TimePoint elapsed() { return now() - starttime; }
#endif
#endif
//=====================================================
struct Factorial
{
Factorial(int n_) :n(n_) { init(); }
const LL mod = 1000000007;//modは素数だと仮定
int n;
std::vector<LL> fac_, inv_;
void init() {
fac_.resize(n + 1);
inv_.resize(n + 1);
calc_factorial();
calc_inv();
}
//累乗の計算
void calc_factorial() {
fac_[0] = 1;
for (int i = 1; i <= n; i++) {
fac_[i] = i * fac_[i - 1] % mod;
}
}
LL mod_pow(LL x, LL n, LL mod) {
if (n == 0) { return 1; }
LL res = mod_pow(x * x % mod, n / 2, mod);
if (n & 1) { res = res * x % mod; }
return res;
}
//逆元の計算
void calc_inv() {
inv_[n] = mod_pow(fac_[n], mod - 2, mod);
for (int i = n - 1; i >= 0; i--) {
inv_[i] = (i + 1) * inv_[i + 1] % mod;
}
}
//逆元を返す
LL inv(size_t i) {
assert(i >= 0 && i <= n);
return inv_[i];
}
//1 以上 N 以下の N 個の整数の中から，相異なる K 個の整数を選ぶパターンの数
LL comb(int n, int k) {
if (n < k)return 0;
LL res = fac_[n];
res = res * inv_[n - k] % mod;
res = res * inv_[k] % mod;
return res;
}
//1 以上 N 以下の N 個の整数の中から，相異なる K 個の整数を選び，順番に並べるパターンの数を P(N,K)
LL perm(int n, int k) {
if (n < k)return 0;
LL res = fac_[n];
res = res * inv_[n - k] % mod;
return res;
}
//1 以上 N 以下の N 個の整数の中から，重複を許して K 個の整数を選ぶパターンの数
LL h(int n, int k) {
if (n == 0 && k == 0)return 1;
return comb(n + k - 1, k);
}
//階乗(n!)を返す
LL fac(size_t i) {
assert(i >= 0 && i <= n);
return fac_[i];
}
};
int main() {
int t;
cin >> t;
Factorial fac(2000000);
REP(i, t) {
string s;
cin >> s;
vector<string> ss = split(s, { ',','(',')' });
int x = toInt(ss[1]);
int y = toInt(ss[2]);
if (ss[0] == "C") {
cout << fac.comb(x, y) << endl;
}
else if (ss[0] == "P") {
cout << fac.perm(x, y) << endl;
}
else {
cout << fac.h(x, y) << endl;
}
}
}