题意: 给定长度为 n 的数列 a, 显然这个数列有很多最长上升子序列, 我们等概率地取出一个最长上升子序列, 求每个数被选中的概率, 对 998244353 取模.
链接: https://nanti.jisuanke.com/t/39611
题外话: 勉强混了个前 400 拿 T 恤, 中间麻将题不知道为什么常数奇大无比调了好久, 导致比赛时候这个题没做出来. 看了题解发现是个 sb 题简单题. 我真的是弱啊.
思路: 会用线段树求最长上升子序列就会这个了, 思路是从左到右扫一遍, 线段树维护以 a[i] 结尾的最长上升子序列的方案数, 显然一颗线段树或者 bit 都可以, 单点修改前缀查询. 同样的方法右边再来一次. 最后直接就可以得出答案了 --- 一个点在多少个最长上升子序列里 / 总上升子序列.
代码:
- #include <bits/stdc++.h>
- #define LL long long
- #define inf 1000000007
- #define pii pair<int,int>
- #define mod 998244353
- #define PB insert
- #define X first
- #define Y second
- using namespace std;
- const int maxn=1e7+7;
- namespace seg_tree{
- int len[maxn],lson[maxn],rson[maxn];
- long long sum[maxn];
- int N=0;
- const int root=0;
- void init(){
- memset(len,0,sizeof(len));
- memset(sum,0,sizeof(sum));
- memset(lson,-1,sizeof(lson));
- memset(rson,-1,sizeof(rson));
- N=1;
- }
- void push_up(int rt){
- int l=lson[rt],r=rson[rt];
- if(len[l]==len[r]){
- len[rt]=len[l],sum[rt]=(sum[l]+sum[r])%mod;
- }
- else{
- if(len[l]<len[r])swap(l,r);
- len[rt]=len[l],sum[rt]=sum[l];
- }
- }
- void make_rt(int &x){
- x=N++;
- len[x]=sum[x]=0;
- }
- void add(int rt,int l,int r,int x,int le,long long su){
- if(l==r){
- if(len[rt]==le){
- sum[rt]=(sum[rt]+su)%mod;
- }
- else if(len[rt]<le){
- len[rt]=le;
- sum[rt]=su;
- }
- return;
- }
- if(lson[rt]==-1)make_rt(lson[rt]);
- if(rson[rt]==-1)make_rt(rson[rt]);
- int mid = (l + r) / 2;
- if(x<=mid) add(lson[rt],l,mid,x,le,su);
- else add(rson[rt],mid+1,r,x,le,su);
- push_up(rt);
- }
- pii query(int rt,int l,int r,int x){
- if(r<=x){
- return {len[rt],sum[rt]};
- }
- if(lson[rt]==-1)make_rt(lson[rt]);
- if(rson[rt]==-1)make_rt(rson[rt]);
- int mid = (l + r) / 2;
- if(x<=mid){
- return query(lson[rt],l,mid,x);
- }
- else{
- pii a=query(lson[rt],l,mid,x);
- pii b=query(rson[rt],mid+1,r,x);
- if(a.X==b.X){
- return {a.X,(a.Y+b.Y)%mod};
- }
- else{
- if(a.X<b.X) swap(a,b);
- return a;
- }
- }
- }
- }
- LL q_pow(LL a,int n,int p){
- LL r=1;
- while(n){
- if(n&1) r=(r*a)%p;
- a=(a*a)%p;
- n>>=1;
- }
- return r;
- }
- int a[maxn];
- pii l[maxn],r[maxn];
- int main(){
- int n,L=0,R=1e9+7;
- pii mx;
- cin>>n;
- for(int i=0;i<n;i++)cin>>a[i];
- seg_tree::init();
- seg_tree::add(seg_tree::root,L,R,a[0],1,1);
- l[0]={1,1};
- for(int i=1;i<n;i++){
- pii p=seg_tree::query(seg_tree::root,L,R,a[i]-1);
- if(p.X==0) p={0,1};
- seg_tree::add(seg_tree::root,L,R,a[i],p.X+1,p.Y);
- l[i]={p.X+1,p.Y};
- }
- mx=seg_tree::query(seg_tree::root,L,R,R);
- seg_tree::init();
- seg_tree::add(seg_tree::root,L,R,R-a[n-1],1,1);
- r[n-1]={1,1};
- for(int i=n-2;i>=0;i--){
- pii p=seg_tree::query(seg_tree::root,L,R,R-a[i]-1);
- if(p.X==0) p={0,1};
- seg_tree::add(seg_tree::root,L,R,R-a[i],p.X+1,p.Y);
- r[i]={p.X+1,p.Y};
- }
- for(int i=0;i<n;i++){
- if(r[i].X+l[i].X-1==mx.X){
- cout<<((long long)r[i].Y*l[i].Y%mod)*q_pow(mx.Y,mod-2,mod)%mod<<"\n"[i==n-1];
- }
- else{
- cout<<0<<"\n"[i==n-1];
- }
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3098640.html