QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#664548#1387. Malowanie płotu [B]Starrykiller10 ✓207ms81328kbC++236.9kb2024-10-21 21:07:362024-10-21 21:07:36

Judging History

This is the latest submission verdict.

  • [2024-10-21 21:07:36]
  • Judged
  • Verdict: 10
  • Time: 207ms
  • Memory: 81328kb
  • [2024-10-21 21:07:36]
  • Submitted

answer

// Homura Akemi a.k.a. Starrykiller (/user/235125)
// I love Madoka Kaname forever! 
#include <bits/stdc++.h>

using namespace std;

template<typename L, typename R>
auto range(L l, R r) { return views::iota(l,r); }
auto rev=views::reverse;

template<typename T>
_GLIBCXX_ALWAYS_INLINE void chmax(T &a, T b) { a=max(a,b); }
template<typename T>
_GLIBCXX_ALWAYS_INLINE void chmin(T &a, T b) { a=min(a,b); }
// #define int long long
namespace sk {
    // modint: https://www.cnblogs.com/hzy1/p/16344746.html
    // Edited by Starrykiller.
    using i64=int64_t;
    using i128=__int128;
    using u128=unsigned __int128;
    using u64=uint64_t;
    using i32=int32_t;
    using u32=uint32_t;
    struct barrett { // From Atcoder Library.
        u32 _m;
        u64 im;
        explicit barrett(u32 m) : _m(m), im((u64)(-1)/m+1) {}
        u32 umod() const { return _m; }
        u32 mul(u32 a, u32 b) const {
            u64 z=a; z*=b;
            u64 x=(u64)((u128(z)*im) >> 64);
            u64 y = x * _m;
            return (u32)(z-y+(z<y?_m:0));
        }
    };
    constexpr i32 inverse(i32 a, i32 m) { i32 r=1;
        while (a>1) { i32 t=m/a; r=i64(r)*(m-t)%m; a=m-t*a; }
        return r;
    }
    template<i32 p>
    struct static_modint { 
        using mi=static_modint;
        public:
        constexpr static_modint(i64 x) : x(normal(x%p)) {}
        constexpr static_modint(i32 x, std::nullptr_t) : x(x) {}
        constexpr static_modint(): x(0) {}
        constexpr i32 normal(i32 x) { 
            if (x>=p) x-=p;
            return x+((x>>31)&p); 
        }
        constexpr i32 val() const { return x; }
        constexpr static i32 mod() { return p; }
        constexpr explicit operator bool() const { return x; }
        constexpr mi inv() const { assert(x!=0); return mi(inverse(x,p),nullptr); }
        constexpr mi pow(i64 x) const { assert(x>=0); mi a=*this, res=1;
            while (x) { if (x&1) res*=a; a*=a; x>>=1; } return res; }
        constexpr mi operator-() const { return mi(p-x); }
        constexpr mi& operator+=(const mi &rhs) { x=normal(x+rhs.x); return *this; }
        constexpr mi& operator-=(const mi &rhs) { x=normal(x-rhs.x); return *this; }
        constexpr mi& operator++() { return (*this)+=1; }
        constexpr mi& operator--() { return (*this)-=1; }
        constexpr mi& operator*=(const mi &rhs) { x=i64(x)*rhs.x%p; return *this; }
        constexpr mi& operator/=(const mi &rhs) { return *this *= rhs.inv(); }
        constexpr friend mi operator+(const mi &lhs, const mi &rhs) { auto res=lhs; res+=rhs; return res; }
        constexpr friend mi operator-(const mi &lhs, const mi &rhs) { auto res=lhs; res-=rhs; return res; }
        constexpr friend mi operator*(const mi &lhs, const mi &rhs) { auto res=lhs; res*=rhs; return res; }
        constexpr friend mi operator/(const mi &lhs, const mi &rhs) { auto res=lhs; res/=rhs; return res; }
        constexpr friend mi operator++(mi &x, i32) { auto tmp=x; x+=1; return tmp; }
        constexpr friend mi operator--(mi &x, i32) { auto tmp=x; x-=1; return tmp; }
        constexpr friend std::istream& operator>>(std::istream &is, mi &a) { i64 v; is>>v; a=v; return is; }
        constexpr friend std::ostream& operator<<(std::ostream &os, const mi &a) { os<<a.val(); return os; }
        constexpr bool operator==(const mi& rhs) const { return val()==rhs.val(); }
        constexpr bool operator!=(const mi& rhs) const { return val()!=rhs.val(); }
        private:
        i32 x;
    };
    template<i32 id>
    struct dynamic_modint { 
        using mi=dynamic_modint;
        public:
        constexpr dynamic_modint(i64 x) : x(normal(x%mod())) {}
        constexpr dynamic_modint(i32 x, std::nullptr_t) : x(x) {}
        constexpr dynamic_modint(): x(0) {}
        constexpr i32 normal(i32 x) { 
            auto p=mod();
            if (x>=p) x-=p;
            return x+((x>>31)&p); 
        }
        constexpr i32 val() const { return x; }
        constexpr static void set_mod(i32 m) { assert(m>=1); bt=barrett((u32)m); }
        constexpr static i32 mod() { return bt.umod(); }
        constexpr explicit operator bool() const { return x; }
        constexpr mi inv() const { assert(x!=0); return mi(inverse(x,mod()),nullptr); }
        constexpr mi pow(i64 x) const { assert(x>=0); mi a=*this, res=1;
            while (x) { if (x&1) res*=a; a*=a; x>>=1; } return res; }
        constexpr mi operator-() const { return mi(mod()-x); }
        constexpr mi& operator+=(const mi &rhs) { x=normal(x+rhs.x); return *this; }
        constexpr mi& operator-=(const mi &rhs) { x=normal(x-rhs.x); return *this; }
        constexpr mi& operator++() { return (*this)+=1; }
        constexpr mi& operator--() { return (*this)-=1; }
        constexpr mi& operator*=(const mi &rhs) { x=bt.mul(val(),rhs.val()); return *this; }
        constexpr mi& operator/=(const mi &rhs) { return *this *= rhs.inv(); }
        constexpr friend mi operator+(const mi &lhs, const mi &rhs) { auto res=lhs; res+=rhs; return res; }
        constexpr friend mi operator-(const mi &lhs, const mi &rhs) { auto res=lhs; res-=rhs; return res; }
        constexpr friend mi operator*(const mi &lhs, const mi &rhs) { auto res=lhs; res*=rhs; return res; }
        constexpr friend mi operator/(const mi &lhs, const mi &rhs) { auto res=lhs; res/=rhs; return res; }
        constexpr friend mi operator++(mi &x, i32) { auto tmp=x; x+=1; return tmp; }
        constexpr friend mi operator--(mi &x, i32) { auto tmp=x; x-=1; return tmp; }
        constexpr friend std::istream& operator>>(std::istream &is, mi &a) { i64 v; is>>v; a=v; return is; }
        constexpr friend std::ostream& operator<<(std::ostream &os, const mi &a) { os<<a.val(); return os; }
        constexpr bool operator==(const mi& rhs) const { return val()==rhs.val(); }
        constexpr bool operator!=(const mi& rhs) const { return val()!=rhs.val(); }
        private:
        i32 x; 
        static barrett bt;
    };
    template<i32 id> barrett dynamic_modint<id>::bt(998244353);
    using modint998244353=static_modint<998244353>;
    using modint1000000007=static_modint<1000000007>;
    using mint=dynamic_modint<-1>; 
};
using ll=sk::mint;

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
// int T; cin>>T;
int T=1;
while (T--) []{
    int n, m, p; cin>>n>>m>>p; ll::set_mod(p);
    vector f(m,ll(0));
    f[m-1]=1;
    while (n--) {    
        vector g(m,ll(0));
        for (ll sum=0; auto i: range(0,m)) {
            sum+=f[i]*(i+1);
            g[i]+=sum;
        }
        for (ll sum=0; auto i: range(0,m)|rev) {
            g[i]+=sum*(i+1);
            sum+=f[i];
        }
        for (ll sum=0; auto &i: f) i=(sum+=i);
        for (auto i: range(0,m-1)) g[i]-=f[m-2-i]*(i+1);
        swap(f,g);
    }
    cout<<accumulate(begin(f),end(f),ll(0))<<'\n';
}();
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 1
Accepted

Test #3:

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

input:

1 1 100000007

output:

1

result:

ok single line: '1'

Test #4:

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

input:

1 2 100000007

output:

3

result:

ok single line: '3'

Test #5:

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

input:

2 1 100000007

output:

1

result:

ok single line: '1'

Test #6:

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

input:

2 2 100000007

output:

7

result:

ok single line: '7'

Test #7:

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

input:

1 12 458190937

output:

78

result:

ok single line: '78'

Test #8:

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

input:

3 9 609209299

output:

45321

result:

ok single line: '45321'

Test #9:

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

input:

5 5 339010421

output:

215401

result:

ok single line: '215401'

Test #10:

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

input:

6 4 489918731

output:

222696

result:

ok single line: '222696'

Test #11:

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

input:

10 1 169646857

output:

1

result:

ok single line: '1'

Subtask #2:

score: 1
Accepted

Test #12:

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

input:

30 30 380195119

output:

166619630

result:

ok single line: '166619630'

Test #13:

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

input:

17 29 360348029

output:

212112394

result:

ok single line: '212112394'

Test #14:

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

input:

27 16 197567003

output:

95366620

result:

ok single line: '95366620'

Subtask #3:

score: 1
Accepted

Test #15:

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

input:

200 200 682943017

output:

56311807

result:

ok single line: '56311807'

Test #16:

score: 1
Accepted
time: 1ms
memory: 3608kb

input:

152 247 581829701

output:

137411851

result:

ok single line: '137411851'

Test #17:

score: 1
Accepted
time: 1ms
memory: 3564kb

input:

253 143 851321791

output:

525957764

result:

ok single line: '525957764'

Subtask #4:

score: 1
Accepted

Test #18:

score: 1
Accepted
time: 3ms
memory: 3636kb

input:

400 400 810613007

output:

435224113

result:

ok single line: '435224113'

Test #19:

score: 1
Accepted
time: 2ms
memory: 3580kb

input:

210 550 285341863

output:

160338540

result:

ok single line: '160338540'

Test #20:

score: 1
Accepted
time: 2ms
memory: 3628kb

input:

531 222 794866781

output:

609575705

result:

ok single line: '609575705'

Subtask #5:

score: 1
Accepted

Test #21:

score: 1
Accepted
time: 2ms
memory: 3884kb

input:

49 2015 372771527

output:

317694427

result:

ok single line: '317694427'

Test #22:

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

input:

14 4121 985447493

output:

387364224

result:

ok single line: '387364224'

Test #23:

score: 1
Accepted
time: 1ms
memory: 3848kb

input:

5 6354 537388739

output:

326949718

result:

ok single line: '326949718'

Test #24:

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

input:

3 9654 249806021

output:

10220508

result:

ok single line: '10220508'

Subtask #6:

score: 1
Accepted

Test #25:

score: 1
Accepted
time: 33ms
memory: 3608kb

input:

6000 400 898580777

output:

832449975

result:

ok single line: '832449975'

Test #26:

score: 1
Accepted
time: 65ms
memory: 3524kb

input:

33333 130 392883373

output:

70395366

result:

ok single line: '70395366'

Test #27:

score: 1
Accepted
time: 31ms
memory: 3604kb

input:

620301 3 578160377

output:

252040878

result:

ok single line: '252040878'

Subtask #7:

score: 1
Accepted

Test #28:

score: 1
Accepted
time: 11ms
memory: 3644kb

input:

1000 1000 860175601

output:

581086038

result:

ok single line: '581086038'

Test #29:

score: 1
Accepted
time: 15ms
memory: 3588kb

input:

500 2000 436780781

output:

372087508

result:

ok single line: '372087508'

Test #30:

score: 1
Accepted
time: 14ms
memory: 3860kb

input:

291 3030 181940159

output:

13684863

result:

ok single line: '13684863'

Test #31:

score: 1
Accepted
time: 10ms
memory: 3672kb

input:

51 12345 287325587

output:

224639430

result:

ok single line: '224639430'

Test #32:

score: 1
Accepted
time: 1ms
memory: 3944kb

input:

2 10008 100170073

output:

0

result:

ok single line: '0'

Subtask #8:

score: 1
Accepted

Test #33:

score: 1
Accepted
time: 34ms
memory: 3652kb

input:

1500 1500 403129117

output:

90005156

result:

ok single line: '90005156'

Test #34:

score: 1
Accepted
time: 30ms
memory: 3608kb

input:

3000 757 360590861

output:

29875505

result:

ok single line: '29875505'

Test #35:

score: 1
Accepted
time: 30ms
memory: 3868kb

input:

16384 123 988806947

output:

473539203

result:

ok single line: '473539203'

Subtask #9:

score: 1
Accepted

Test #36:

score: 1
Accepted
time: 93ms
memory: 3592kb

input:

2500 2500 244828267

output:

12777369

result:

ok single line: '12777369'

Test #37:

score: 1
Accepted
time: 86ms
memory: 3680kb

input:

999 5757 103497613

output:

79212279

result:

ok single line: '79212279'

Test #38:

score: 1
Accepted
time: 45ms
memory: 3764kb

input:

100 30000 145049507

output:

55697904

result:

ok single line: '55697904'

Subtask #10:

score: 1
Accepted

Test #39:

score: 1
Accepted
time: 174ms
memory: 81328kb

input:

1 10000000 100000007

output:

1500000

result:

ok single line: '1500000'

Test #40:

score: 1
Accepted
time: 163ms
memory: 42308kb

input:

2 5000000 100000007

output:

50418441

result:

ok single line: '50418441'

Test #41:

score: 1
Accepted
time: 149ms
memory: 7824kb

input:

17 588235 640229041

output:

418700675

result:

ok single line: '418700675'

Test #42:

score: 1
Accepted
time: 149ms
memory: 3852kb

input:

123 81300 732576583

output:

495183394

result:

ok single line: '495183394'

Test #43:

score: 1
Accepted
time: 148ms
memory: 3892kb

input:

3162 3162 999999937

output:

499132075

result:

ok single line: '499132075'

Test #44:

score: 1
Accepted
time: 145ms
memory: 3576kb

input:

21255 470 356450219

output:

93266631

result:

ok single line: '93266631'

Test #45:

score: 1
Accepted
time: 144ms
memory: 3572kb

input:

214928 46 107718181

output:

41692801

result:

ok single line: '41692801'

Test #46:

score: 1
Accepted
time: 175ms
memory: 3572kb

input:

5000000 2 100000007

output:

45607950

result:

ok single line: '45607950'

Test #47:

score: 1
Accepted
time: 207ms
memory: 3604kb

input:

10000000 1 225408061

output:

1

result:

ok single line: '1'