C++14(g++5.4) 解法, 执行用时: 932ms, 内存消耗: 740K, 提交时间: 2019-03-09 01:59:37

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=10005,mod=1e9+7;
int a[maxn],b[maxn],n;
int h[maxn],t[maxn];
int inv,k,ans;
int ksm(ll x,int y)
{
	ll res=1;
	while(y)
	{
		if(y&1)res=res*x%mod;
		x=x*x%mod;
		y/=2; 
	}
	return res;
}
void add(int& x,int y)
{
	if(1ll*x+y>=mod)x=x-mod+y;
	else x=x+y;
}
void gao(int cur)
{
	int m=n-cur+1,pre=0,last,o=0,cnt=0;
	for(int i=cur;i<=n;i++)b[a[i]]=cur;
	for(int i=1;i<=n;i++)
	if(b[i]==cur)
	{
		cnt++;
		if(cnt==(m+1)/2)o=i;
		t[pre]=i,h[i]=pre,pre=i;	
	}
	t[pre]=0;
	int res=ksm(k,(cur-1)*n+n);
	for(int i=n;i>=cur;i--)
	{
		if(m%2)add(ans,1ll*res*o*2%mod);
		else add(ans,1ll*res*(o+t[o])%mod);		
		pre=h[a[i]];
		last=t[a[i]];
		t[pre]=last;
		h[last]=pre;
		if(a[i]==o)
		{
			if(m%2)o=h[o];
			else o=t[o];
		}
		else if(a[i]<o)
		{
			if(m%2==0)o=t[o];
		}
		else
		{
			if(m%2)o=h[o];
		}
		m--;
		res=1ll*res*inv%mod;
	}
}
int main()
{
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++)
	scanf("%d",&a[i]);
	inv=ksm(k,mod-2);
	for(int i=1;i<=n;i++)
	gao(i);
	printf("%d\n",ans);
}

C++11(clang++ 3.9) 解法, 执行用时: 513ms, 内存消耗: 868K, 提交时间: 2019-11-21 19:25:00

#include<bits/stdc++.h>
using namespace std;
const int N=20005,P=1e9+7;
int n,m,ans,a[N],b[N],c[N],s[N],cnt[N],p1[N],p2[N];
inline int pw(int a,int b){int r=1;for(;b;b>>=1,a=1ll*a*a%P)if(b&1)r=1ll*r*a%P;return r;}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]),c[a[i]]=i;
	for(int i=p2[0]=1;i<=n;i++)p2[i]=1ll*p2[i-1]*m%P;
	p1[1]=1;for(int i=2;i<=n;i++)p1[i]=1ll*p1[i-1]*p2[n]%P;
	s[0]=10000;
	for(int i=1;i<=n;i++)
	{
		memset(cnt,0,sizeof(cnt));cnt[s[0]]=p1[1];
		for(int j=1;j<c[i];j++)
		{
			b[j]=(i<a[j])-(i>a[j]);s[j]=s[j-1]+b[j];
			cnt[s[j]]=(cnt[s[j]]+p1[j+1])%P;
		}
		for(int j=c[i];j<=n;j++)
		{
			b[j]=(i<a[j])-(i>a[j]);s[j]=s[j-1]+b[j];
			ans=(ans+(2ll*i*cnt[s[j]]+1ll*i*(cnt[s[j]-1]+cnt[s[j]+1]))%P*p2[j])%P;
		}
	}
	printf("%d\n",ans);
	return 0;
}