結果
問題 | No.389 ロジックパズルの組み合わせ |
ユーザー |
![]() |
提出日時 | 2016-07-09 00:59:26 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 31 ms / 2,000 ms |
コード長 | 1,359 bytes |
コンパイル時間 | 1,795 ms |
コンパイル使用メモリ | 161,144 KB |
実行使用メモリ | 7,524 KB |
最終ジャッジ日時 | 2024-10-13 07:56:43 |
合計ジャッジ時間 | 4,444 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 99 |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; using ld = long double; using vi = vector<int>; using vvi = vector<vi>; using vb = vector<bool>; using vvb = vector<vb>; using vl = vector<ll>; using vvl = vector<vl>; using vd = vector<double>; using vvd = vector<vd>; #define REP(i,n) for(ll i = 0; i < (n); ++i) #define ALL(c) (c).begin(), (c).end() #define FOR(i,s,e) for (ll i = s; i < (ll)e; i++) #define TEN(x) ((ll)1e##x) ll inverse(ll v, ll mod) { ll a = v, b = mod, x = 1, y = 0; while (b) { ll t = a / b; swap(a -= t * b, b); swap(x -= t * y, y); } return (x % mod + mod) % mod; } ll nCr(ll n,ll r, ll mod){ if(n < r) return 0; r = min(r,n-r); ll ret = 1; REP(i, r) { (ret *= n - i) %= mod; (ret *= inverse(i + 1, mod)) %= mod; } return ret; } int main() { #ifdef _WIN32 ifstream cin("sample.in"); ofstream cout("sample.out"); #endif cin.tie(0); // cinとcoutの連携を切る ios_base::sync_with_stdio(false); cout << fixed << setprecision(50); ll m; cin >> m; vl h; { ll tmp; while (cin >> tmp) h.push_back(tmp); } if (h[0] == 0) { cout << 1 << endl; return 0; } ll sum = -1; REP(i, h.size()) sum += h[i] + 1; ll diff = m - sum; if (diff < 0) { cout << "NA" << endl; return 0; } ll mod = TEN(9) + 7; cout << nCr(diff + h.size(), diff, mod) << endl; return 0; }