相关链接
题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4881
神犇题解:http://krydom.com/bzoj4881/
解题报告
不难发现,这就是一个二分图染色问题
那么我们首先需要判无解
分析题目我们可以发现,如果存在长度为$x+2$的奇环,那么一定存在长度为$x$的奇环
于是我们只需要判有没有长度为$3$的奇环,然后我们发现这就是三个递减的数,于是随便搞一搞就好
至于输出方案数,就是$2$的连通块个数次方
Code
#include<bits/stdc++.h> #define LL long long using namespace std; const int N = 100009; const int MOD = 998244353; int n, p[N], mx[N], mn[N]; stack<int> stk; inline int read() { char c=getchar(); int f=1,ret=0; while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();} while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();} return ret * f; } int main() { n = read(); for (int i = 1; i <= n; i++) { p[i] = read(); } mx[1] = p[1]; for (int i = 2; i <= n; i++) { mx[i] = max(mx[i - 1], p[i]); } mn[n] = p[n]; for (int i = n - 1; i; i--) { mn[i] = min(mn[i + 1], p[i]); } for (int i = 2; i < n; i++) { if (mx[i - 1] > p[i] && p[i] > mn[i + 1]) { puts("0"); exit(0); } } for (int i = 1; i <= n; i++) { if (stk.empty() || stk.top() < p[i]) { stk.push(p[i]); } else { int tt = stk.top(); for (; !stk.empty() && stk.top() > p[i]; stk.pop()); stk.push(tt); } } int ans = 1; for (int i = 1; i <= (int)stk.size(); i++) { ans = (ans << 1) % MOD; } cout<<ans<<endl; return 0; }