source : Pertozavodsk Winter Training Camp 2016 Day 1: SPb SU and SPb AU Contest, Friday, January 29, 2016
url:https://codeforces.com/gym/100956/attachments
-----------------------------------------------------
题意:
有一个1~n的全排列p1~pn,问有多少个长度为n的数组,满足
1.数组中每个元素均为1~n的正整数
2.按照全排列的顺序,i从1到n,依次将数组中等于pi的元素拿出来放在新数组末端,完成后新数组为有序的。
-----------------------------------------------------
题解:
样例
3
2 1 3
含1个不同元素的数组:
1:1个
2:1个
3:1个
含2个不同元素的数组:
2,3:2^3-1个
1,3:2^3-1个
解法:
求出原排列中长度为1~n的上升子序列有多少个,记为len[i];
求出严格含1~n个不同元素的n位的数组有多少种,记为f[i];
则ans = sigma(len[i]*f[i])
求len[i]:递推,已知以第j位为结尾的长度为x的上升子序列有sum_prelen[j]个,则以第i位为结尾长度为x+1的上升子序列数量=sigma(sum_prelen[1~i-1])。用树状数组维护。
求f[i]:f[i]=i! - sigma(f[1~i-1])
-------------------------------------------------
代码如下:
#include<bits/stdc++.h>
using namespace std; typedef long long LL;
const int N=;
const LL mod=(LL)1e9+;
int n;
LL c[N],sum_prelen[N],len[N],val[N],jc[N],f[N]; void readin(LL &x)
{
x=;bool f=;char ch=getchar();
while(!isdigit(ch)) {
f|=(ch=='-');
ch=getchar();
}
while(isdigit(ch)) {
x=(x<<)+(x<<)+ch-;
ch=getchar();
}
if(f) x=-x;
} void add(LL x,LL d){
for(int i=x;i<=n;i+=(i&(-i))) c[i]=(c[i]+d)%mod;
}
LL getsum(LL x){
LL ans=;
for(int i=x;i>=;i-=(i&(-i))) ans=(ans+c[i])%mod;
return ans;
} LL mypow(LL x,LL y){
LL ans=;
while(y)
{
if(y&) ans=ans*x%mod;
x=x*x%mod;
y>>=;
}
return ans;
} LL mod_inverse(LL x,LL n){
return mypow(x,n-);
} LL cal_C(LL x,LL y){
// C(x,y)=y!/(x!(y-x)!)
return jc[y] * mod_inverse(jc[x],mod) % mod * mod_inverse(jc[y-x],mod) % mod;
} int main()
{
freopen("a.in","r",stdin);
scanf("%d",&n);
for(int i=;i<=n;i++) readin(val[i]);
for(int i=;i<=n;i++) sum_prelen[i]=;
len[]=n;
for(int i=;i<=n;i++)
{
len[i]=;
for(int j=;j<=n;j++) c[j]=;
for(int j=;j<=n;j++)
{
LL sum_nowlen=getsum(val[j]-);
len[i]=(len[i]+sum_nowlen)%mod;
add(val[j],sum_prelen[j]);
sum_prelen[j]=sum_nowlen;
}
// for(int j=1;j<=n;j++) printf("%lld ",len[j]);printf("\n");
} jc[]=;for(int i=;i<=n;i++) jc[i]=(jc[i-]*((LL)i))%mod;
f[]=;
LL ans=;
for(int i=;i<=n;i++)
{
f[i]=mypow(i,n);
for(int j=;j<i;j++)
f[i]=((f[i]-cal_C(j,i)*f[j]%mod)%mod+mod)%mod;
ans=(ans+len[i]*f[i]%mod)%mod;
} printf("%I64d\n",ans);
return ;
}