QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#89245#1839. JokeeyiigjknWA 3ms3612kbC++142.1kb2023-03-19 13:36:012023-03-19 13:36:05

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-03-19 13:36:05]
  • 评测
  • 测评结果:WA
  • 用时:3ms
  • 内存:3612kb
  • [2023-03-19 13:36:01]
  • 提交

answer

# include <bits/stdc++.h>
using namespace std;
using ll=long long;
using Poly=vector<int>;
constexpr int mod=988244353;
int a[110],b[110],p[110],c1[110],c2[110],fac[110],inv[110],f[110],g[110][110],y[110];
inline void add(int &x,const auto &y){x=(x+y)%mod;}
Poly operator+(const Poly &F,const Poly &G)
{
	int n=F.size(),m=G.size();
	Poly H(max(n,m));
	copy(F.begin(),F.end(),H.begin());
	for(int i=0;i<m;i++) add(H[i],G[i]);
	return H;
}
Poly operator*(const Poly &F,const int &x)
{
	Poly G=F;
	for(int &i:G) i=(ll)i*x%mod;
	return G;
}
Poly operator*(const Poly &F,const Poly &G)
{
	int n=F.size(),m=G.size();
	Poly H(n+m-1);
	for(int i=0;i<n;i++)
		for(int j=0;j<m;j++)
			add(H[i+j],(ll)F[i]*G[j]);
	return H;
}
Poly div(Poly F,const int &a)
{
	int n=F.size();
	Poly G(n-1);
	for(int i=n-1;i;i--) G[i-1]=F[i],add(F[i-1],(ll)a*F[i]);
	return G;
}
Poly Langrange(int n)
{
	Poly mul={1},F;
	for(int i=0;i<=n;i++) mul=mul*Poly{mod-i,1};
	for(int i=0;i<=n;i++)
	{
		Poly G=div(mul,i)*y[i];
		for(int j=0;j<i;j++) G=G*inv[i-j];
		for(int j=n;j>i;j--) G=G*(mod-inv[j-i]);
		F=F+G;
	}
	return F;
}
int main()
{
	int n,ans=0;
	cin>>n;
	fac[0]=fac[1]=inv[1]=1;
	for(int i=2;i<=n;i++) fac[i]=(ll)fac[i-1]*i%mod;
	for(int i=2;i<=n;i++) inv[i]=(ll)(mod-mod/i)*inv[mod%i]%mod;
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	for(int i=1;i<=n;i++) scanf("%d",&b[i]);
	for(int i=1;i<=n;i++) p[a[i]]=b[i];
	p[n+1]=n+1;
	fill(c1+1,c1+n+1,1);
	fill(c2+1,c2+n+1,1);
	for(int i=1;i<=n;i++)
		if(p[i]) c1[i]=c2[p[i]]=0;
	partial_sum(c1+1,c1+n+2,c1+1);
	partial_sum(c2+1,c2+n+2,c2+1);
	for(int x=0;x<=n;x++)
	{
		for(int i=0;i<=n;i++) g[i][0]=g[0][i]=1;
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++)
				g[i][j]=(g[i-1][j]+g[i][j-1]+(ll)(mod+x-1)*g[i-1][j-1])%mod;
		f[0]=1;
		for(int i=1;i<=n+1;i++)
		{
			if(!p[i]) continue;
			for(int j=0;j<i;j++)
				if(p[j]<p[i]) add(f[i],(ll)f[j]*g[c1[i]-c1[j]][c2[p[i]]-c2[p[j]]]);
		}
		y[x]=f[n+1];
		memset(f,0,sizeof(int)*(n+2));
	}
	Poly F=Langrange(n);
	for(int i=0,sz=F.size();i<sz && i<=c1[n];i++) add(ans,(ll)F[i]*fac[c1[n]-i]);
	cout<<ans<<endl;
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3396kb

input:

2
1 2
2 1

output:

3

result:

ok 1 number(s): "3"

Test #2:

score: 0
Accepted
time: 2ms
memory: 3508kb

input:

4
4 3 2 1
4 3 2 1

output:

16

result:

ok 1 number(s): "16"

Test #3:

score: 0
Accepted
time: 2ms
memory: 3392kb

input:

5
1 2 3 4 5
0 0 0 0 0

output:

1546

result:

ok 1 number(s): "1546"

Test #4:

score: 0
Accepted
time: 2ms
memory: 3492kb

input:

6
1 6 2 5 3 4
0 1 0 2 0 3

output:

52

result:

ok 1 number(s): "52"

Test #5:

score: 0
Accepted
time: 2ms
memory: 3520kb

input:

10
8 2 10 3 4 6 1 7 9 5
0 0 0 0 0 0 0 0 0 0

output:

234662231

result:

ok 1 number(s): "234662231"

Test #6:

score: 0
Accepted
time: 0ms
memory: 3612kb

input:

10
5 8 4 9 6 1 2 7 3 10
8 3 0 5 0 9 0 0 6 0

output:

5294

result:

ok 1 number(s): "5294"

Test #7:

score: 0
Accepted
time: 1ms
memory: 3572kb

input:

10
4 2 6 9 5 3 8 1 10 7
0 9 8 0 7 3 4 2 1 10

output:

166

result:

ok 1 number(s): "166"

Test #8:

score: 0
Accepted
time: 2ms
memory: 3516kb

input:

10
8 2 7 1 5 9 3 4 10 6
7 0 2 9 5 1 8 4 3 6

output:

26

result:

ok 1 number(s): "26"

Test #9:

score: 0
Accepted
time: 3ms
memory: 3516kb

input:

10
10 1 6 7 9 8 4 3 5 2
2 5 1 3 9 10 4 8 6 7

output:

47

result:

ok 1 number(s): "47"

Test #10:

score: -100
Wrong Answer
time: 1ms
memory: 3520kb

input:

50
41 15 17 1 5 31 7 38 30 39 43 35 2 26 20 42 48 25 19 32 50 4 8 10 44 12 9 18 13 36 28 6 27 23 40 24 3 14 29 11 49 47 45 46 34 21 37 16 22 33
0 0 0 0 0 0 0 0 0 33 34 0 0 0 0 0 0 0 0 0 0 2 0 0 0 20 0 0 28 0 0 0 9 0 0 0 48 0 0 0 50 0 0 0 0 5 0 0 32 0

output:

691900132

result:

wrong answer 1st numbers differ - expected: '976189245', found: '691900132'