Submission #70197666

Source Code Expand

//utf-8  c++14
/*
+ - * / ^ io only, mod is prime, 2 * mod <= u32 max
*/
#include <cstdint>
#include <type_traits>
#include <limits>
#include <numeric>
#include <iostream>

#define ILCST inline constexpr
#define TMILCST template <u32 mod> ILCST
#define ILCSTMR ILCST modint&
#define NT noexcept

namespace modint_nm {

    using u32 = std::uint32_t;
    using u64 = std::uint64_t;
    using umx = std::uintmax_t;
    using i32 = std::int32_t;
    using imx = std::intmax_t;

    template <u32 mod, typename type, typename = void> struct modval_t
        { static ILCST u32 modval(type v) NT { return v % mod; } };
    template <u32 mod, typename type> struct modval_t <mod, type, std::enable_if_t<std::is_unsigned<type>::value> >
        { static ILCST u32 modval(type v) NT { return v % mod; } };
    template <u32 mod, typename type> struct modval_t <mod, type, std::enable_if_t<std::is_signed<type>::value> >
        { static ILCST u32 modval(type v) NT { v %= i32(mod);return v < 0? v + mod : v; } };
    template <u32 mod, typename type> struct modval_t <mod, type, std::enable_if_t<std::is_floating_point<type>::value> >
        { static ILCST u32 modval(type v) NT { return modval_t<mod, imx>::modval(imx(v)); } };
    template <u32 mod> struct modval_t <mod, __int128_t>
        { static ILCST u32 modval(__int128_t v) NT { v %= i32(mod);return v < 0? v + mod : v; } };
    template <u32 mod> struct modval_t <mod, __uint128_t>
        { static ILCST u32 modval(__uint128_t v) NT { return v % mod; } };

    TMILCST void modsplus(u32 &a, u32 b) NT { a += b;if (a >= mod)a -= mod; }
    TMILCST u32 modplus(u32 a, u32 b) NT { a += b;return a >= mod? a - mod : a; }

    TMILCST void modssubt(u32 &a, u32 b) NT { if (a < b)a += mod - b; else a -= b; }
    TMILCST u32 modsubt(u32 a, u32 b) NT { return a < b? a + (mod - b) : a - b; }

    TMILCST u32 modmult(u32 a, u32 b) NT { return u64(a) * b % mod; }
    TMILCST u32 modfpow(u32 a, umx b) NT
        { u32 ret = 1;for (; b; b >>= 1, a = modmult<mod>(a, a))if (b & 1)ret = modmult<mod>(ret, a);return ret; }

    // 假定值在模范围内，减少一次取模操作
    struct in_mod_range_t { } in_mod_range;

    template <u32> struct modint;

    template <u32 mod, typename _T>
        ILCST modint<mod> operator ^ (modint<mod> a, modint<mod - 1> b) NT;

    template <u32 mod_>
        struct modint {
            static constexpr u32 mod = mod_;
            typedef void is_modint_t;
            u32 val;
            ILCST modint() NT : val() { }
            template <typename Val_t> ILCST modint(Val_t Val) NT : val(modval_t<mod, Val_t>::modval(Val)) {}
            ILCST modint(const modint &) NT = default;
            ILCST modint(modint &&) NT = default;
            ILCST modint(in_mod_range_t, u32 v) NT : val{v} {}
            template <typename Val_t> ILCST modint &operator = (Val_t Val) NT
                { val = modval_t<mod, Val_t>::modval(Val);return *this; }
            ILCSTMR operator = (const modint &) NT = default;
            ILCSTMR operator = (modint &&) NT = default;
            ILCSTMR operator += (modint o) NT { modsplus<mod>(val, o.val);return *this; }
            ILCSTMR operator -= (modint o) NT { modssubt<mod>(val, o.val);return *this; }
            ILCSTMR operator *= (modint o) NT { val = modmult<mod>(val, o.val);return *this; }
            ILCSTMR operator ^= (modint<mod - 1> o) NT
                { val = modfpow<mod>(val, modint<mod - 1>(o).value());return *this; }
            ILCST modint operator - () const NT { return modint(in_mod_range, val? mod - val : 0u); }
            ILCST modint inv() const NT { return (*this) ^ (mod - 2); }
            ILCSTMR operator /= (modint o) NT { val = modmult<mod>(val, o.inv().val);return *this; }
            ILCST u32 value() const NT { return val; }
            ILCST operator u32 () const NT { return val; }
            template <typename _Tp> ILCST operator _Tp () const NT { return (_Tp)val; }

            ILCSTMR plussubt(bool v, modint x) NT //+=(-1)^v*x
                { if (v)*this -= x; else *this += x; return *this; }
            template <typename _Tp, typename = std::enable_if_t<std::is_integral<_Tp>::value> >
                ILCSTMR plussubt(_Tp v, modint x) NT //+=(-1)^v*x
                    { if (v & 1)*this -= x; else *this += x; return *this; }

            static constexpr modint nan = modint(in_mod_range, mod);

        }; // __is_trivially_copyable(modint<...>) = true

    template <u32 mod> constexpr u32 modint<mod>::mod;
    template <u32 mod> constexpr modint<mod> modint<mod>::nan;

    #define DEFOPT(opt, expr)\
        TMILCST modint<mod> operator opt (modint<mod> a, modint<mod> b) NT\
            { return modint<mod>(in_mod_range, expr); }\
        template <u32 mod, typename _T> ILCST modint<mod> operator opt (_T a, modint<mod> b) NT\
            { return modint<mod>(a) opt b; }\
        template <u32 mod, typename _T> ILCST modint<mod> operator opt (modint<mod> a, _T b) NT\
            { return a opt modint<mod>(b); }

    DEFOPT(+, modplus<mod>(a.val, b.val))
    DEFOPT(-, modsubt<mod>(a.val, b.val))
    DEFOPT(*, modmult<mod>(a.val, b.val))
    DEFOPT(/, modmult<mod>(a.val, b.inv().val))

    TMILCST modint<mod> operator ^ (modint<mod> a, modint<mod - 1> b) NT
        { return modint<mod>(in_mod_range, modfpow<mod>(a.val, modint<mod - 1>(b).value())); }

    TMILCST modint<mod> fma(modint<mod> a, modint<mod> b, modint<mod> c) NT
        { return modint<mod>(in_mod_range, (u64(a.val) * b.val + c.val) % mod); }

    template <u32 mod> // a += b * c
        ILCST void splusmult(modint<mod> &a, modint<mod> b, modint<mod> c) NT { a = fma(b, c, a); }

    template <typename iter_t>
        using is_modint_iter = std::enable_if_t<std::is_base_of<std::random_access_iterator_tag,
            typename std::iterator_traits<iter_t>::iterator_category>::value, typename std::iterator_traits<iter_t>::value_type::is_modint_t>;

    template <typename iter_t, typename = is_modint_iter<iter_t> >
        constexpr void calc_fact(u32 n, iter_t fc){//let fc_i = i!, 0<=i<n
            if (n == 0)return;
            *fc = 1;
            for (u32 i = 1; i < n; ++i)fc[i] = fc[i - 1] * i;
        }

    inline namespace predefine_modint {
        using modp0 = modint<998244353>;
        using modp1 = modint<1000000007>;
    }

}

namespace std {

    using u32 = std::uint32_t;
    using u64 = std::uint64_t;

    template <u32 mod> ostream &operator << (ostream &os, modint_nm::modint<mod> v){ return os << v.value(); }
    template <u32 mod> istream &operator >> (istream &is, modint_nm::modint<mod> &v){ u64 x;is >> x;v = x;return is; }

}

#include <bits/stdc++.h>
using namespace std;
using mod = modint_nm::modp0;
mod fc[3010];
int n;
bool b[3010];//b_i? i<-p_i : i->p_i
int p[3010];//i-p_i
int main(){
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n;
    {//calc `p`, `b`
        static int a[3010], b[3010], c[3010];
        for (int i = 1; i <= n; ++i)cin >> a[i], c[(a[i] + 1) >> 1] = i;
        if (count(c + 1, c + n + 1, 0)){
            cout << 0 << endl;
            return 0;
        }
        for (int i = 1; i <= n; ++i)cin >> b[i];
        for (int i = 1; i <= n; ++i){
            ::b[i] = a[c[i]] & 1;
            p[i] = b[c[i]] == -1? 0 : (b[c[i]] + 1 >> 1);
        }
    }
    int c0 = 0, c1 = 0, c2 = 0;//count only =0, only =1, both
    {//calc `c0,c1,c2`
        static bool v[3010];
        fill_n(v + 1, n, 0);
        for (int i = 1; i <= n; ++i)v[p[i]] = 1;
        static bool vs[3010];
        fill_n(vs + 1, n, 0);
        for (int i = 1; i <= n; ++i)if (!v[i]){//enum lists
            int ms = 0;
            for (int u = i; u; u = p[u])vs[u] = 1, ms |= 1 << ::b[u];
            ++(ms == 1? c0 : ms == 2? c1 : c2);
        }
        for (int i = 1; i <= n; ++i)if (!vs[i]){
            int ms = 0;
            for (int u = i; !vs[u]; u = p[u])vs[u] = 1, ms |= 1 << ::b[u];
            if (ms < 3){
                cout << 0 << endl;
                return 0;
            }
        }
    }
    modint_nm::calc_fact(n + 1, fc);
    constexpr mod f[2]{1, -1};
    mod rs = 0;
    for (int i = 0; i <= 1 && i <= c0; ++i)
        for (int j = 0; j <= 1 && j <= c1; ++j)
            rs += (i? c0 : 1) * (j? c1 : 1) * f[i] * f[j] * fc[c0 - i + c1 - j + c2];
    cout << rs << endl;
    return 0;
}

Submission Info

Submission Time
Task D - Mirror and Order
User szt100309
Language C++ 20 (gcc 12.2)
Score 1000
Code Size 8549 Byte
Status AC
Exec Time 2 ms
Memory 3696 KiB

Compile Error

Main.cpp: In function ‘int main()’:
Main.cpp:164:48: warning: suggest parentheses around ‘+’ inside ‘>>’ [-Wparentheses]
  164 |             p[i] = b[c[i]] == -1? 0 : (b[c[i]] + 1 >> 1);
      |                                        ~~~~~~~~^~~

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 1000 / 1000
Status
AC × 2
AC × 49
Set Name Test Cases
Sample sample-01.txt, sample-02.txt
All in-01.txt, in-02.txt, in-03.txt, in-04.txt, in-05.txt, in-06.txt, in-07.txt, in-08.txt, in-09.txt, in-10.txt, in-11.txt, in-12.txt, in-13.txt, in-14.txt, in-15.txt, in-16.txt, in-17.txt, in-18.txt, in-19.txt, in-20.txt, in-21.txt, in-22.txt, in-23.txt, in-24.txt, in-25.txt, in-26.txt, in-27.txt, in-28.txt, in-29.txt, in-30.txt, in-31.txt, in-32.txt, in-33.txt, in-34.txt, in-35.txt, in-36.txt, in-37.txt, in-38.txt, in-39.txt, in-40.txt, in-41.txt, in-42.txt, in-43.txt, in-44.txt, in-45.txt, in-46.txt, in-47.txt, sample-01.txt, sample-02.txt
Case Name Status Exec Time Memory
in-01.txt AC 1 ms 3448 KiB
in-02.txt AC 1 ms 3516 KiB
in-03.txt AC 2 ms 3692 KiB
in-04.txt AC 2 ms 3468 KiB
in-05.txt AC 1 ms 3464 KiB
in-06.txt AC 1 ms 3424 KiB
in-07.txt AC 1 ms 3572 KiB
in-08.txt AC 1 ms 3500 KiB
in-09.txt AC 1 ms 3576 KiB
in-10.txt AC 1 ms 3492 KiB
in-11.txt AC 2 ms 3548 KiB
in-12.txt AC 2 ms 3492 KiB
in-13.txt AC 1 ms 3464 KiB
in-14.txt AC 1 ms 3504 KiB
in-15.txt AC 2 ms 3620 KiB
in-16.txt AC 2 ms 3584 KiB
in-17.txt AC 2 ms 3648 KiB
in-18.txt AC 1 ms 3584 KiB
in-19.txt AC 2 ms 3484 KiB
in-20.txt AC 2 ms 3496 KiB
in-21.txt AC 1 ms 3588 KiB
in-22.txt AC 1 ms 3560 KiB
in-23.txt AC 1 ms 3488 KiB
in-24.txt AC 1 ms 3540 KiB
in-25.txt AC 2 ms 3696 KiB
in-26.txt AC 2 ms 3584 KiB
in-27.txt AC 1 ms 3632 KiB
in-28.txt AC 2 ms 3560 KiB
in-29.txt AC 1 ms 3440 KiB
in-30.txt AC 2 ms 3468 KiB
in-31.txt AC 1 ms 3604 KiB
in-32.txt AC 1 ms 3512 KiB
in-33.txt AC 1 ms 3492 KiB
in-34.txt AC 2 ms 3636 KiB
in-35.txt AC 1 ms 3560 KiB
in-36.txt AC 1 ms 3444 KiB
in-37.txt AC 1 ms 3564 KiB
in-38.txt AC 1 ms 3556 KiB
in-39.txt AC 1 ms 3560 KiB
in-40.txt AC 1 ms 3456 KiB
in-41.txt AC 1 ms 3432 KiB
in-42.txt AC 1 ms 3648 KiB
in-43.txt AC 1 ms 3504 KiB
in-44.txt AC 1 ms 3544 KiB
in-45.txt AC 1 ms 3636 KiB
in-46.txt AC 2 ms 3492 KiB
in-47.txt AC 2 ms 3540 KiB
sample-01.txt AC 1 ms 3432 KiB
sample-02.txt AC 1 ms 3452 KiB