QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#164717 | #5408. 计数鸡 | Lynkcat# | 30 | 31ms | 4416kb | C++20 | 1.9kb | 2023-09-05 13:10:58 | 2024-07-04 01:52:26 |
Judging History
answer
#include<bits/stdc++.h>
#define poly vector<int>
#define IOS ios::sync_with_stdio(false)
#define ll long long
#define mp make_pair
#define mt make_tuple
#define pa pair < int,int >
#define fi first
#define se second
#define inf 1e18
#define mod 998244353
#define sz(x) ((int)((x).size()))
#define int ll
#define N 305
using namespace std;
int n,p[N],cnt[N],h[N],a[N][N];
int quickPower(int x,int y)
{
int res=1;
while (y)
{
if (y&1) res=res*x%mod;
x=x*x%mod;
y>>=1;
}
return res;
}
void BellaKira()
{
cin>>n;
for (int i=1;i<=n;i++)
cin>>p[i];
for (int i=1;i<=n;i++)
cin>>h[i];
for (int i=n;i>=1;i--)
{
for (int j=1;j<=n;j++)
{
a[i][j]=1;
if (j+h[i]>=0&&cnt[j+h[i]]==1) a[i][j]=mod-1;
}
for (int j=1;j<=n;j++)
cnt[j]^=(j>=p[i]);
}
// for (int i=1;i<=n;i++)
// {
// for (int j=1;j<=n;j++)
// cout<<a[i][j]<<" ";
// cout<<endl;
// }
int ans=1;
for (int i=1;i<=n;i++)
{
if (!a[i][i])
{
for (int j=i;j<=n;j++)
if (a[j][i])
{
swap(a[i],a[j]);
ans=(mod-ans)%mod;
break;
}
}
if (!a[i][i])
{
ans=0;
break;
}
for (int j=i+1;j<=n;j++)
{
int coef=a[j][i]*quickPower(a[i][i],mod-2)%mod;
for (int k=1;k<=n;k++)
a[j][k]=(a[j][k]-coef*a[i][k]%mod+mod)%mod;
}
}
int tmp=1;
for (int i=1;i<=n;i++)
ans=ans*a[i][i]%mod,tmp=tmp*i%mod;
cout<<((ans+tmp)*((mod+1)/2)%mod)<<'\n';
}
signed main()
{
IOS;
cin.tie(0);
int T=1;
while (T--)
{
BellaKira();
}
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 20
Accepted
time: 0ms
memory: 3724kb
input:
20 20 4 15 16 11 3 7 18 9 5 13 8 6 12 2 10 1 17 14 19 -7 -11 9 -3 -20 -13 -18 15 0 8 0 12 -16 -19 8 -9 -4 -2 6 -10
output:
699910446
result:
ok 1 number(s): "699910446"
Test #2:
score: -20
Wrong Answer
time: 0ms
memory: 3644kb
input:
20 11 6 3 18 17 19 4 8 10 15 12 16 1 13 7 14 5 20 9 2 13 9 -1 1 9 -11 -19 8 -5 -11 -4 3 17 1 8 1 0 -11 -16 -10
output:
702531886
result:
wrong answer 1st numbers differ - expected: '694405422', found: '702531886'
Subtask #2:
score: 30
Accepted
Test #11:
score: 30
Accepted
time: 0ms
memory: 3764kb
input:
15 14 4 15 10 11 3 7 1 9 5 13 8 6 12 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
output:
985377138
result:
ok 1 number(s): "985377138"
Test #12:
score: 0
Accepted
time: 0ms
memory: 3712kb
input:
15 1 2 12 4 8 13 6 5 9 3 11 10 7 14 15 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
output:
985385330
result:
ok 1 number(s): "985385330"
Test #13:
score: 0
Accepted
time: 0ms
memory: 3692kb
input:
15 7 13 6 10 3 5 2 15 11 8 9 14 12 1 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
output:
985377138
result:
ok 1 number(s): "985377138"
Test #14:
score: 0
Accepted
time: 0ms
memory: 3632kb
input:
15 1 6 4 2 9 14 13 12 11 15 3 10 7 8 5 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
output:
985385330
result:
ok 1 number(s): "985385330"
Test #15:
score: 0
Accepted
time: 28ms
memory: 4300kb
input:
290 210 151 231 91 180 53 275 208 138 4 251 83 136 247 22 64 104 39 120 218 51 26 203 196 280 153 191 163 161 159 241 175 284 132 17 236 11 211 142 162 107 259 246 257 47 54 165 172 70 274 219 267 289 67 237 286 1 222 194 144 146 281 9 65 89 87 171 5 271 71 285 94 283 81 261 42 260 157 244 213 127 2...
output:
68391778
result:
ok 1 number(s): "68391778"
Test #16:
score: 0
Accepted
time: 31ms
memory: 4348kb
input:
293 1 170 64 256 155 245 196 19 106 108 262 104 235 56 232 6 143 140 226 65 177 202 174 133 193 263 96 191 176 114 113 91 161 290 165 30 128 83 152 53 240 139 12 154 156 118 203 252 90 68 49 208 153 59 21 198 66 280 163 182 105 149 35 79 220 239 236 151 3 276 269 93 127 189 225 237 110 228 212 109 3...
output:
31579777
result:
ok 1 number(s): "31579777"
Test #17:
score: 0
Accepted
time: 26ms
memory: 4368kb
input:
298 164 51 214 25 106 42 2 201 281 189 118 105 76 264 291 39 54 177 176 260 158 85 151 154 107 219 29 224 212 259 92 268 110 203 250 245 138 61 222 49 296 20 33 162 14 225 172 223 43 15 148 272 257 226 4 276 79 114 24 273 91 143 240 282 284 156 115 248 131 86 251 64 231 41 132 200 186 270 187 63 17 ...
output:
882980580
result:
ok 1 number(s): "882980580"
Test #18:
score: 0
Accepted
time: 30ms
memory: 4416kb
input:
291 1 95 126 139 63 31 267 240 237 145 276 179 151 220 69 256 278 208 261 112 289 55 200 155 247 18 284 27 129 169 262 22 61 185 29 175 174 229 249 94 73 2 226 75 147 290 199 110 10 215 124 198 52 93 211 121 137 171 128 64 51 204 186 109 135 254 122 48 26 246 96 236 144 157 23 30 239 263 47 282 148 ...
output:
991645574
result:
ok 1 number(s): "991645574"
Test #19:
score: 0
Accepted
time: 26ms
memory: 4304kb
input:
292 176 103 58 8 252 64 40 157 253 49 22 60 71 234 213 248 122 233 70 226 283 96 92 65 184 73 264 125 140 271 104 175 163 12 159 228 193 151 42 145 269 28 124 158 155 14 261 143 90 185 164 88 285 166 27 255 139 188 4 57 132 37 56 131 23 87 165 216 5 99 211 218 121 138 129 171 34 183 254 225 174 274 ...
output:
605781403
result:
ok 1 number(s): "605781403"
Test #20:
score: 0
Accepted
time: 30ms
memory: 4284kb
input:
290 1 99 242 93 198 161 155 49 56 2 48 43 248 207 239 240 157 138 126 289 81 275 258 70 261 177 171 251 241 112 101 145 109 121 136 15 286 141 260 285 72 271 103 139 63 64 229 129 209 196 42 222 76 53 277 172 162 212 92 265 263 221 4 282 246 182 45 119 132 134 152 175 34 223 226 236 114 183 46 27 59...
output:
595654396
result:
ok 1 number(s): "595654396"
Subtask #3:
score: 0
Skipped
Dependency #1:
0%