来自FallDream的博客,未经允许,请勿转载,谢谢。
quailty和tangjz正在玩一个关于线段的游戏。在平面上有n条线段,编号依次为1到n。其中第i条线段的两端点坐标分别为(0,i)和(1,p_i),其中p_1,p_2,...,p_n构成了1到n的一个排列。quailty先手,他可以选择一些互不相交的线段,将它们拿走,当然他也可以一条线段也不选。然后tangjz必须拿走所有剩下的线段,若有两条线段相交,那么他就输了,否则他就赢了。注意若quailty拿走了全部线段,那么tangjz也会胜利。quailty深深喜欢着tangjz,所以他不希望tangjz输掉游戏,请计算他有多少种选择线段的方式,使得tangjz可以赢得游戏。
n<=100000
这道题挺有意思的233
如果把线段只要有相交的就成一个块,可以得到很多块。答案应该是2^块的个数次方。
特判无解,也就是如果有三条或者更多的线段互相交织,那么显然无解。只需要对每个块做一次,维护当前右端点最大值,和当前最右的那条线段相交的右端点的最大值即可判定。
网上好像有一些看起来比较靠谱的做法 但是我这个扫一遍就行了,复杂度O(n)
轻松rank1
#include<iostream>
#include<cstdio>
#define getchar() (S==T&&(T=(S=B)+fread(B,1,1<<15,stdin),S==T)?0:(*S++))
char B[<<],*S=B,*T=B;
#define mod 998244353
using namespace std;
inline int read()
{
int x = ; char ch = getchar();
while(ch < '' || ch > '') ch = getchar();
while(ch >= '' && ch <= ''){x = x * + ch - '';ch = getchar();}
return x;
} int ans=,n,a[],pre=;
bool flag=; inline int pow(int x,int k)
{
int sum=;
for(;k;k>>=,x=1LL*x*x%mod)
if(k&) sum=1LL*sum*x%mod;
return sum;
} inline void Solve(int l,int r)
{
int mx=,Mx=;
for(register int i=l;i<=r&&!flag;++i)
{
if(a[i]<mx&&a[i]<Mx) flag=;
if(a[i]>mx) mx=a[i],Mx=;
else if(a[i]>Mx) Mx=a[i];
}
} int main()
{
n=read();
for(register int i=,Mx=;i<=n&&!flag;Mx=max(Mx,a[i++]))
if((a[i]=read())==i&&Mx<i) Solve(pre+,i-),ans+=+(pre!=i-),pre=i;
Solve(pre+,n);if(pre!=n) ++ans;
printf("%d\n",flag?:pow(,ans));
return ;
}