企业网站管理系统下载,什么是网络营销环境,北京建站公司哪家好,大型门户网站设计前言
这里是线性做法。 在题解里几句话说清楚的性质愣是推了一上午。 too vegetable
解析
考虑怎样的排列是不合法的。 一个排列如果不合法#xff0c;也就是在某次交换时其中一个元素距离目标的距离没有减少反而增大了#xff0c;那么以后这个数一定会再换回来#xff0…前言
这里是线性做法。 在题解里几句话说清楚的性质愣是推了一上午。 too vegetable
解析
考虑怎样的排列是不合法的。 一个排列如果不合法也就是在某次交换时其中一个元素距离目标的距离没有减少反而增大了那么以后这个数一定会再换回来也就是这个数会反复横跳。 考虑怎样的数会反复横跳不难发现会反复横跳也就等价于左边有比自己大的元素右边有比自己小的元素也就是存在长度为三的递减子序列。 所以可以抽象出合法的充要条件不存在长度为三的递减子序列也就等价于排列可以拆分为两个递增序列。
这咋算啊 打一下表发现没有字典序的时候答案就是卡特兰数。 为什么呢 尝试往上嗯套。设 mximaxj1iajmx_i\max_{j1}^ia_jmximaxj1iaj那么一个排列就可以理解为所有的 (mxi,i)(mx_i,i)(mxi,i) 的点顺次连接的路径不难发现它和卡特兰数所谓“ (0,0)−(n,n)(0,0)-(n,n)(0,0)−(n,n) 且不超过对角线上方” 的路径是双射的。
那么本题就好办了暴力枚举第一个比给出排列大的位置那么此时必然需要更新 mximx_imxi设 f((a,b)−(c,d))f((a,b)-(c,d))f((a,b)−(c,d)) 是从 (a,b)(a,b)(a,b) 走到 (c,d)(c,d)(c,d) 且不超过对角线的方案数可以通过翻折容斥 O(1)O(1)O(1) 求解那么这里的方案数就是 ∑jmxi1nf((j,i)−(n,n))f((mxi1,i−1)−(n,n))\sum_{jmx_i1}^nf((j,i)-(n,n))f((mx_i1,i-1)-(n,n))∑jmxi1nf((j,i)−(n,n))f((mxi1,i−1)−(n,n))。一直到给出排列的前缀一定无法拆分为两个递增序列是退出。 总复杂度 O(n)O(n)O(n)。
代码
#includebits/stdc.h
using namespace std;
#define ll long long
#define ull unsigned long long
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define ok debug(line: %d\n,__LINE__)inline ll read(){ll x(0),f(1);char cgetchar();while(!isdigit(c)) {if(c-)f-1;cgetchar();}while(isdigit(c)) {x(x1)(x3)c-0;cgetchar();}return x*f;
}
bool mem1;const int N2e6100;
const int inf1e9100;
const int mod998244353;
const bool Flag0;#define add(x,y) ((((x)(y))mod)((x)-mod))
inline ll ksm(ll x,ll k){ll res(1);while(k){if(k1) resres*x%mod;xx*x%mod;k1;}return res;
}int n;int a[N];
ll jc[N],ni[N];
void init(int n){jc[0]1;for(int i1;in;i) jc[i]jc[i-1]*i%mod;ni[n]ksm(jc[n],mod-2);for(int in-1;i0;i--) ni[i]ni[i1]*(i1)%mod;
}
inline int C(int n,int m){return nm||m0?0:jc[n]*ni[m]%mod*ni[n-m]%mod;
}inline int walk(int i,int j){return (C(n-in-j,n-i)mod-C(n-1-in1-j,n-1-i))%mod;
}
bool vis[N];
void work(){nread();for(int i1;in;i) a[i]read(),vis[i]0;int mx(0),sec(1);int ans(0);for(int i1;in;i){vis[a[i]]1;if(a[i]mx) mxa[i];else if(a[i]!sec){add(ans,walk(mx1,i-1));break;}while(vis[sec]) sec;add(ans,walk(mx1,i-1));}printf(%lld\n,ans);
}bool mem2;
signed main(){
#ifndef ONLINE_JUDGEfreopen(a.in,r,stdin);freopen(a.out,w,stdout);
#endifinit(2e6);int Tread();while(T--) work();return 0;
}
