QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#164697#5408. 计数鸡Lynkcat#0 0ms3764kbC++201.9kb2023-09-05 13:02:142024-07-04 01:52:25

Judging History

你现在查看的是最新测评结果

  • [2024-07-04 01:52:25]
  • 评测
  • 测评结果:0
  • 用时:0ms
  • 内存:3764kb
  • [2023-09-05 13:02:14]
  • 提交

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%