結果
問題 | No.696 square1001 and Permutation 5 |
ユーザー |
![]() |
提出日時 | 2018-06-08 23:20:18 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 8,490 ms / 10,000 ms |
コード長 | 2,010 bytes |
コンパイル時間 | 827 ms |
コンパイル使用メモリ | 76,788 KB |
実行使用メモリ | 7,412 KB |
最終ジャッジ日時 | 2024-06-30 11:05:51 |
合計ジャッジ時間 | 31,743 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 12 |
ソースコード
#include <iostream>#include <algorithm>#include <vector>#include <string>using namespace std;long long INF = 1000000000000000000LL, BB = 1000000000LL, T = 9LL;vector<long long>kakezan(vector<long long>A, vector<long long>B) {vector<long long>C(A.size() + B.size(), 0);for (int i = 0; i < A.size(); i++) {for (int j = 0; j < B.size(); j++) {C[i + j] += A[i] * B[j];if (C[i + j] >= INF) { C[i + j + 1] += BB; C[i + j] -= INF; }}}for (int i = 0; i < C.size() - 1; i++) {C[i + 1] += C[i] / BB;C[i] %= BB;}while (C[C.size() - 1] == 0 && C.size() >= 2) C.pop_back();return C;}vector<long long>tashizan(vector<long long>A, vector<long long>B) {vector<long long>C(max(A.size(), B.size()) + 1);for (int i = 0; i < A.size(); i++) C[i] += A[i];for (int i = 0; i < B.size(); i++) C[i] += B[i];for (int i = 0; i < C.size() - 1; i++) {C[i + 1] += C[i] / BB;C[i] %= BB;}while (C[C.size() - 1] == 0 && C.size() >= 2) C.pop_back();return C;}int bit[100009];void add(int pos, int x) {while (pos <= 100008) { bit[pos] += x; pos += (pos&-pos); }}int sum(int pos) {int s = 0;while (pos >= 1) { s += bit[pos]; pos -= (pos&-pos); }return s;}long long N, P[100009], S[100009];vector<long long>factorial(long long L, long long R) {if (R - L == 1) return vector<long long>{L};return kakezan(factorial(L, (L + R) / 2), factorial((L + R) / 2, R));}vector<long long>solve(long long L, long long R) {if (R - L == 1) return vector<long long>{S[L]};return tashizan(solve(L, (L + R) / 2), kakezan(solve((L + R) / 2, R), factorial(L, (L + R) / 2)));}int main() {cin >> N;for (int i = 1; i <= N; i++) cin >> P[i];for (int i = N; i >= 1; i--) {S[i] = sum(P[i]);add(P[i], 1);}reverse(S + 1, S + N + 1);S[1]++;vector<long long>D = solve(1, N + 1);for (int i = D.size() - 1; i >= 0; i--) {string S = to_string(D[i]);if (i < (int)D.size() - 1) { while (S.size() < T) S = "0" + S; }cout << S;}cout << endl;return 0;}