QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#164697 | #5408. 计数鸡 | Lynkcat# | 0 | 0ms | 3764kb | C++20 | 1.9kb | 2023-09-05 13:02:14 | 2024-07-04 01:52:25 |
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],cnt[p[i]]^=1;
for (int i=1;i<=n;i++) cnt[i]^=cnt[i-1];
for (int i=1;i<=n;i++)
cin>>h[i];
for (int i=n;i>=1;i--)
{
for (int j=1;j<=n;j++)
cnt[j]^=(j>=p[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 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();
}
}
详细
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 20
Accepted
time: 0ms
memory: 3616kb
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: 3764kb
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:
699910446
result:
wrong answer 1st numbers differ - expected: '694405422', found: '699910446'
Subtask #2:
score: 0
Wrong Answer
Test #11:
score: 30
Accepted
time: 0ms
memory: 3616kb
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: -30
Wrong Answer
time: 0ms
memory: 3620kb
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:
985377138
result:
wrong answer 1st numbers differ - expected: '985385330', found: '985377138'
Subtask #3:
score: 0
Skipped
Dependency #1:
0%