結果
問題 | No.389 ロジックパズルの組み合わせ |
ユーザー |
|
提出日時 | 2016-07-08 22:39:40 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 103 ms / 2,000 ms |
コード長 | 1,516 bytes |
コンパイル時間 | 2,827 ms |
コンパイル使用メモリ | 169,144 KB |
実行使用メモリ | 69,272 KB |
最終ジャッジ日時 | 2024-10-13 04:40:20 |
合計ジャッジ時間 | 11,592 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 99 |
ソースコード
#include <bits/stdc++.h> using namespace std; const long long mod = 1e9 + 7; vector<long long> F, invF; long long modpow(long long a, long long b, long long mod) { long long ret = 1; for (; b > 0; a = a * a % mod, b /= 2) if (b & 1) ret = ret * a % mod; return ret; } long long modinv(long long a, long long mod) { return modpow(a, mod - 2, mod); } void initF(int n) { F.resize(n, 1); invF.resize(n, 1); for (int i = 1; i < n; i++) F[i] = i * F[i - 1] % mod; invF[n - 1] = modinv(F[n - 1], mod); for (int i = n - 2; i >= 0; i--) invF[i] = invF[i + 1] * (i + 1) % mod; } long long P(int a, int b) { if (a < b || a < 0 || b < 0) return 0; return F[a] * invF[a - b] % mod; } long long C(int a, int b) { if (a < b || a < 0 || b < 0) return -1; return P(a, b) * invF[b] % mod; } long long H(int a, int b) { if (a == 0 && b == 0) return 1; return C(a + b - 1, b); } vector<string> split(string s, char d) { vector<string> ret; for (int i = 0; i <= s.size(); i++) { int j = i; while (i < s.size() && s[i] != d) i++; ret.emplace_back(s.substr(j, i - j)); } return ret; } int main() { initF(3030303); int m; cin >> m; cin.ignore(); string s; getline(cin, s); auto ss = split(s, ' '); int n = ss.size(); vector<int> h(n); for (int i = 0; i < n; i++) h[i] = stoi(ss[i]); for (int i = 0; i < n; i++) m -= h[i] + 1; m++; if (h[0] == 0) { cout << 1 << endl; } else { int ans = H(n + 1, m); if (ans == -1) { cout << "NA" << endl; } else { cout << ans << endl; } } }