QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#108236 | #1286. Ternary String Counting | Faccirx | TL | 1169ms | 34984kb | C++20 | 3.4kb | 2023-05-23 23:33:12 | 2023-05-23 23:33:14 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define int long long
template<class T>bool chkmax(T &a,T b){return b>a?a=b,true:false;}
template<class T>bool chkmin(T &a,T b){return b<a?a=b,true:false;}
constexpr int inf=2e18;
template<const int mod>
struct modint{
int x;
modint(int x=0):x(norm(x%mod)){}
int val()const{
return x;
}
modint operator-()const{
return modint(norm(mod-x));
}
int norm(int x)const{
if(x<0) x+=mod;
if(x>=mod) x-=mod;
return x;
}
modint pow(int x)const{
modint res=1;
modint cur=*this;
while(x){
if(x&1){
res*=cur;
}
cur*=cur;
x/=2;
}
return res;
}
modint inv()const{
assert(x!=0);
return pow(mod-2);
}
modint &operator*=(const modint &rhs){
x=(long long)(x)*rhs.x%mod;
return *this;
}
modint &operator+=(const modint &rhs){
x=norm(x+rhs.x);
return *this;
}
modint &operator-=(const modint &rhs){
x=norm(x-rhs.x);
return *this;
}
modint &operator/=(const modint &rhs){
return *this*=rhs.inv();
}
friend modint operator*(const modint &lhs,const modint &rhs){
modint res=lhs;
res*=rhs;
return res;
}
friend modint operator+(const modint &lhs,const modint &rhs){
modint res=lhs;
res+=rhs;
return res;
}
friend modint operator-(const modint &lhs,const modint &rhs){
modint res=lhs;
res-=rhs;
return res;
}
friend modint operator/(const modint &lhs,const modint &rhs){
modint res=lhs;
res/=rhs;
return res;
}
friend istream &operator>>(istream &is,modint &a){
long long v;
is>>v;
a=modint(v);
return is;
}
friend ostream &operator<<(ostream &os,const modint &a){
return os<<a.val();
}
friend bool operator==(const modint &lhs,const modint &rhs){
return lhs.val()==rhs.val();
}
friend bool operator!=(const modint &lhs,const modint &rhs){
return lhs.val()!=rhs.val();
}
};
using Mint=modint<(int)1e9+7>;
void solve(){
int n,m;
cin>>n>>m;
vector<vector<pair<int,int>>>con(n);
for(int i=0;i<m;i++){
int l,r,x;
cin>>l>>r>>x;
l--,r--;
con[r].emplace_back(l,x);
}
for(auto[l,x]:con[0]){
if(x>1){
cout<<"0\n";
return;
}
}
vector<vector<Mint>>dp(n+2,vector<Mint>(n+2));
dp[-1+2][-2+2]=3;
vector<Mint>sum(n+2);
sum[-1+2]=3;
sum[-2+2]=3;
vector<int>row;
row.push_back(-1);
row.push_back(0);
for(int i=0;i<n-1;i++){
int l_j=-inf,r_j=inf;
int l_k=-inf,r_k=inf;
for(auto[l,x]:con[i+1]){
if(x==1){
chkmin(r_j,l-1);
}
else if(x==2){
chkmax(l_j,l);
chkmin(r_k,l-1);
}
else{
chkmax(l_k,l);
}
}
auto cur=sum;
for(int j=-2;j<i;j++){
dp[i+2][j+2]+=cur[j+2];
sum[i+2]+=cur[j+2];
sum[j+2]+=cur[j+2];
}
vector<int>nrow;
for(int j:row){
if(l_j<=j&&j<=r_j){
nrow.push_back(j);
}
else{
for(int k=-2;k<n;k++){
sum[j+2]-=dp[j+2][k+2];
sum[k+2]-=dp[j+2][k+2];
dp[j+2][k+2]=0;
}
}
}
swap(row,nrow);
for(int j:row){
for(int k=-2;k<j;k++){
if(!(l_k<=k&&k<=r_k)){
sum[j+2]-=dp[j+2][k+2];
sum[k+2]-=dp[j+2][k+2];
dp[j+2][k+2]=0;
}
}
}
row.push_back(i+1);
}
Mint ans=0;
for(int j:row){
for(int k=-2;k<j;k++){
ans+=dp[j+2][k+2];
}
}
cout<<ans<<"\n";
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int T;
cin>>T;
while(T--){
solve();
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3528kb
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: 3ms
memory: 3480kb
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: 2ms
memory: 3476kb
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: 286ms
memory: 11416kb
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: 325ms
memory: 11452kb
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: 1169ms
memory: 34972kb
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: 1038ms
memory: 34984kb
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: -100
Time Limit Exceeded
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