QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#227071#4842. Rectangle PlacementJerryBlack_ZJNUAC ✓1ms3512kbC++205.1kb2023-10-26 20:55:492023-10-26 20:55:49

Judging History

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

  • [2023-10-26 20:55:49]
  • 评测
  • 测评结果:AC
  • 用时:1ms
  • 内存:3512kb
  • [2023-10-26 20:55:49]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;

#define endl '\n'
#define ll long long
#define fi first
#define se second
#define lowbit(x) (x&(-x))
const int mod=998244353;
const double eps=1e-12;
const int inf=0x3f3f3f3f;
const ll INF=0x3f3f3f3f3f3f3f3f;
#define popcnt __builtin_popcount
int dcmp(double x){if(fabs(x)<eps)return 0;return x>0?1:-1;}

// #define int ll

template<typename T>
int normalize(T value, int mod) {
    if (value < -mod || value >= 2 * mod) value %= mod;
    if (value < 0) value += mod;
    if (value >= mod) value -= mod;
    return value;
}
 
template<int mod>
struct static_modular_int {
    using mint = static_modular_int<mod>;
 
    int value;
 
    static_modular_int() : value(0) {}
    static_modular_int(const mint &x) : value(x.value) {}
 
    template<typename T, typename U = std::enable_if_t<std::is_integral<T>::value>>
    static_modular_int(T value) : value(normalize(value, mod)) {}
 
    template<typename T>
    mint power(T degree) const {
        degree = normalize(degree, mod - 1);
        mint prod = 1, a = *this;
        for (; degree > 0; degree >>= 1, a *= a)
            if (degree & 1)
                prod *= a;
 
        return prod;
    }
 
    mint inv() const {
        return power(-1);
    }
 
    mint& operator=(const mint &x) {
        value = x.value;
        return *this;
    }
 
    mint& operator+=(const mint &x) {
        value += x.value;
        if (value >= mod) value -= mod;
        return *this;
    }
 
    mint& operator-=(const mint &x) {
        value -= x.value;
        if (value < 0) value += mod;
        return *this;
    }
 
    mint& operator*=(const mint &x) {
        value = int64_t(value) * x.value % mod;
        return *this;
    }
 
    mint& operator/=(const mint &x) {
        return *this *= x.inv();
    }
 
    friend mint operator+(const mint &x, const mint &y) {
        return mint(x) += y;
    }
 
    friend mint operator-(const mint &x, const mint &y) {
        return mint(x) -= y;
    }
 
    friend mint operator*(const mint &x, const mint &y) {
        return mint(x) *= y;
    }
 
    friend mint operator/(const mint &x, const mint &y) {
        return mint(x) /= y;
    }
 
    mint& operator++() {
        ++value;
        if (value == mod) value = 0;
        return *this;
    }
 
    mint& operator--() {
        --value;
        if (value == -1) value = mod - 1;
        return *this;
    }
 
    mint operator++(int) {
        mint prev = *this;
        value++;
        if (value == mod) value = 0;
        return prev;
    }
 
    mint operator--(int) {
        mint prev = *this;
        value--;
        if (value == -1) value = mod - 1;
        return prev;
    }
 
    mint operator-() const {
        return mint(0) - *this;
    }
 
    bool operator==(const mint &x) const {
        return value == x.value;
    }
 
    bool operator!=(const mint &x) const {
        return value != x.value;
    }
 
    bool operator<(const mint &x) const {
        return value < x.value;
    }
 
    template<typename T>
    explicit operator T() {
        return value;
    }
 
    friend std::istream& operator>>(std::istream &in, mint &x) {
        std::string s;
        in >> s;
        x = 0;
        for (const auto c : s)
            x = x * 10 + (c - '0');
 
        return in;
    }
 
    friend std::ostream& operator<<(std::ostream &out, const mint &x) {
        return out << x.value;
    }
 
    static int primitive_root() {
        if constexpr (mod == 1000000007) return 5;
        if constexpr (mod == 998244353) return 3;
        if constexpr (mod == 786433) return 10;
 
        static int root = -1;
        if (root != -1)
            return root;
 
        std::vector<int> primes;
        int value = mod - 1;
        for (int i = 2; i * i <= value; i++)
            if (value % i == 0) {
                primes.push_back(i);
                while (value % i == 0)
                    value /= i;
            }
 
        if (value != 1) primes.push_back(value);
        for (int r = 2;; r++) {
            bool ok = true;
            for (auto p : primes) {
                if ((mint(r).power((mod - 1) / p)).value == 1) {
                    ok = false;
                    break;
                }
            }
            if (ok) return root = r;
        }
    }
};
 
// constexpr int MOD = 1000000007;
constexpr int MOD = 998244353;
using mint = static_modular_int<MOD>;

mint binom(mint n,mint m)
{
    mint res=1;
    for(mint i=0;i<m;i++)
    {
        res=res*(n-i)/(m-i);
    }
    return res;
}

void solve()
{
    mint n,m;
    cin>>n>>m;
    cout<<mint(11)*binom(n,4)*binom(m,4)+
          mint(6)*binom(n,4)*binom(m,3)+
          mint(6)*binom(n,3)*binom(m,4)+
          binom(n,4)*binom(m,2)+
          binom(n,2)*binom(m,4)<<endl;
}

/*

*/

#undef int

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



    // int _;cin>>_;while(_--)
    {
        solve();
    }
    return 0;
}

詳細信息

Test #1:

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

input:

4 5

output:

275

result:

ok 1 number(s): "275"

Test #2:

score: 0
Accepted
time: 1ms
memory: 3480kb

input:

723435135 239873451

output:

832099301

result:

ok 1 number(s): "832099301"

Test #3:

score: 0
Accepted
time: 1ms
memory: 3476kb

input:

10348683 1000000000

output:

959472414

result:

ok 1 number(s): "959472414"

Test #4:

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

input:

1000000000 886687075

output:

994294391

result:

ok 1 number(s): "994294391"

Test #5:

score: 0
Accepted
time: 1ms
memory: 3412kb

input:

238133469 977550485

output:

181382226

result:

ok 1 number(s): "181382226"

Test #6:

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

input:

895943525 1000000000

output:

574248092

result:

ok 1 number(s): "574248092"

Test #7:

score: 0
Accepted
time: 1ms
memory: 3408kb

input:

1000000000 772281920

output:

2306050

result:

ok 1 number(s): "2306050"

Test #8:

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

input:

123728314 859786182

output:

722858859

result:

ok 1 number(s): "722858859"

Test #9:

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

input:

76505681 1000000000

output:

94904116

result:

ok 1 number(s): "94904116"

Test #10:

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

input:

1000000000 952844073

output:

632222340

result:

ok 1 number(s): "632222340"

Test #11:

score: 0
Accepted
time: 1ms
memory: 3416kb

input:

599257776 36989190

output:

592333335

result:

ok 1 number(s): "592333335"

Test #12:

score: 0
Accepted
time: 1ms
memory: 3404kb

input:

257067834 1000000000

output:

520152555

result:

ok 1 number(s): "520152555"

Test #13:

score: 0
Accepted
time: 1ms
memory: 3392kb

input:

1000000000 133406229

output:

769022397

result:

ok 1 number(s): "769022397"

Test #14:

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

input:

484852621 919224885

output:

829749309

result:

ok 1 number(s): "829749309"

Test #15:

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

input:

437629987 1000000000

output:

388969627

result:

ok 1 number(s): "388969627"

Test #16:

score: 0
Accepted
time: 1ms
memory: 3396kb

input:

1000000000 313968382

output:

471013029

result:

ok 1 number(s): "471013029"

Test #17:

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

input:

665414774 326352585

output:

424688776

result:

ok 1 number(s): "424688776"

Test #18:

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

input:

1000000000 1000000000

output:

656213933

result:

ok 1 number(s): "656213933"

Test #19:

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

input:

4 4

output:

71

result:

ok 1 number(s): "71"

Test #20:

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

input:

4 1000000000

output:

946327704

result:

ok 1 number(s): "946327704"

Test #21:

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

input:

1000000000 4

output:

946327704

result:

ok 1 number(s): "946327704"