QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#573299	#9353. Interesting Permutation	whyhere	AC ✓	96ms	4424kb	C++17	4.1kb	2024-09-18 18:05:06	2024-09-18 18:05:07

Judging History

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

[2024-09-18 18:05:07]
评测

测评结果：AC
用时：96ms
内存：4424kb

查看

[2024-09-18 18:05:06]
提交

answer

#include <bits/stdc++.h>
#define ll long long
using namespace std;
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
template <class T>
constexpr T power(T a, i64 b)
{
    T res{1};
    for (; b; b /= 2, a *= a)
    {
        if (b % 2)
        {
            res *= a;
        }
    }
    return res;
}

constexpr i64 mul(i64 a, i64 b, i64 p)
{
    i64 res = a * b - i64(1.L * a * b / p) * p;
    res %= p;
    if (res < 0)
    {
        res += p;
    }
    return res;
}

template <i64 P>
struct MInt
{
    i64 x;
    constexpr MInt() : x{0} {}
    constexpr MInt(i64 x) : x{norm(x % getMod())} {}

    static i64 Mod;
    constexpr static i64 getMod()
    {
        if (P > 0)
        {
            return P;
        }
        else
        {
            return Mod;
        }
    }
    constexpr static void setMod(i64 Mod_)
    {
        Mod = Mod_;
    }
    constexpr i64 norm(i64 x) const
    {
        if (x < 0)
        {
            x += getMod();
        }
        if (x >= getMod())
        {
            x -= getMod();
        }
        return x;
    }
    constexpr i64 val() const
    {
        return x;
    }
    constexpr MInt operator-() const
    {
        MInt res;
        res.x = norm(getMod() - x);
        return res;
    }
    constexpr MInt inv() const
    {
        return power(*this, getMod() - 2);
    }
    constexpr MInt &operator*=(MInt rhs) &
    {
        if (getMod() < (1ULL << 31))
        {
            x = x * rhs.x % int(getMod());
        }
        else
        {
            x = mul(x, rhs.x, getMod());
        }
        return *this;
    }
    constexpr MInt &operator+=(MInt rhs) &
    {
        x = norm(x + rhs.x);
        return *this;
    }
    constexpr MInt &operator-=(MInt rhs) &
    {
        x = norm(x - rhs.x);
        return *this;
    }
    constexpr MInt &operator/=(MInt rhs) &
    {
        return *this *= rhs.inv();
    }
    friend constexpr MInt operator*(MInt lhs, MInt rhs)
    {
        MInt res = lhs;
        res *= rhs;
        return res;
    }
    friend constexpr MInt operator+(MInt lhs, MInt rhs)
    {
        MInt res = lhs;
        res += rhs;
        return res;
    }
    friend constexpr MInt operator-(MInt lhs, MInt rhs)
    {
        MInt res = lhs;
        res -= rhs;
        return res;
    }
    friend constexpr MInt operator/(MInt lhs, MInt rhs)
    {
        MInt res = lhs;
        res /= rhs;
        return res;
    }
    friend constexpr std::istream &operator>>(std::istream &is, MInt &a)
    {
        i64 v;
        is >> v;
        a = MInt(v);
        return is;
    }
    friend constexpr std::ostream &operator<<(std::ostream &os, const MInt &a)
    {
        return os << a.val();
    }
    friend constexpr bool operator==(MInt lhs, MInt rhs)
    {
        return lhs.val() == rhs.val();
    }
    friend constexpr bool operator!=(MInt lhs, MInt rhs)
    {
        return lhs.val() != rhs.val();
    }
    friend constexpr bool operator<(MInt lhs, MInt rhs)
    {
        return lhs.val() < rhs.val();
    }
};

template <>
i64 MInt<0>::Mod = 1000000007;

constexpr int P = 1000000007;
using Z = MInt<P>;

void _Z()
{
    int n;
    cin >> n;
    vector<Z> h(n);
    for (int i = 0;i < n;i ++)
    {
        cin >> h[i];
    }
    Z ans = 1;
    if (h[0] != 0)
    {
        ans = 0;
        cout << ans <<"\n";
        return;
    }
    for (int i = 1;i < n;i ++)
    {
        if (i == n - 1 && h[i] != n - 1)
        {
            ans = 0;
            break;
        }
        if (h[i] < h[i - 1])
        {
            ans = 0;
            break;
        }
        if (h[i - 1] == h[i])
        {
            ans *= h[i] + 1 - i;
        }
        else
        {
            ans *= 2;
        }
    }
    cout << ans << "\n";
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(15);

    int t = 1;
    cin >> t;
    while (t--)
    {
        _Z();
    }
    return 0;
}

源文件, 语言: C++17

这程序好像有点Bug，我给组数据试试？

详细

Test #1:

score: 100

Accepted

time: 1ms

memory: 3612kb

input:

output:

2
4
0

result:

ok 3 lines

Test #2:

score: 0

Accepted

time: 63ms

memory: 4264kb

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:

result:

ok 10039 lines

Test #3:

score: 0

Accepted

time: 96ms

memory: 4424kb

input:

20
100000
0 1 2 3 5 6 7 9 10 10 12 12 12 13 14 15 17 17 18 19 21 22 24 26 28 28 28 28 29 31 32 34 35 36 38 39 39 39 41 41 42 44 45 47 48 49 51 53 54 56 58 58 58 60 62 62 64 64 64 66 66 66 66 68 70 70 71 72 72 74 74 75 76 77 77 78 80 80 82 82 84 85 86 86 88 88 89 90 91 91 93 93 95 97 98 100 101 103 1...

output:

result:

ok 20 lines

Test #4:

score: 0

Accepted

time: 1ms

memory: 3576kb

input:

1
14
5 6 7 8 9 10 11 12 13 13 13 13 13 13

output:

result:

ok single line: '0'

Test #5:

score: 0

Accepted

time: 0ms

memory: 3584kb

input:

1
14
0 5 6 7 8 9 10 11 12 13 14 14 14 14

output:

result:

ok single line: '0'

Test #6:

score: 0

Accepted

time: 1ms

memory: 3532kb

input:

1
1
1

output:

result:

ok single line: '0'

Test #7:

score: 0

Accepted

time: 0ms

memory: 3580kb

input:

1
14
0 5 4 8 9 10 11 12 13 13 13 13 13 13

output:

result:

ok single line: '0'

Extra Test:

score: 0

Extra Test Passed