QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#575546 | #9353. Interesting Permutation | lqh2024# | WA | 60ms | 4660kb | C++17 | 2.7kb | 2024-09-19 15:16:52 | 2024-09-19 15:16:52 |
Judging History
answer
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> // 包含 tree、gp_hash_table、cc_hash_table
#include <ext/pb_ds/priority_queue.hpp> // 引入后使用 STL 的堆需要 std::
#include <ext/rope>
using namespace __gnu_pbds;
using namespace __gnu_cxx;
using namespace std;
template<class key, class val = null_type, class cmp = less<>>
using rb_tree = tree<key, val, cmp, rb_tree_tag, tree_order_statistics_node_update>;
template<class key, class cmp = less<>>
using pairing_heap = __gnu_pbds::priority_queue<key, cmp>;
typedef long long ll;
#define int long long
template<class T> void print_debug(const T & v) { cerr << v; }
template<class T, class ... A> void print_debug(const T & v, const A & ... a) { cerr << v << ", ", print_debug(a...); }
#define debug(...) (cerr << "[" << #__VA_ARGS__ << "] = [", print_debug(__VA_ARGS__), cerr << "]\n")
mt19937_64 rd(time(0));
const int mod = 1e9 + 7;
auto binpow = [](int a, int b, int res = 1) {
for (a %= mod; b; b >>= 1, (a *= a) %= mod) {
if (b & 1) (res *= a) %= mod;
}
return res;
};
vector<int> inv, fact, invfact;
auto init_inv = [](int n) {
inv = fact = invfact = vector<int>(n + 1, 1); // 注意 0 的 inv 无意义
for (int i = 2; i <= n; i++) { // 注意从 2 开始
(inv[i] = (mod - mod / i) * inv[mod % i]) %= mod;
(fact[i] = fact[i - 1] * i) %= mod, (invfact[i] = invfact[i - 1] * inv[i]) %= mod;
}
};
auto C = [](int n, int m) -> int {
return m > n || n < 0 || m < 0 ? 0 : fact[n] * invfact[m] % mod * invfact[n - m] % mod;
};
auto P = [](int n, int m) -> int {
return m > n || n < 0 || m < 0 ? 0 : fact[n] * invfact[n - m] % mod;
};
auto Lucas = [](auto && self, int n, int m) -> int {
return m == 0 ? 1 : C(n % mod, m % mod) * self(self, n / mod, m / mod) % mod;
};
void QAQ() {
int n, ans = 1;
cin >> n;
vector<int> a(n + 1);
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
if (a[0] != 0) return cout << "0\n", void();
for (int i = 1; i <= n; i++) {
if (a[i] < a[i - 1]) return cout << "0\n", void();
if (a[i] < i - 1) return cout << "0\n", void();
}
if (*max_element(a.begin() + 1, a.end()) != n - 1) return cout << "0\n", void();
for (int i = 2; i <= n; i++) {
if (a[i] != a[i - 1]) {
(ans *= 2) %= mod;
} else if (a[i] == a[i - 1]) {
(ans *= a[i] + 1 - (i - 1)) %= mod;
}
}
cout << ans << "\n";
}
signed main() {
cin.tie(0) -> sync_with_stdio(0);
cout << fixed << setprecision(12);
int t = 1;
cin >> t;
while (t--) {
QAQ();
}
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3940kb
input:
3 3 0 2 2 3 0 1 2 3 0 2 3
output:
2 4 0
result:
ok 3 lines
Test #2:
score: -100
Wrong Answer
time: 60ms
memory: 4660kb
input:
10039 14 5 6 7 8 9 10 11 12 13 13 13 13 13 13 14 0 5 6 7 8 9 10 11 12 13 14 14 14 14 1 1 14 0 5 4 8 9 10 11 12 13 13 13 13 13 13 45 0 1 1 2 2 3 5 5 6 6 8 9 11 13 15 17 18 18 20 22 22 24 26 26 26 26 27 27 27 28 30 32 32 33 34 34 34 36 36 38 38 38 39 39 44 24 0 2 3 5 7 9 9 10 11 12 13 14 14 14 14 15 1...
output:
30720 0 0 0 0 0 24576 0 0 0 0 0 658159182 0 805306368 8 572589350 12288 2 0 981283070 0 0 2 0 0 0 0 4423680 0 0 14155776 16 0 768 0 0 0 855189487 0 2 0 0 0 0 2 0 2 797370259 0 0 0 0 4 0 0 0 301989888 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 192 0 0 12288 0 0 2 8 0 0 495514526 0 0 955131071 768 0 0 147456...
result:
wrong answer 1st lines differ - expected: '0', found: '30720'