QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#714005 | #1286. Ternary String Counting | Azusa | ML | 214ms | 233968kb | C++14 | 3.3kb | 2024-11-05 21:13:01 | 2024-11-05 21:13:04 |
Judging History
answer
#include<bits/stdc++.h>
#define rep(i,a,n) for(int i=(a);i<=(n);++i)
#define per(i,a,n) for(int i=(n);i>=(a);--i)
#define SZ(x) ((int)(x).size())
using namespace std;
typedef double db;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn=5e3+10,mod=1e9+7;
inline void rd(){};
template<typename T1,typename ...T2>
inline void rd(T1 &x,T2 &...rest){
bool w=1; x=0; char ch=getchar();
while(!isdigit(ch)){w^=(ch=='-');ch=getchar();}
while(isdigit(ch)){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
w?0:x=-x;
rd(rest...);
}
template<int MOD> struct mint {
static const int mod = MOD;
int v;
explicit operator int() const { return v; }
mint():v(0) {}
mint(ll _v) {
v = int((-MOD < _v && _v < MOD) ? _v : _v % MOD);
if (v < 0) v += MOD;
}
bool operator==(const mint& o) const {return v==o.v;}
friend bool operator!=(const mint& a, const mint& b) {return !(a==b);}
friend bool operator<(const mint& a, const mint& b) {return a.v<b.v;}
mint& operator+=(const mint& o){
if ((v += o.v) >= MOD) v -= MOD;
return *this;
}
mint& operator-=(const mint& o){
if ((v -= o.v) < 0) v += MOD;
return *this;
}
mint& operator*=(const mint& o){ v=int((ll)v*o.v%MOD); return *this;}
mint& operator/=(const mint& o) { return (*this) *= _inv(o); }
friend mint pow(mint a, ll p) {
mint ans = 1;
assert(p >= 0);
for (; p; p /= 2, a *= a) if (p&1) ans *= a;
return ans;
}
friend mint _inv(const mint& a) {
assert(a.v != 0);
return pow(a,MOD-2);
}
mint operator-() const { return mint(-v); }
mint& operator++() { return *this += 1; }
mint& operator--() { return *this -= 1; }
friend mint operator+(mint a, const mint& b) { return a += b; }
friend mint operator-(mint a, const mint& b) { return a -= b; }
friend mint operator*(mint a, const mint& b) { return a *= b; }
friend mint operator/(mint a, const mint& b) { return a /= b; }
};
using mi = mint<mod>;
int n,m;
vector<pii> event[maxn],h[maxn],w[maxn];
vector<int> val;
mi s[maxn],t[maxn];
inline void add(int x,int y,mi v){
if(v==0) return;
int nw=SZ(val);
val.emplace_back((int)v);
h[x].emplace_back(make_pair(y,nw));
w[y].emplace_back(make_pair(x,nw));
s[x]+=v; s[y]+=v;
}
inline void init(){
rep(i,0,n){
event[i].clear();
h[i].clear();
w[i].clear();
s[i]=0;
}
val.clear();
}
inline void solve(){
rd(n,m);
init();
rep(i,1,m){
int l,r,x;
rd(l,r,x);
event[r].emplace_back(make_pair(l,x));
}
add(0,0,1);
rep(i,0,n){
int jl=0,jr=n+1,kl=0,kr=n+1;
for(auto [j,x]:event[i]){
if(x==1) jr=min(jr,j-1);
if(x==2) jl=max(jl,j),kr=min(kr,j-1);
if(x==3) kl=max(kl,j);
}
rep(j,0,i){
if(jl<=j && j<=jr) continue;
for(auto [y,id]:h[j]){
s[j]-=val[id]; s[y]-=val[id];
val[id]=0;
}
h[j].clear();
}
rep(j,0,i){
if(kl<=j && j<=kr) continue;
for(auto [y,id]:w[j]){
s[j]-=val[id]; s[y]-=val[id];
val[id]=0;
}
w[j].clear();
}
if(i!=n){
rep(j,0,i) t[j]=s[j];
rep(j,0,i) add(i,j,t[j]);
}
}
mi res=0;
rep(i,0,n) res+=s[i];
printf("%d\n",res/2);
}
signed main(){
int _=1;
scanf("%d",&_);
while(_--) solve();
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 4352kb
input:
4 1 0 2 0 3 0 5 2 1 3 3 4 5 1
output:
3 9 27 18
result:
ok 4 tokens
Test #2:
score: 0
Accepted
time: 1ms
memory: 4300kb
input:
741 5 3 1 5 3 3 4 2 1 4 3 4 3 2 4 2 1 4 1 2 3 3 10 3 9 10 2 3 6 3 1 9 1 3 4 2 3 2 1 3 2 2 3 3 1 3 3 10 4 6 6 1 9 10 2 4 8 3 4 10 3 6 3 1 4 3 2 4 2 2 2 2 4 3 1 4 1 1 1 2 2 3 1 5 3 4 5 2 4 5 1 1 4 3 9 3 2 3 2 1 9 2 2 4 2 4 3 1 3 3 2 3 2 1 2 3 8 4 5 8 1 4 8 1 3 5 3 1 3 3 9 3 4 5 1 1 5 3 3 8 2 8 3 5 7 2...
output:
90 0 0 0 24300 0 0 0 768 0 0 972 2916 0 6480 864 0 0 0 0 0 0 0 0 6 0 0 0 0 0 96 0 6 0 0 0 0 0 0 0 108 0 0 0 2916 0 0 0 0 0 0 0 0 0 0 324 8748 0 0 0 0 0 0 4320 0 0 0 18 0 0 0 0 0 0 0 0 0 0 0 1992 0 0 450 0 162 1656 0 0 0 0 0 54 0 18 0 0 0 0 744 0 1620 324 0 0 36 36 0 0 60 6 54 0 0 0 0 0 0 0 0 243 810...
result:
ok 741 tokens
Test #3:
score: 0
Accepted
time: 1ms
memory: 4364kb
input:
332 17 5 4 9 1 4 6 1 7 17 1 5 5 1 5 6 3 13 5 10 12 3 8 13 2 1 10 3 2 9 1 9 10 1 19 5 11 13 1 9 17 2 1 7 1 4 4 2 3 9 1 15 4 8 11 2 9 14 3 10 12 2 4 5 2 12 4 3 9 2 7 8 1 1 7 3 6 7 3 16 5 4 14 3 1 5 1 2 10 1 2 12 3 6 9 3 20 4 10 17 3 4 20 3 17 19 3 8 17 1 20 5 11 11 1 9 13 1 1 5 3 17 17 3 3 18 3 17 5 1...
output:
0 0 0 2047032 0 0 0 0 0 839808 0 0 0 0 0 0 0 0 0 0 0 0 44641044 0 20412 0 0 0 0 0 0 0 6 0 0 0 0 81 0 0 0 0 0 0 0 0 0 0 0 313155072 0 0 0 0 0 0 0 0 0 5400 0 10368 0 0 0 0 14580 0 0 0 217728 40310784 0 0 218700 0 0 0 0 1620 0 0 0 0 0 108 146304 0 0 0 466560 288 0 0 0 0 0 0 0 276138 0 0 0 0 0 0 0 52488...
result:
ok 332 tokens
Test #4:
score: 0
Accepted
time: 31ms
memory: 16296kb
input:
5 1000 0 1000 5 779 779 2 543 840 3 30 477 1 10 295 3 463 741 1 1000 6 379 569 1 249 826 2 194 819 3 90 400 1 614 808 2 102 868 2 1000 8 463 981 1 680 857 3 560 623 1 209 659 1 55 957 2 244 327 1 321 888 3 37 204 3 1000 5 336 851 3 410 676 1 522 911 2 165 962 1 258 330 3
output:
56888193 0 0 0 0
result:
ok 5 tokens
Test #5:
score: 0
Accepted
time: 29ms
memory: 16656kb
input:
5 1000 9 190 765 1 212 745 3 437 798 3 682 814 3 122 289 1 44 821 1 115 448 3 400 936 2 562 639 3 1000 5 561 808 3 23 160 2 57 915 2 211 943 3 125 596 2 1000 1 398 739 2 1000 3 629 973 2 7 721 2 591 815 2 1000 10 536 708 1 217 256 2 690 913 3 418 871 2 302 325 2 334 830 2 496 573 2 396 865 1 240 837...
output:
0 0 722271060 85306976 0
result:
ok 5 tokens
Test #6:
score: 0
Accepted
time: 63ms
memory: 52092kb
input:
2 2000 1 1501 1703 2 2000 5 1230 1521 3 1022 1939 3 1241 1283 3 767 1944 2 303 1163 3
output:
841960641 0
result:
ok 2 tokens
Test #7:
score: 0
Accepted
time: 71ms
memory: 48520kb
input:
2 2000 2 640 1942 1 1473 1917 3 2000 4 490 887 1 670 1163 3 824 1434 2 1221 1746 1
output:
0 0
result:
ok 2 tokens
Test #8:
score: 0
Accepted
time: 63ms
memory: 36540kb
input:
1 5000 9 2821 3377 2 798 1535 2 3563 4161 3 2205 2946 3 1320 1594 3 278 1624 1 1243 2759 3 2882 4939 1 2639 3559 3
output:
0
result:
ok "0"
Test #9:
score: 0
Accepted
time: 214ms
memory: 233968kb
input:
1 5000 2 539 4252 1 906 3821 1
output:
101862333
result:
ok "101862333"
Test #10:
score: 0
Accepted
time: 3ms
memory: 4496kb
input:
111 34 0 30 0 18 0 35 0 3 0 43 0 13 0 28 0 57 0 75 0 31 0 4 0 92 0 1 0 53 0 85 0 74 0 43 0 59 0 72 0 79 0 40 0 70 0 36 0 86 0 56 0 53 0 66 0 50 0 100 0 60 0 74 0 50 0 51 0 92 0 49 0 50 0 78 0 95 0 4 0 59 0 44 0 92 0 84 0 7 0 75 0 99 0 56 0 54 0 13 0 27 0 33 0 22 0 80 0 14 0 79 0 29 0 39 0 21 0 97 0 ...
output:
582926302 130653412 387420489 748778899 27 738321955 1594323 792294829 998064805 100094381 391960236 81 587240675 3 172815616 473062299 700031465 738321955 982583189 966670169 107644805 953271190 662963356 246336683 419186890 666021604 172815616 909419307 710104287 886041711 947749553 700031465 7101...
result:
ok 111 tokens
Test #11:
score: 0
Accepted
time: 12ms
memory: 6748kb
input:
16 350 0 453 0 485 0 361 0 498 0 149 0 433 0 435 0 279 0 240 0 166 0 152 0 393 0 159 0 219 0 222 0
output:
378029361 68761795 621961191 766744305 24977444 679213660 705815658 352340880 186665231 458529104 150230246 338768694 907169137 887128598 322586612 709838468
result:
ok 16 tokens
Test #12:
score: -100
Memory Limit Exceeded
input:
1 5000 0
output:
22443616