QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#725134#9477. Topological Sortnan01WA 0ms3812kbC++234.3kb2024-11-08 16:24:132024-11-08 16:24:13

Judging History

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

  • [2024-11-08 16:24:13]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3812kb
  • [2024-11-08 16:24:13]
  • 提交

answer

#include <bits/stdc++.h>
#define rep(i, a, n) for (int i = a; i <= n; i++)
#define per(i, a, n) for (int i = n; i >= a; i--)
#define ll long long
#define pii pair<int, int>
#define inf 0x3f3f3f3f
#define fi first
#define pll pair<ll, ll>
#define se second
#define lll __int128
#define ld long double
#define all(a) a.begin() + 1, a.end()
#define iofast                   \
    ios::sync_with_stdio(false); \
    cin.tie(0), cout.tie(0)
#define lowbit(i) (i & (-i))
using namespace std;
const int maxn = 1e6 + 5, mod = 1000000007;
class bit
{
public:
    ll b[maxn];
    int n; // 记得初始化
    void add(int x, int add)
    {
        for (int i = x; i <= n; i += lowbit(i))
        {
            b[i] += add;
        }
    }
    ll s(int a)
    {
        ll ans = 0;
        for (int i = a; i > 0; i -= lowbit(i))
        {
            ans += b[i];
        }
        return ans;
    }
    ll query(int l, int r)
    {
        return s(r) - s(l - 1);
    }
} bit;
// modint
template <int MOD>
struct Fp
{
    ll val;
    Fp(ll v = 0) : val(v % MOD)
    {
        if (val < 0)
            val += MOD;
    }
    int getmod() const { return MOD; }
    Fp operator-() const { return val ? MOD - val : 0; }
    Fp operator+(const Fp &r) const { return Fp(*this) += r; }
    Fp operator-(const Fp &r) const { return Fp(*this) -= r; }
    Fp operator*(const Fp &r) const { return Fp(*this) *= r; }
    Fp operator/(const Fp &r) const { return Fp(*this) /= r; }
    Fp &operator+=(const Fp &r)
    {
        val += r.val;
        if (val >= MOD)
            val -= MOD;
        return *this;
    }
    Fp &operator-=(const Fp &r)
    {
        val -= r.val;
        if (val < 0)
            val += MOD;
        return *this;
    }
    Fp &operator*=(const Fp &r)
    {
        val = val * r.val % MOD;
        return *this;
    }
    Fp &operator/=(const Fp &r)
    {
        ll a = r.val, b = MOD, u = 1, v = 0;
        while (b)
        {
            ll t = a / b;
            a -= t * b, swap(a, b);
            u -= t * v, swap(u, v);
        }
        val = val * u % MOD;
        if (val < 0)
            val += MOD;
        return *this;
    }
    bool operator<(const Fp &r) const { return this->val < r.val; }
    bool operator==(const Fp &r) const { return this->val == r.val; }
    bool operator!=(const Fp &r) const { return this->val != r.val; }
    friend istream &operator>>(istream &is, Fp<MOD> &x)
    {
        is >> x.val;
        x.val %= MOD;
        if (x.val < 0)
            x.val += MOD;
        return is;
    }
    friend ostream &operator<<(ostream &os, const Fp<MOD> &x) { return os << x.val; }
    friend Fp<MOD> modpow(const Fp<MOD> &r, ll n)
    {
        if (n == 0)
            return 1;
        if (n < 0)
            return modpow(modinv(r), -n);
        Fp<MOD> t = modpow(r, n / 2);
        t = t * t;
        if (n & 1)
            t = t * r;
        return t;
    }
    friend Fp<MOD> modinv(const Fp<MOD> &r)
    {
        ll a = r.val, b = MOD, u = 1, v = 0;
        while (b)
        {
            ll t = a / b;
            a -= t * b, swap(a, b);
            u -= t * v, swap(u, v);
        }
        return Fp<MOD>(u);
    }
};
const int MOD = 998244353; // 看取得哪个模!!!!!!!!!!!
typedef Fp<MOD> mint;
mint qkpow(mint a, ll p = MOD - 2)
{
    mint t = 1, tt = a;
    while (p)
    {
        if (p & 1)
            t = t * tt;
        tt = tt * tt;
        p >>= 1;
    }
    return t;
}
void solve()
{
    int n;
    cin >> n;
    mint ans = 1;
    bit.n = n;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
    stack<int> stk;
    vector<int> in(n + 1);
    int mx = 0;
    a.push_back(inf);
    for (int i = 1; i <= n; i++)
    {
        if (mx > a[i] && !in[i])
        {
            ans *= qkpow(2);
        }
        mx = max(mx, a[i]);
        if (a[i] > a[i + 1])
        {
            ans *= qkpow(2, n - i - 1);
            in[i + 1]++;
        }
        else
            ans *= qkpow(2, n - i);
    }
    cout << ans << endl;
}
int main()
{
    iofast;
    int t = 1;
    // cin >> t;
    while (t--)
        solve();
    // cout << endl;
    //  system("pause");
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 3812kb

input:

3
1 3 2

output:

4

result:

ok "4"

Test #2:

score: 0
Accepted
time: 0ms
memory: 3588kb

input:

5
1 2 3 4 5

output:

1024

result:

ok "1024"

Test #3:

score: 0
Accepted
time: 0ms
memory: 3604kb

input:

6
4 2 1 5 6 3

output:

4096

result:

ok "4096"

Test #4:

score: -100
Wrong Answer
time: 0ms
memory: 3628kb

input:

492
397 486 227 395 58 452 172 216 130 181 268 482 85 209 365 104 373 90 260 326 252 96 267 106 102 398 441 41 292 314 12 78 242 353 153 424 179 86 299 228 54 390 73 465 396 349 4 10 451 99 342 250 391 6 323 197 159 47 136 473 392 77 125 362 418 255 291 13 238 339 8 28 413 121 384 157 152 23 221 305...

output:

390557336

result:

wrong answer 1st words differ - expected: '73428942', found: '390557336'