結果
| 問題 | No.603 hel__world (2) |
| ユーザー |
 Sebastian King
|
| 提出日時 | 2017-12-04 00:52:27 |
| 言語 | C++11（廃止可能性あり） (gcc 13.3.0) |
| 結果 |
AC
|
| 実行時間 | 68 ms / 3,000 ms |
| コード長 | 4,669 bytes |
| コンパイル時間 | 1,959 ms |
| コンパイル使用メモリ | 178,544 KB |
| 実行使用メモリ | 31,592 KB |
| 最終ジャッジ日時 | 2024-11-30 20:57:20 |
| 合計ジャッジ時間 | 3,752 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 30 |
コンパイルメッセージ
main.cpp: In function ‘ll gao(ll, std::vector<int>)’:
main.cpp:98:53: warning: narrowing conversion of ‘b.std::vector<long long int>::size()’ from ‘std::vector<long long int>::size_type’ {aka ‘long unsigned int’} to ‘int’ [-Wnarrowing]
98 | Q.push((node){y + 1, x.first, b.size()});
| ~~~~~~^~
ソースコード
#include<bits/stdc++.h>using namespace std;typedef long long ll;typedef pair<int, int> PII;const int MM = 1e6 + 3;const double eps = 1e-8;const int MAXN = 2e6 + 10;using int64 = long long;using int128 = __int128;const int N = 1e6 + 10;const int mod = 1e6 + 3;const int128 denom = 2e20;int64 fac[mod], inv[mod];int64 binom(int64 n, int64 m) {if (n < m) return 0;if (n == m || m == 0) return 1;int64 a = n % mod, b = m % mod;if (a < b) return 0;return fac[a] * inv[fac[b]] * inv[fac[a - b]] % mod * binom(n / mod, m / mod) % mod;}ll a[100];vector<int> s[100];string str;int n, m;void prework(){fac[0] = fac[1] = inv[1] = 1;for (int i = 2; i < mod; ++i) {fac[i] = i * fac[i - 1] % mod;inv[i] = (mod - mod / i) * inv[mod % i] % mod;}}void read(){}struct node{__int128 y, x;int num;};bool operator < (const node & a, const node & b){return a.y * (b.y - b.x) < b.y * (a.y - a.x);}ll gao(ll S, vector<int> a){ll tmpS = S;//cout << S << ' ' << a.size() << endl;ll __sm = 0;for (auto &x : a) __sm += x;sort(a.begin(), a.end());if (__sm > S) return 0ll;if (__sm == S) return 1ll;if (a.size() == 0) return 1ll;if (a.size() == 1)return binom(S, a[0]);__int128 limit = 5e23;__int128 l = limit + 1, r = limit * (a.back() + 2) + 1;vector<PII> c, ps;a.push_back(a.back() + 1);for (int i = 1, j = 0; i < a.size(); i++)if (a[i] != a[j]){c.push_back(PII(a[j], i - j));ps.push_back(PII(j, i));j = i;}a.pop_back();/*__int128 tot = 0;for (auto &x : c){tot += x.first * l * x.second;if (tot > S) break;}if (tot )*/while(l + 1 < r){__int128 m = (r + l) / 2;__int128 tot = 0;for (auto &x : c){tot += x.first * m / (m - limit) * x.second;if (tot > S) break;}if (tot > S)l = m;elser = m;// cout << (ll)tot << ' ' << S << endl;}vector<ll> b;vector<ll> finb(a.size());priority_queue<node> Q;for (auto &x : c){ll y = (ll)(x.first * r / (r - limit));Q.push((node){y + 1, x.first, b.size()});int l = ps[b.size()].first, r = ps[b.size()].second;for (int i = l; i < r; i++)finb[i] = y;S -= y * x.second;b.push_back(0);}//assert(S >= 0);if (S >= 100000001 && c.back().first < 7){int Magic = 100;S -= 1ll * a.size() * Magic;while(!Q.empty()) Q.pop();ll sm = 0;for (auto &x : c) sm += 1ll * x.first * x.second;for (int i = 0; i < c.size(); i++){b[i] += S / sm * c[i].first;Q.push((node){b[i]+1, c[i].first, i});}S %= sm;S += 1ll * a.size() * Magic;//for (auto &x : b)// cout << x << ' '; cout << endl;}else{/*int Magic = 100;if (S >= a.size() * Magic){while(!Q.empty()) Q.pop();for (int i = 0; i < c.size(); i++){b[i] += (S - a.size() * Magic) / a.size();Q.push((node){b[i]+1, c[i].first, i});}S = (S - Magic * a.size()) % a.size() + Magic * a.size();}*/}//cout << "!!!" << S << ' ' << a.size() << ' ' << c.size() << endl;while(S){node p = Q.top();Q.pop();if (S >= c[p.num].second){b[p.num]++;S -= c[p.num].second;}else{for (int l = ps[p.num].first, i = 0; i < S; i++){finb[l + i]++;}S = 0;}p.y++;Q.push(p);}/*cout << tmpS << ' ';tmpS = 0;for (int i = 0; i < b.size(); i++){tmpS += b[i] * c[i].second;}cout << tmpS << ' ';tmpS = 0;for (int i = 0; i < a.size(); i++)tmpS += finb[i];cout << tmpS << endl;for (auto &x : b)cout << x << ' '; cout << endl;*//*cout << "B: ";for (auto &x : b)cout << x << ' '; cout << endl;cout << "C: ";for (auto &x : c)cout << x.first << ' '; cout << endl;for (int i = 0; i < c.size(); i++){cout << b[i] * 1.0 / (b[i] - c[i].first) << ' ';} cout << endl;cout << 1.0 * l / limit << ' ' << 1.0 * r / limit << endl;*/for (int i = 0; i < c.size(); i++)for (int l = ps[i].first, r = ps[i].second, j = l; j < r; j++)finb[j] += b[i];ll ret = 1;for (int i = 0; i < a.size(); i++)ret = ret * binom(finb[i], a[i]) % mod;//cout << "?? " << S << ' ' << a.size() << ' ' << ret << endl;return ret;}void solve(int casi){// cout << "Case #" << casi << ": ";for (int i = 0; i < 26; i++)cin >> a[i];cin >> str;str += '+';for (int i = 1, j = 0; i < str.length(); i++){if (str[i] != str[j]){s[str[j]-'a'].push_back(i - j);j=i;}}ll ans = 1;for (int i = 0; i < 26; i++)ans = ans * gao(a[i], s[i]) % MM;cout << ans << endl;}void printans(){}int main(){std::ios::sync_with_stdio(false);prework();int T = 1;// cin>>T;for(int i = 1; i <= T; i++){read();solve(i);printans();}return 0;}