双阳区住房和城乡建设局网站,lumen 做企业网站,手机建网站软件,网站开发 实战从题解的角度来说#xff0c;这是一道简单题。不过考场上在没有任何人提示的情况下要想出正确的结论其实并不容易。
我自己做这道题的时候#xff0c;因为没有想清楚题目给出的下界能取到的充要条件是什么#xff0c;所以到了很晚才猜到结论#xff0c;以至于难以为继。
…从题解的角度来说这是一道简单题。不过考场上在没有任何人提示的情况下要想出正确的结论其实并不容易。
我自己做这道题的时候因为没有想清楚题目给出的下界能取到的充要条件是什么所以到了很晚才猜到结论以至于难以为继。
结论当且仅当一个排列不含有长度为333的下降子序列冒泡排序的交换次数取到下界。这也非常好理解因为如果一个位置存在前面一个数比它大后面一个数比它小那么至少会向左/向右移动一次因此取不到下界。
证明需要运用Dilworth\text{Dilworth}Dilworth定理我们可以把原序列划分成两个上升子序列 其中一个子序列的数只会往左移另一个子序列的数只会往右移然后就证完了。
先不考虑字典序的限制。我们将限制转化一下变成不存在一个位置iii使得存在前面的一个数比它大后面的一个数比它小。这直接导出了下面的dpdpdp设dpi,jdp_{i,j}dpi,j表示前iii个位置最大值为jjj的方案数。如果[1:i−1][1:i-1][1:i−1]的最大值为jjj那么pip_ipi只能是[1:j][1:j][1:j]中没填的最小的那一个方案数dpi−1,jdp_{i-1,j}dpi−1,j。否则若[1:i−1][1:i-1][1:i−1]最大值为k(kj)k(kj)k(kj)那么pip_ipi填jjj总是合法的。那么dpi,j∑k≤jdpi−1,k(i≤j)dp_{i,j}\sum_{k\le j}dp_{i-1,k}(i\le j)dpi,j∑k≤jdpi−1,k(i≤j) 。我们发现这就是从(1,1)(1,1)(1,1)走到(n,n)(n,n)(n,n)且不穿过对角线xyxyxy的方案数也就是(2nn)−(2nn−1)\binom{2n}{n}-\binom{2n}{n-1}(n2n)−(n−12n)。
回到原题我们枚举lcp\text{lcp}lcp然后就变成了求从(i,j)(i,j)(i,j)走到(n,n)(n,n)(n,n)的方案数同样可以组合数计算。然后就做完了。
复杂度O(n)O(n)O(n)。
#includebits/stdc.h
#define ll long long
#define pb push_back
using namespace std;
const int mod998244353;
const int N2e65;
int T,n,p[N],vs[N];
ll fac[N],inv[N],bit[N],res;
void add(ll x,ll y){x(xy)%mod;
}
ll fpow(ll x,ll ymod-2){ll z(1);for(;y;y1){if(y1)zz*x%mod;xx*x%mod;}return z;
}
void init(int n){fac[0]1;for(int i1;in;i)fac[i]fac[i-1]*i%mod;inv[n]fpow(fac[n]);for(int in;i1;i--)inv[i-1]inv[i]*i%mod;
}
ll binom(ll x,ll y){return fac[x]*inv[y]%mod*inv[x-y]%mod;
}
ll G(int a,int b,int c,int d){if(cadb)return binom(cd-a-b,c-a);return 0;
}
ll F(int a,int b,int c,int d){if(cadbba){return G(a,b,c,d)-G(b1,a-1,c,d);}return 0;
}
int main(){ ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);init(2e6);cinT;while(T--){cinn;for(int i1;in;i)cinp[i],vs[i]0;res0;int tp0,j1;for(int i0;in;i){add(res,F(i,max(tp,p[i1])1,n,n));while(jnvs[j])j;if(jtpjp[i1]){add(res,F(i1,tp,n,n));}if(p[i1]tpp[i1]!j){break;}tpmax(tp,p[i1]);vs[p[i1]]1;}cout(resmod)%mod\n;}
}
