結果
問題 | No.389 ロジックパズルの組み合わせ |
ユーザー |
![]() |
提出日時 | 2016-07-08 23:33:19 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 43 ms / 2,000 ms |
コード長 | 1,991 bytes |
コンパイル時間 | 1,486 ms |
コンパイル使用メモリ | 170,940 KB |
実行使用メモリ | 25,988 KB |
最終ジャッジ日時 | 2024-10-13 07:17:02 |
合計ジャッジ時間 | 5,627 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 99 |
ソースコード
#include <bits/stdc++.h> using namespace std; #define int long long // <-----!!!!!!!!!!!!!!!!!!! #define rep(i,n) for (int i=0;i<(n);i++) #define rep2(i,a,b) for (int i=(a);i<(b);i++) #define rrep(i,n) for (int i=(n)-1;i>=0;i--) #define rrep2(i,a,b) for (int i=(b)-1;i>=(a);i--) #define all(a) (a).begin(),(a).end() typedef long long ll; typedef pair<int, int> Pii; typedef tuple<int, int, int> TUPLE; typedef vector<int> V; typedef vector<V> VV; typedef vector<VV> VVV; typedef vector<vector<int>> Graph; const int inf = 1e9; const int mod = 1e9 + 7; ll powmod (ll a, ll p) { ll ans = 1ll; ll mul = a; for (; p > 0ll; p >>= 1ll, mul = (mul * mul) % mod) { if ((p & 1ll) == 1ll) ans = (ans * mul) % mod; } return ans; } ll getRev(ll x) { return powmod(x, mod - 2ll); } // int C(int n, int k) { // int ret = 1ll; // for (int i = n; i > n - k; i--) { // (ret *= i) %= mod; // } // for (int i = k; i >= 1ll; i--) { // (ret *= getRev(i)) %= mod; // } // return ret; // } const int MAX_N = 1000010; ll fact[MAX_N]; ll revFact[MAX_N]; // !!!!!!!!SET FACT!!!!!!! void setFact(int N) { fact[0] = 1; for (int i = 1; i < N; i++) { fact[i] = fact[i - 1] * i; fact[i] %= mod; } revFact[N - 1] = powmod(fact[N - 1], mod - 2); for (int i = N - 2; i >= 0; i--) { revFact[i] = revFact[i + 1] * (i + 1); revFact[i] %= mod; } } ll getC(int a, int b) { return (((fact[a] * revFact[b]) % mod) * revFact[a - b]) % mod; } signed main() { std::ios::sync_with_stdio(false); std::cin.tie(0); int M; cin >> M; setFact(MAX_N); V h; string s; cin.ignore(); getline(cin, s); stringstream ss(s); int x; while (ss >> x) h.emplace_back(x); int K = h.size(); int sm = accumulate(all(h), 0ll); if (sm == 0ll) { cout << 1ll << endl; return 0; } if (M - sm + 1ll < K) { cout << "NA" << endl; return 0; } cout << getC(M - sm + 1ll, K) << endl; }