打卡信奥刷题（3174）用C++实现信奥题 P7972 [KSN2021] Self Permutation

P7972 [KSN2021] Self Permutation

题目描述

给定一个长度为NNN的排列aia_iai​，你可以执行若干次操作：

• 选择两个相邻的数，删除它们中较大的那个。

问最后可能得到序列的数量，答案对109+710^9+7109+7取模。

注意如果两个数中间所有的数被删除了，它们会变成相邻的。

输入格式

第一行输入一个正整数NNN。

第二行输入NNN个正整数aia_iai​。

输出格式

输出一个整数代表答案。

输入输出样例 #1

输入 #1

3 2 3 1

输出 #1

3

输入输出样例 #2

输入 #2

4 2 1 4 3

输出 #2

6

说明/提示

【样例解释】

对于第一组样例，以下为所有可能得到的序列：

• [2,3,1][2,3,1][2,3,1]
• [2,3,1]→[2,1][\bold2,\bold3,1]\to[2,1][2,3,1]→[2,1]
• [2,3,1]→[2,1]→[1][\bold2,\bold3,1]→[\bold2,\bold1]→[1][2,3,1]→[2,1]→[1]

对于第二组样例，以下为所有可能得到的序列：

• [2,1,4,3][2,1,4,3][2,1,4,3]
• [2,1,4,3]→[1,4,3][\bold2,\bold1, 4, 3]\to[1, 4, 3][2,1,4,3]→[1,4,3]
• [2,1,4,3]→[1,4,3]→[1,3][\bold2,\bold1, 4, 3]\to[1,\bold4,\bold3]\to[1, 3][2,1,4,3]→[1,4,3]→[1,3]
• [2,1,4,3]→[1,4,3]→[1,3]→[1][\bold2,\bold1, 4, 3]\to[1,\bold4,\bold3]\to[\bold1,\bold3]\to[1][2,1,4,3]→[1,4,3]→[1,3]→[1]
• [2,1,4,3]→[2,1,3][2, 1,\bold4,\bold3]\to[2, 1, 3][2,1,4,3]→[2,1,3]
• [2,1,4,3]→[2,1,3]→[2,1][2, 1,\bold4,\bold3]\to[2,\bold1,\bold3]\to[2, 1][2,1,4,3]→[2,1,3]→[2,1]

【数据范围】

本题采用捆绑测试。

• Subtask 1（8 points）：只存在一组数据，满足N=6N=6N=6，A=[2,5,1,3,4,6]A=[2,5,1,3,4,6]A=[2,5,1,3,4,6]。
• Subtask 2（20 points）：N≤200N\leq 200N≤200。
• Subtask 3（13 points）：N≤2000N\leq 2000N≤2000，Ai=iA_i=iAi​=i。
• Subtask 4（9 points）：Ai=iA_i=iAi​=i。
• Subtask 5（23 points）：N≤2000N\leq 2000N≤2000。
• Subtask 6（27 points）：无特殊限制。

对于所有数据，N≤3×105N\leq 3\times 10^5N≤3×105，保证输入的aia_iai​能构成一个排列。

C++实现

#include<bits/stdc++.h>usingnamespacestd;usingii=pair<int,int>;constintN=3e5+10;constintmod=1e9+7;intn,a[N];intdp[N],sum[N];// sum 是前缀和intmain(){ios::sync_with_stdio(0);cin.tie(0);cin>>n;for(inti=1;i<=n;++i)cin>>a[i];set<ii>s;sum[0]=1;for(inti=1,res=0;i<=n;++i){// res 维护的是当前 set 内 dp 值之和ii u;while(!s.empty()){u=(*s.rbegin());if(u.first>a[i]){res=(res-dp[u.second]+mod)%mod;s.erase(u);}elsebreak;}if(s.empty())dp[i]=sum[i-1];elsedp[i]=(res+sum[i-1]-sum[u.second])%mod;if(dp[i]<0)dp[i]+=mod;sum[i]=(sum[i-1]+dp[i])%mod;s.insert({a[i],i});res=(res+dp[i])%mod;}intans=0;for(ii u:s)ans=(ans+dp[u.second])%mod;cout<<ans<<endl;return0;}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容