NOI.AC
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #196376 | #2482. 序列 | wosile | 100 | 297ms | 56396kb | C++11 | 1.1kb | 2023-10-24 09:03:30 | 2023-10-24 12:19:18 |
answer
#include<bits/stdc++.h>
#define mod 998244353
using namespace std;
int dp[305][305][305];
int n,m;
vector<pair<int,int> >v[305];
int main(){
// freopen("sequence.in","r",stdin);
// freopen("sequence.out","w",stdout);
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++){
int l,r,x;
scanf("%d%d%d",&l,&r,&x);
v[r].push_back(make_pair(l,x));
}
dp[0][0][0]=1;
int ans=0;
for(int i=0;i<=n;i++){
for(int j=0;j<i||j==0;j++)for(int k=0;k<j||k==0;k++)for(int q=0;q<v[i].size();q++){
int l=v[i][q].first,x=v[i][q].second;
if(x==1 && j>=l)dp[i][j][k]=0;
if(x==2 && (j<l || k>=l))dp[i][j][k]=0;
if(x==3 && k<l)dp[i][j][k]=0;
}
// for(int q=0;q<v[i].size();q++)printf("lim %d %d %d\n",i,v[i][q].first,v[i][q].second);
// for(int j=0;j<i||j==0;j++)for(int k=0;k<j||k==0;k++)printf("dp[%d][%d][%d]=%d\n",i,j,k,dp[i][j][k]);
for(int j=0;j<i||j==0;j++)for(int k=0;k<j||k==0;k++){
if(i==n)ans=(ans+dp[i][j][k])%mod;
dp[i+1][j][k]=(dp[i+1][j][k]+dp[i][j][k])%mod;
dp[i+1][i][k]=(dp[i+1][i][k]+dp[i][j][k])%mod;
dp[i+1][i][j]=(dp[i+1][i][j]+dp[i][j][k])%mod;
}
}
printf("%d",ans);
return 0;
}
Details
小提示：点击横条可展开更详细的信息
Test #1:
score: 10
Accepted
time: 0ms
memory: 1372kb
input:
12 12 3 4 2 8 10 3 1 9 3 5 7 2 5 10 3 4 9 3 1 4 3 10 12 3 1 1 1 1 2 2 7 10 3 5 7 2
output:
4032
result:
ok single line: '4032'
Test #2:
score: 10
Accepted
time: 28ms
memory: 56388kb
input:
300 12 103 293 3 81 92 3 125 164 3 129 200 3 37 54 3 29 295 3 8 216 3 10 19 3 21 205 3 254 287 3 41 ...
output:
124537807
result:
ok single line: '124537807'
Test #3:
score: 10
Accepted
time: 34ms
memory: 56396kb
input:
300 300 53 54 2 106 109 2 219 221 2 205 210 2 267 274 2 113 119 2 206 209 2 79 81 2 201 208 2 206 20...
output:
287380185
result:
ok single line: '287380185'
Test #4:
score: 10
Accepted
time: 37ms
memory: 56396kb
input:
300 300 295 299 1 191 191 1 167 167 1 194 194 1 35 39 1 53 57 1 63 65 1 86 89 1 182 183 1 105 105 1 ...
output:
524111765
result:
ok single line: '524111765'
Test #5:
score: 10
Accepted
time: 48ms
memory: 56396kb
input:
300 300 53 54 2 106 109 2 219 221 2 205 210 2 267 274 2 113 119 2 206 209 2 79 81 2 201 208 2 206 20...
output:
931051581
result:
ok single line: '931051581'
Test #6:
score: 10
Accepted
time: 42ms
memory: 56392kb
input:
300 300 22 26 2 262 266 2 241 245 2 35 43 2 255 261 2 93 96 2 184 189 2 236 239 2 107 114 2 153 161 ...
output:
29541404
result:
ok single line: '29541404'
Test #7:
score: 10
Accepted
time: 0ms
memory: 2940kb
input:
50 50 20 27 3 13 16 2 31 31 1 22 27 3 3 31 3 12 45 3 17 34 3 17 22 3 8 37 3 23 46 3 26 35 3 24 34 3 ...
output:
586118159
result:
ok single line: '586118159'
Test #8:
score: 10
Accepted
time: 0ms
memory: 2940kb
input:
50 50 6 7 2 15 45 3 3 45 3 1 40 3 19 43 3 8 35 3 26 32 3 2 40 3 7 36 3 20 50 3 24 44 3 5 16 3 4 24 3...
output:
212281931
result:
ok single line: '212281931'
Test #9:
score: 10
Accepted
time: 51ms
memory: 56392kb
input:
300 300 46 146 3 76 177 3 176 282 3 85 157 3 12 182 3 75 200 3 186 192 3 176 226 3 219 284 3 47 277 ...
output:
309026097
result:
ok single line: '309026097'
Test #10:
score: 10
Accepted
time: 57ms
memory: 56392kb
input:
300 300 3 287 3 40 166 3 130 192 3 10 83 3 165 197 3 233 290 3 141 225 3 37 113 3 176 275 3 35 72 3 ...
output:
168965403
result:
ok single line: '168965403'
Extra Test:
score: 0
Extra Test Passed
