@ysner
2018-08-25T22:16:25.000000Z
字数 4330
阅读 2273
DP
计数
排列
模拟即可。
当然如果忘了答案清的话。。。。
手玩下样例,可以感受到:当交换次数达到下限时,每个数到自己位置的过程中不需要折返。
这就需要保证,一个数被交换过一遍后,不能被反方向交换。
这种情况只有在前面有数比它大,后面有数比它小的的情况下才能实现。
想想冒泡排序就是交换逆序对。。。
可得结论:当交换次数达到下限时,序列中不存在长度超过的下降子序列。
注意到,可以状压。
设表示在某种符合条件的排列中,已经填完的数(包括当前这一次)的集合为。
然后显然可得出这一次填数之前的集合。
(模拟序列从前往后填数的过程)
于是要从转移到。
填了前几位数可从中得出,设此为。
肯定要枚举当前这一位填了哪个数。
如果,就说明后面一定有比它小的数,此时判掉前面填了比它大的数的情况。
如果,就说明前面一定有比它大的数,此时判掉后面填了比它小的数的情况。
如果,若前面有比它大的数,后面就一定有比它小的数,随便选一种情况判掉即可。
答案有严格大于的限制?
加一维看当前填出的序列是否比原来序列的字典序大,限制下转移即可。
代码整合在下一档部分分的代码里。
这种限制,相当于使题目只给出一个。
大概率可以打表。
发现答案是第个卡特兰数。
卡特兰数公式是。
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#define ll long long
#define re register
#define il inline
#define pf(a) ((ll)(a)*(a))
#define max(a,b) (((a)>(b))?(a):(b))
#define min(a,b) (((a)<(b))?(a):(b))
#define fp(i,a,b) for(re int i=a;i<=b;i++)
#define fq(i,a,b) for(re int i=a;i>=b;i--)
using namespace std;
const int mod=998244353,N=2e6+100;
int n,a[N],f[2][1<<20],tag,jc[N];
il ll gi()
{
re ll x=0,t=1;
re char ch=getchar();
while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
if(ch=='-') t=-1,ch=getchar();
while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
return x*t;
}
il ll ksm(re ll S,re ll n)
{
re ll T=S;S=1;
while(n)
{
if(n&1) S=S*T%mod;
T=T*T%mod;
n>>=1;
}
return S;
}
il void solve()
{
jc[0]=1;fp(i,1,n*2) jc[i]=1ll*jc[i-1]*i%mod;
re ll ans=1ll*jc[n*2]*ksm(1ll*jc[n]*jc[n]%mod,mod-2)%mod*ksm(n+1,mod-2)%mod-1;
if(ans<0) ans+=mod;
printf("%lld\n",ans);
}
int main()
{
re int T=gi();
while(T--)
{
tag=1;
n=gi();
fp(i,1,n) a[i]=gi(),tag&=(a[i]==i);
if(tag) {solve();continue;}
memset(f,0,sizeof(f));
f[1][0]=1;
fp(S,1,(1<<n)-1)
{
re int t=0,p=S;
while(p) p-=p&-p,++t;
fp(i,1,n)
{
if(!(S&(1<<i-1))) continue;
re int g=S^(1<<i-1);
if(i>t&&g>((1<<i-1)-1)) continue;
if(i<=t&&(g&((1<<i-1)-1))!=(1<<i-1)-1) continue;
if(a[t]==i) (f[0][S]+=f[0][g])%=mod,(f[1][S]+=f[1][g])%=mod;
else
{
(f[0][S]+=f[0][g])%=mod;
if(a[t]<i) (f[0][S]+=f[1][g])%=mod;
}
}
}
printf("%d\n",f[0][(1<<n)-1]);
}
return 0;
}
考虑二维状态的。
发现存下每个数的使用状态是没有必要的。
实际上,我们每次能够填入的数只有两种:
易证其它情况一定不合法。
根据条件,状态应该设为表示填了前个数,没填的数中有个比前面的数大。
边界当然是
则转移就是
代码整合在下一档部分分的代码里。
复杂度瓶颈在计算上,想办法优化。
看着那个很匀称的递推式,是不是能想到什么东西?
有点像在网格图中,从出发,只能往右或往上走,中间坐标不能出现的情况,到的方案数?
该限制条件相当于路径不能越过(触碰)这条线。
这是个组合数学中的经典模型,
答案是,在只能往右或往上走的前提下,点到点的方案数点到点的方案数(即用合法方案减去所有不合法方案)
则
最后可以通过记忆化和预处理一部分逆元来卡常。
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#define ll long long
#define re register
#define il inline
#define pf(a) ((ll)(a)*(a))
#define max(a,b) (((a)>(b))?(a):(b))
#define min(a,b) (((a)<(b))?(a):(b))
#define fp(i,a,b) for(re int i=a;i<=b;i++)
#define fq(i,a,b) for(re int i=a;i>=b;i--)
using namespace std;
const int mod=998244353,N=1e6+2e5+100,M=N;
int n,a[N],jc[N],inv[M],gu[N],tag,F[1010][1010];
bool vis[N];
il ll gi()
{
re ll x=0,t=1;
re char ch=getchar();
while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
if(ch=='-') t=-1,ch=getchar();
while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
return x*t;
}
il ll ksm(re int p)
{
if(jc[p]<=M-100) return inv[jc[p]];
if(~gu[p]) return gu[p];
re ll T=jc[p],S=1,n=mod-2;
while(n)
{
if(n&1) S=S*T%mod;
T=T*T%mod;
n>>=1;
}
return gu[p]=S;
}
il ll getF(re ll n,re ll m)
{
re int c1=jc[n+m-2];
re ll ans=(1ll*c1*ksm(n-1)%mod*ksm(m-1)%mod+mod-1ll*c1*ksm(n)%mod*ksm(m-2)%mod)%mod;
if(ans<0) ans+=mod;
return ans;
}
il void solve1()
{
fp(i,1,n) vis[i]=0;
if(!F[1][1])
{
F[1][1]=1;
fp(i,2,1001)
fp(j,1,i)
F[i][j]=(F[i][j-1]+F[i-1][j])%mod;
}
re int flag=1,mx=0,ans=0,p=1;
fq(o,n,1)
if(flag)
{
re int i=n-o+1;
(ans+=F[o+1][n-max(a[i],mx)])%=mod;
if(a[i]<mx&&a[i]>p) flag=0;
mx=max(mx,a[i]);
vis[a[i]]=1;
while(vis[p]) ++p;
}
printf("%d\n",ans);
}
il void solve2()
{
memset(vis,0,sizeof(vis));
re int flag=1,mx=0,ans=0,p=1;
fq(o,n,1)
if(flag)
{
re int i=n-o+1;
(ans+=getF(o+1,n-max(a[i],mx)))%=mod;
if(a[i]<mx&&a[i]>p) flag=0;
mx=max(mx,a[i]);
vis[a[i]]=1;
while(vis[p]) ++p;
}
printf("%d\n",ans);
}
il void Pre()
{
memset(gu,-1,sizeof(gu));
tag=1;
jc[0]=1;fp(i,1,N-100) jc[i]=1ll*jc[i-1]*i%mod;
inv[1]=1;fp(i,2,M-100) inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;
}
int main()
{
re int T=gi();
while(T--)
{
n=gi();if(n>1000&&!tag) Pre();
fp(i,1,n) a[i]=gi();
if(n<=1000) solve1();
else
solve2();
}
return 0;
}