QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#75460#5456. Big Picturerin204AC ✓195ms10964kbC++1712.6kb2023-02-05 11:58:232023-02-05 11:58:27

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-02-05 11:58:27]
  • 评测
  • 测评结果:AC
  • 用时:195ms
  • 内存:10964kb
  • [2023-02-05 11:58:23]
  • 提交

answer

#line 1 "A.cpp"
// #pragma GCC target("avx2")
// #pragma GCC optimize("O3")
// #pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>
using namespace std;

using ll = long long;
using ull = unsigned long long;
template <class T>
using pq = priority_queue<T>;
template <class T>
using qp = priority_queue<T, vector<T>, greater<T>>;
#define vec(T, A, ...) vector<T> A(__VA_ARGS__);
#define vvec(T, A, h, ...) vector<vector<T>> A(h, vector<T>(__VA_ARGS__));
#define vvvec(T, A, h1, h2, ...) vector<vector<vector<T>>> A(h1, vector<vector<T>>(h2, vector<T>(__VA_ARGS__)));

#define endl "\n"
#define spa ' '
#define len(A) A.size()
#define all(A) begin(A), end(A)

#define fori1(a) for(ll _ = 0; _ < (a); _++)
#define fori2(i, a) for(ll i = 0; i < (a); i++)
#define fori3(i, a, b) for(ll i = (a); i < (b); i++)
#define fori4(i, a, b, c) for(ll i = (a); ((c) > 0 || i > (b)) && ((c) < 0 || i < (b)); i += (c))
#define overload4(a, b, c, d, e, ...) e
#define fori(...) overload4(__VA_ARGS__, fori4, fori3, fori2, fori1)(__VA_ARGS__)

template <typename T>
vector<tuple<ll, T>> ENUMERATE(vector<T> &A, ll s = 0){
    vector<tuple<ll, T>> ret(A.size());
    for(int i = 0; i < A.size(); i++) ret[i] = {i + s, A[i]};
    return ret;
}

vector<tuple<ll, char>> ENUMERATE(string &A, ll s = 0){
    vector<tuple<ll, char>> ret(A.size());
    for(int i = 0; i < A.size(); i++) ret[i] = {i + s, A[i]};
    return ret;
}

#define enum1(A) fori(A.size())
#define enum2(a, A) for(auto a:A)
#define enum3(i, a, A) for(auto&& [i, a]: ENUMERATE(A))
#define enum4(i, a, A, s) for(auto&& [i, a]: ENUMERATE(A, s))
#define enum(...) overload4(__VA_ARGS__, enum4, enum3, enum2, enum1)(__VA_ARGS__)

template <typename T, typename S>
vector<tuple<T, S>> ZIP(vector<T> &A, vector<S> &B){
    int n = min(A.size(), B.size());
    vector<tuple<T, S>> ret(n);
    for(int i = 0; i < n; i++) ret[i] = {A[i], B[i]};
    return ret;
}

template <typename T, typename S>
vector<tuple<ll, T, S>> ENUMZIP(vector<T> &A, vector<S> &B, ll s = 0){
    int n = min(A.size(), B.size());
    vector<tuple<ll, T, S>> ret(n);
    for(int i = 0; i < n; i++) ret[i] = {i + s, A[i], B[i]};
    return ret;
}

#define zip4(a, b, A, B) for(auto&& [a, b]: ZIP(A, B))
#define enumzip5(i, a, b, A, B) for(auto&& [i, a, b]: ENUMZIP(A, B))
#define enumzip6(i, a, b, A, B, s) for(auto&& [i, a, b]: ENUMZIP(A, B, s))
#define overload6(a, b, c, d, e, f, g, ...) g
#define zip(...) overload6(__VA_ARGS__, enumzip6, enumzip5, zip4, _, _, _)(__VA_ARGS__)

vector<char> stoc(string &S){
    int n = S.size();
    vector<char> ret(n);
    for(int i = 0; i < n; i++) ret[i] = S[i];
    return ret;
}

#define INT(...) int __VA_ARGS__; inp(__VA_ARGS__);
#define LL(...) ll __VA_ARGS__; inp(__VA_ARGS__);
#define STRING(...) string __VA_ARGS__; inp(__VA_ARGS__);
#define CHAR(...) char __VA_ARGS__; inp(__VA_ARGS__);
#define VEC(T, A, n) vector<T> A(n); inp(A);
#define VVEC(T, A, n, m) vector<vector<T>> A(n, vector<T>(m)); inp(A);

const ll MOD1 = 1000000007;
const ll MOD9 = 998244353;

template<class T> auto min(const T& a){
    return *min_element(all(a));
}
template<class T> auto max(const T& a){
    return *max_element(all(a));
}
template <class T, class S>
inline bool chmax(T &a, const S &b) {
  return (a < b ? a = b, 1 : 0);
}
template <class T, class S>
inline bool chmin(T &a, const S &b) {
  return (a > b ? a = b, 1 : 0);
}

void FLUSH(){cout << flush;}
void print(){cout << endl;}
template <class Head, class... Tail>
void print(Head &&head, Tail &&... tail) {
    cout << head;
    if (sizeof...(Tail)) cout << spa;
    print(forward<Tail>(tail)...);
}
template<typename T>
void print(vector<T> &A){
    int n = A.size();
    for(int i = 0; i < n; i++){
        cout << A[i];
        if(i == n - 1) cout << endl;
        else cout << spa;
    }
}
template<typename T>
void print(vector<vector<T>> &A){
    for(auto &row: A) print(row);
}
template<typename T, typename S>
void print(pair<T, S> &A){
    cout << A.first << spa << A.second << endl;
}
template<typename T, typename S>
void print(vector<pair<T, S>> &A){
    for(auto &row: A) print(row);
}
template<typename T, typename S>
void prisep(vector<T> &A, S sep){
    int n = A.size();
    for(int i = 0; i < n; i++){
        cout << A[i];
        if(i == n - 1) cout << endl;
        else cout << sep;
    }
}
template<typename T, typename S>
void priend(T A, S end){
    cout << A << end;
}
template<typename T>
void priend(T A){
    priend(A, spa);
}
template<class... T>
void inp(T&... a){
    (cin >> ... >> a);
}
template<typename T>
void inp(vector<T> &A){
    for(auto &a:A) cin >> a;
}
template<typename T>
void inp(vector<vector<T>> &A){
    for(auto &row:A) inp(row);
}
template<typename T, typename S>
void inp(pair<T, S> &A){
    inp(A.first, A.second);
}
template<typename T, typename S>
void inp(vector<pair<T, S>> &A){
    for(auto &row: A) inp(row.first, row.second);
}

template<typename T>
T sum(vector<T> &A){
    T tot = 0;
    for(auto a:A) tot += a;
    return tot;
}

template<typename T>
pair<vector<T>, map<T, int>> compression(vector<T> X){
    sort(all(X));
    X.erase(unique(all(X)), X.end());
    map<T, int> mp;
    for(int i = 0; i < X.size(); i++) mp[X[i]] = i;
    return {X, mp};
}

#line 2 "Library/C++/other/Modint.hpp"

template<int MOD>
struct Modint{
    int x;
    Modint() : x(0){}
    Modint(int64_t y){
        if(y >= 0) x = y % MOD;
        else x = (y % MOD + MOD) % MOD;
    }

    Modint &operator+=(const Modint &p){
        x += p.x;
        if(x >= MOD) x -= MOD;
        return *this;
    }

    Modint &operator-=(const Modint &p){
        x -= p.x;
        if(x < 0) x += MOD;
        return *this;
    }

    Modint &operator*=(const Modint &p){
        x = int(1LL * x * p.x % MOD);
        return *this;
    }

    Modint &operator/=(const Modint &p){
        *this *= p.inverse();
        return *this;
    }

    Modint &operator%=(const Modint &p){
        assert(p.x == 0);
        return *this;
    }

    Modint operator-() const{
        return Modint(-x);
    }

    Modint& operator++() {
        x++;
        if (x == MOD) x = 0;
        return *this;
    }

    Modint& operator--() {
        if (x == 0) x = MOD;
        x--;
        return *this;
    }

    Modint operator++(int) {
        Modint result = *this;
        ++*this;
        return result;
    }

    Modint operator--(int) {
        Modint result = *this;
        --*this;
        return result;
    }

    friend Modint operator+(const Modint &lhs, const Modint &rhs){
        return Modint(lhs) += rhs;
    }

    friend Modint operator-(const Modint &lhs, const Modint &rhs){
        return Modint(lhs) -= rhs;
    }

    friend Modint operator*(const Modint &lhs, const Modint &rhs){
        return Modint(lhs) *= rhs;
    }

    friend Modint operator/(const Modint &lhs, const Modint &rhs){
        return Modint(lhs) /= rhs;
    }

    friend Modint operator%(const Modint &lhs, const Modint &rhs){
        assert(rhs.x == 0);
        return Modint(lhs);
    }

    bool operator==(const Modint &p) const{
        return x == p.x;
    }

    bool operator!=(const Modint &p) const{
        return x != p.x;
    }

    bool operator<(const Modint &rhs) {
        return x < rhs.x;
    }

    bool operator<=(const Modint &rhs) {
        return x <= rhs.x;
    }

    bool operator>(const Modint &rhs) {
        return x > rhs.x;
    }

    bool operator>=(const Modint &rhs) {
        return x >= rhs.x;
    }

    Modint inverse() const{
        int a = x, b = MOD, u = 1, v = 0, t;
        while(b > 0){
            t = a / b;
            a -= t * b;
            u -= t * v;
            swap(a, b);
            swap(u, v);
        }
        return Modint(u);
    }

    Modint pow(int64_t k) const{
        Modint ret(1);
        Modint y(x);
        while(k > 0){
            if(k & 1) ret *= y;
            y *= y;
            k >>= 1;
        }
        return ret;
    }

    friend ostream &operator<<(ostream &os, const Modint &p){
        return os << p.x;
    }

    friend istream &operator>>(istream &is, Modint &p){
        int64_t y;
        is >> y;
        p = Modint<MOD>(y);
        return (is);
    }

    static int get_mod(){
        return MOD;
    }
};

struct Arbitrary_Modint{
    int x;
    static int MOD;

    static void set_mod(int mod){
        MOD = mod;
    }

    Arbitrary_Modint() : x(0){}
    Arbitrary_Modint(int64_t y){
        if(y >= 0) x = y % MOD;
        else x = (y % MOD + MOD) % MOD;
    }

    Arbitrary_Modint &operator+=(const Arbitrary_Modint &p){
        x += p.x;
        if(x >= MOD) x -= MOD;
        return *this;
    }

    Arbitrary_Modint &operator-=(const Arbitrary_Modint &p){
        x -= p.x;
        if(x < 0) x += MOD;
        return *this;
    }

    Arbitrary_Modint &operator*=(const Arbitrary_Modint &p){
        x = int(1LL * x * p.x % MOD);
        return *this;
    }

    Arbitrary_Modint &operator/=(const Arbitrary_Modint &p){
        *this *= p.inverse();
        return *this;
    }

    Arbitrary_Modint &operator%=(const Arbitrary_Modint &p){
        assert(p.x == 0);
        return *this;
    }

    Arbitrary_Modint operator-() const{
        return Arbitrary_Modint(-x);
    }

    Arbitrary_Modint& operator++() {
        x++;
        if (x == MOD) x = 0;
        return *this;
    }

    Arbitrary_Modint& operator--() {
        if (x == 0) x = MOD;
        x--;
        return *this;
    }

    Arbitrary_Modint operator++(int) {
        Arbitrary_Modint result = *this;
        ++*this;
        return result;
    }

    Arbitrary_Modint operator--(int) {
        Arbitrary_Modint result = *this;
        --*this;
        return result;
    }

    friend Arbitrary_Modint operator+(const Arbitrary_Modint &lhs, const Arbitrary_Modint &rhs){
        return Arbitrary_Modint(lhs) += rhs;
    }

    friend Arbitrary_Modint operator-(const Arbitrary_Modint &lhs, const Arbitrary_Modint &rhs){
        return Arbitrary_Modint(lhs) -= rhs;
    }

    friend Arbitrary_Modint operator*(const Arbitrary_Modint &lhs, const Arbitrary_Modint &rhs){
        return Arbitrary_Modint(lhs) *= rhs;
    }

    friend Arbitrary_Modint operator/(const Arbitrary_Modint &lhs, const Arbitrary_Modint &rhs){
        return Arbitrary_Modint(lhs) /= rhs;
    }

    friend Arbitrary_Modint operator%(const Arbitrary_Modint &lhs, const Arbitrary_Modint &rhs){
        assert(rhs.x == 0);
        return Arbitrary_Modint(lhs);
    }

    bool operator==(const Arbitrary_Modint &p) const{
        return x == p.x;
    }

    bool operator!=(const Arbitrary_Modint &p) const{
        return x != p.x;
    }

    bool operator<(const Arbitrary_Modint &rhs) {
        return x < rhs.x;
    }

    bool operator<=(const Arbitrary_Modint &rhs) {
        return x <= rhs.x;
    }

    bool operator>(const Arbitrary_Modint &rhs) {
        return x > rhs.x;
    }

    bool operator>=(const Arbitrary_Modint &rhs) {
        return x >= rhs.x;
    }

    Arbitrary_Modint inverse() const{
        int a = x, b = MOD, u = 1, v = 0, t;
        while(b > 0){
            t = a / b;
            a -= t * b;
            u -= t * v;
            swap(a, b);
            swap(u, v);
        }
        return Arbitrary_Modint(u);
    }

    Arbitrary_Modint pow(int64_t k) const{
        Arbitrary_Modint ret(1);
        Arbitrary_Modint y(x);
        while(k > 0){
            if(k & 1) ret *= y;
            y *= y;
            k >>= 1;
        }
        return ret;
    }

    friend ostream &operator<<(ostream &os, const Arbitrary_Modint &p){
        return os << p.x;
    }

    friend istream &operator>>(istream &is, Arbitrary_Modint &p){
        int64_t y;
        is >> y;
        p = Arbitrary_Modint(y);
        return (is);
    }

    static int get_mod(){
        return MOD;
    }
};
int Arbitrary_Modint::MOD = 998244353;

using modint9 = Modint<998244353>;
using modint1 = Modint<1000000007>;
using modint = Arbitrary_Modint;
#line 186 "A.cpp"
using mint = modint9;

void solve(){
    INT(n, m);
    VVEC(mint, P, n, m);
    VVEC(mint, Q, n, m);
    fori(i, n){
        fori(j, 1, m){
            P[i][j] += P[i][j - 1];
        }
    }
    fori(j, m){
        fori(i, 1, n){
            Q[i][j] += Q[i - 1][j];
        }
    }
    mint ans = 2;
    fori(i, 1, n - 1) fori(j, 1, m - 1){
        ans += P[i][j - 1] * Q[i - 1][j] * (1 - P[i + 1][j - 1]) * (1 - Q[i - 1][j + 1]);
    }
    print(ans);
}

int main(){
    cin.tie(0)->sync_with_stdio(0);
    // cout << fixed << setprecision(12);
    int t;
    t = 1;
    // cin >> t;
    while(t--) solve();
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 3408kb

input:

3 3
0 0 1
1 0 0
0 0 1
0 1 0
0 0 0
1 0 1

output:

3

result:

ok 1 number(s): "3"

Test #2:

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

input:

2 2
499122177 499122177
499122177 499122177
499122177 499122177
499122177 499122177

output:

2

result:

ok 1 number(s): "2"

Test #3:

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

input:

3 3
332748118 332748118 332748118
332748118 332748118 332748118
332748118 332748118 332748118
332748118 332748118 332748118
332748118 332748118 332748118
332748118 332748118 332748118

output:

308100111

result:

ok 1 number(s): "308100111"

Test #4:

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

input:

3 3
493467174 925495668 577525865
405223176 658993746 932271785
966780207 630353698 399354802
22358767 981331599 114314620
272795749 519599007 591379230
703089838 495558101 292550504

output:

23563191

result:

ok 1 number(s): "23563191"

Test #5:

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

input:

3 4
493659548 347753380 41129357 115702069
790219615 554402002 99659402 552207688
7961216 627013784 223799162 139470192
329148825 491071064 379664791 105141924
498265681 675980390 393090456 957492234
170829848 829437253 225489107 933854549

output:

784737880

result:

ok 1 number(s): "784737880"

Test #6:

score: 0
Accepted
time: 5ms
memory: 3488kb

input:

100 100
968816278 734173596 234681910 93630748 134697884 471229964 39013156 956757252 235131257 511081728 621947839 676193272 840439535 664182871 902176048 20092424 884007838 81431694 951304691 976244158 965161864 845777280 94028804 565315467 686041993 462628490 127799346 373093423 391855425 4867259...

output:

674065285

result:

ok 1 number(s): "674065285"

Test #7:

score: 0
Accepted
time: 10ms
memory: 3724kb

input:

200 199
651700501 316888933 636760258 710519804 979635790 431517212 426271520 438606170 264014396 821432690 856532353 593193153 730369769 738218364 931314610 464183384 649108501 692856317 896419090 859042084 253545651 925218904 209204714 964720847 270465040 877213966 556600916 266109538 89025348 955...

output:

761582714

result:

ok 1 number(s): "761582714"

Test #8:

score: 0
Accepted
time: 6ms
memory: 3716kb

input:

199 200
855982177 899033137 857166748 154194180 491821489 936038701 3224246 36250618 98892048 302140015 794640536 416783706 127675016 405917998 810549418 512853897 794410341 751776756 962776697 437808995 42664926 617079413 287993531 754517649 196857387 98605924 437576034 405249986 501341390 9381807 ...

output:

23575883

result:

ok 1 number(s): "23575883"

Test #9:

score: 0
Accepted
time: 41ms
memory: 4528kb

input:

500 400
72515769 740084226 495955960 818627803 996233188 939336757 660769842 900083013 516811832 948688370 190983166 700755046 725666191 328442680 875581535 336718725 61207501 432805968 739541236 154531312 562430186 291869705 53196304 388792842 771217822 494695449 92141944 786309802 59729318 8289686...

output:

646310271

result:

ok 1 number(s): "646310271"

Test #10:

score: 0
Accepted
time: 195ms
memory: 10964kb

input:

1000 999
795650098 214468232 293238302 956472869 963508300 152950675 332778044 343814027 226283602 475129464 264926647 612915811 52220688 752047365 53207005 824854089 964440017 176446166 421148215 794524271 734053120 903086814 195743674 134468212 708339297 274493474 991647876 223649647 499895016 343...

output:

777267719

result:

ok 1 number(s): "777267719"

Test #11:

score: 0
Accepted
time: 194ms
memory: 10864kb

input:

999 1000
990078941 834513847 566770109 186987188 311749761 202816623 18178171 341799789 882531908 227919120 738756186 31713847 38448010 887427104 749097109 721772777 800574980 140838641 340760447 317536000 153645022 20203677 509441381 92386232 683428380 485171900 141082579 519803036 239407921 431904...

output:

797495799

result:

ok 1 number(s): "797495799"

Test #12:

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

input:

1 1000
865561477 72336177 512589404 659280480 729664705 332496264 10125067 162396209 337852118 235168352 745897162 624343408 680571458 406843703 593295102 463447303 875777949 65980904 986994648 123891087 299721718 487984705 833593382 879673048 20178491 596839074 66333708 72629381 989328440 610923886...

output:

2

result:

ok 1 number(s): "2"

Test #13:

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

input:

1000 1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1...

output:

2

result:

ok 1 number(s): "2"

Test #14:

score: 0
Accepted
time: 160ms
memory: 10868kb

input:

1000 1000
363404459 364033656 109262550 987419044 566850510 158677668 86765910 117668850 972431056 752990746 797824608 368896025 828777722 179827000 547989067 559543021 250055475 621118166 343014414 973968011 780219307 411784822 657282180 275541216 632340286 805660555 962920542 536482883 840886893 2...

output:

319243592

result:

ok 1 number(s): "319243592"