QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#664548 | #1387. Malowanie płotu [B] | Starrykiller | 10 ✓ | 207ms | 81328kb | C++23 | 6.9kb | 2024-10-21 21:07:36 | 2024-10-21 21:07:36 |
Judging History
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'