QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #212966 | #90. Fishing Game | Ahmed57# | 40 | 0ms | 27748kb | C++23 | 2.0kb | 2023-10-13 23:55:49 | 2024-07-04 02:19:45 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
long long dp[80][80][80][2][3];
long long mod = 1000000007;
long long solve(long long ft,long long fs,long long st,int done,int i){
if(ft<0||fs<0||st<0||(i==0&&done==0))return 0;
if(ft==0&&fs==0&&st==0){
return 1;
}
if(dp[ft][fs][st][done][i]!=-1)return dp[ft][fs][st][done][i];
if(i==0){
long long c1 = 0;
if(ft==0&&fs==0){
c1 = solve(ft,fs,st,0,(i+1)%3);
}
else c1 = ((solve(ft-1,fs,st+1,0,(i+1)%3)*ft)%mod)+((solve(ft,fs-1,st,1,(i+1)%3)*fs)%mod);
return dp[ft][fs][st][done][i] = c1%mod;
}if(i==1){
long long c1 = 0;
if(fs==0&&st==0){
c1 = solve(ft,fs,st,done,(i+1)%3);
}
else c1 = ((solve(ft+1,fs-1,st,done,(i+1)%3)*fs)%mod)+((solve(ft,fs,st-1,1,(i+1)%3)*st)%mod);
return dp[ft][fs][st][done][i] = c1%mod;
}if(i==2){
long long c1 = 0;
if(ft==0&&st==0){
c1 = solve(ft,fs,st,done,(i+1)%3);
}
else c1 = ((solve(ft,fs+1,st-1,done,(i+1)%3)*st)%mod)+((solve(ft-1,fs,st,1,(i+1)%3)*ft)%mod);
return dp[ft][fs][st][done][i] = c1%mod;
}
}
int main(){
memset(dp,-1,sizeof dp);
int n,t;cin>>n>>t;
while(t--){
set<int> a, b,c;
for(int i = 0;i<2*n;i++){
int x;cin>>x;a.insert(x);
}
for(int i = 0;i<2*n;i++){
int x;cin>>x;b.insert(x);
}
for(int i = 0;i<2*n;i++){
int x;cin>>x;c.insert(x);
}
int cnt[3*n+1] = {0};
for(auto i:a)cnt[i]|=(1<<0);
for(auto i:b)cnt[i]|=(1<<1);
for(auto i:c)cnt[i]|=(1<<2);
int fs =0 , ft = 0 , st = 0;
for(int i = 1;i<=3*n;i++){
if(cnt[i]==3){
fs++;
}
if(cnt[i]==5){
ft++;
}
if(cnt[i]==6){
st++;
}
}
cout<<solve(ft,fs,st,1,0)<<endl;
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 10
Accepted
time: 0ms
memory: 27600kb
input:
2 3 6 1 5 2 1 6 4 2 3 4 5 3 6 3 1 5 2 3 5 6 2 4 4 1 1 2 3 4 3 4 5 6 1 2 5 6
output:
690 690 19400
result:
ok 3 lines
Test #2:
score: 10
Accepted
time: 0ms
memory: 27520kb
input:
3 5 9 6 3 8 1 5 4 9 4 2 1 6 5 7 7 3 2 8 4 5 7 5 6 8 2 9 7 1 4 9 3 3 1 6 2 8 7 2 1 3 6 9 8 3 5 4 6 7 4 8 9 5 1 2 8 8 2 5 4 6 1 2 9 3 9 4 6 7 3 5 1 7 1 2 3 4 5 6 4 5 6 7 8 9 1 2 3 7 8 9
output:
920808 19400 339064275 19400 339064275
result:
ok 5 lines
Test #3:
score: 10
Accepted
time: 0ms
memory: 27596kb
input:
10 5 15 22 9 24 13 11 7 25 21 14 3 5 4 26 19 26 18 29 16 29 16 7 13 30 17 1 4 15 23 9 12 20 22 2 23 18 5 3 10 21 12 30 14 28 27 11 24 8 10 28 17 27 2 20 1 25 6 19 8 6 19 15 27 9 16 21 14 10 19 15 12 11 2 7 16 28 26 25 18 18 12 24 13 29 13 14 1 1 20 29 22 17 3 23 11 28 20 17 5 10 4 24 3 6 4 5 21 22 2...
output:
169430774 184903628 864843034 186397548 145548558
result:
ok 5 lines
Test #4:
score: 10
Accepted
time: 0ms
memory: 27748kb
input:
20 5 26 19 51 35 32 56 13 57 27 9 44 35 34 58 42 12 59 12 8 33 59 16 1 17 11 50 60 28 34 7 33 1 15 8 32 11 29 22 27 52 9 24 15 2 45 19 56 39 28 18 21 3 14 41 6 18 23 25 6 26 23 49 52 17 2 42 10 16 41 31 4 54 43 29 30 46 55 24 49 44 10 21 20 55 20 60 14 4 37 54 45 48 31 5 47 3 5 40 36 36 38 53 7 43 4...
output:
147852189 405005016 808713263 143513805 739432483
result:
ok 5 lines
Test #5:
score: 0
Runtime Error
input:
50 10 103 51 39 35 6 66 124 140 131 19 117 97 47 98 14 101 60 41 99 140 94 58 132 30 128 116 44 41 104 7 1 90 75 37 14 95 89 45 116 79 90 86 138 11 7 102 43 87 29 110 127 127 84 26 62 128 107 56 136 47 64 42 124 149 119 71 48 100 40 81 59 11 59 83 62 91 55 4 146 5 73 46 145 117 75 24 20 26 16 97 122...
output:
417911208 97351943 508312273 671488492 300257045 924447116 20804203 895244811 807592393
result:
Test #6:
score: 0
Runtime Error
input:
60 10 180 96 39 136 47 63 77 105 74 67 142 122 70 72 137 143 155 95 156 105 121 37 81 3 159 167 139 130 152 180 88 148 149 114 31 43 112 146 127 84 90 75 27 2 46 128 178 116 69 83 117 135 173 177 118 129 34 127 94 40 174 150 56 99 159 116 43 44 59 32 163 175 131 54 113 50 132 50 83 94 149 88 27 161 ...
output:
588018227 89518503 36429159 568488696
result:
Test #7:
score: 0
Runtime Error
input:
70 10 78 164 105 187 88 118 8 96 82 143 38 127 27 93 18 171 19 158 112 91 179 17 40 15 99 205 113 19 186 16 26 82 4 41 193 5 110 79 201 106 161 59 183 196 123 127 69 37 117 130 88 141 96 93 149 113 176 206 46 195 35 178 102 111 155 41 25 148 150 179 185 61 166 136 118 176 46 50 61 84 124 150 112 185...
output:
574244039
result:
Test #8:
score: 0
Runtime Error
input:
80 10 125 87 139 196 191 41 58 194 2 175 150 76 18 87 1 40 180 166 13 119 159 123 210 135 61 224 142 149 222 216 197 113 234 194 9 231 96 71 198 176 98 36 24 185 235 157 80 122 226 187 42 240 154 171 25 218 195 198 124 50 113 32 91 119 45 141 53 12 74 121 158 96 180 116 145 22 142 133 88 182 16 124 ...
output:
result:
Test #9:
score: 0
Runtime Error
input:
90 10 42 170 5 215 133 153 104 85 9 164 157 42 87 108 64 161 205 168 228 216 257 81 163 68 195 99 234 136 231 142 127 149 86 182 224 219 80 125 7 230 256 41 204 125 251 77 86 29 28 204 55 15 30 35 174 53 269 23 240 127 262 199 260 232 259 46 80 43 49 169 233 88 192 27 217 186 47 185 228 249 63 245 2...
output:
result:
Test #10:
score: 0
Runtime Error
input:
99 10 243 69 109 28 151 100 296 2 258 112 25 206 181 148 21 246 12 84 254 250 91 248 46 14 183 162 38 82 130 48 20 150 139 247 283 24 29 93 191 105 129 38 131 87 147 166 22 297 297 71 232 185 106 123 291 15 63 101 286 214 224 29 187 154 215 292 226 223 225 55 23 170 165 238 137 113 203 79 21 217 289...