QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#575546#9353. Interesting Permutationlqh2024#WA 60ms4660kbC++172.7kb2024-09-19 15:16:522024-09-19 15:16:52

Judging History

你现在查看的是最新测评结果

  • [2024-09-19 15:16:52]
  • 评测
  • 测评结果:WA
  • 用时:60ms
  • 内存:4660kb
  • [2024-09-19 15:16:52]
  • 提交

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'