NC20524. [ZJOI2016]线段树
描述
输入描述
第一行包含2个正整数n,q，表示序列里数的个数和操作的个数。接下来1行，包含n个非负整数a1,a2...an。N ≤ 400,Q ≤ 400
输出描述
输出共1行，包含n个整数，表示每个数的答案
示例1
输入:
5 5 1 5 2 3 4
输出:
3152671 3796875 3692207 3623487 3515626
C++14(g++5.4) 解法, 执行用时: 617ms, 内存消耗: 3556K, 提交时间: 2020-03-27 00:59:16
#include<bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define ROF(i,a,b) for(int i=(a);i>=(b);--i)
const int mod = 1e9+7;
int g[403][403], ls[403][403], rs[403][403], f[2][403][403], mx;
int n,q,a[500];
inline int v(int x){ return x*(x+1)>>1; }
int main(){
scanf("%d %d", &n, &q);
FOR(i, 1, n) scanf("%d", &a[i]);
a[0] = a[n+1] = mod;
FOR(l, 1, n){
mx = a[l];
FOR(r, l, n) {
mx = max(mx, a[r]);
if(min(a[l-1], a[r+1]) > mx) f[0][l][r] = (mx - min(a[l-1], a[r+1])+mod)%mod;
g[l][r] = (v(r-l+1) + v(l-1) + v(n-r)) % mod;
}
}
int t = 0;
FOR(i,1,q){
t ^= 1;
FOR(r,1,n) FOR(l,1,r) ls[l][r] = (ls[l-1][r]+1ll*(l-1)*f[t^1][l][r])%mod;
ROF(l,n,1) ROF(r,n,l) rs[l][r] = (rs[l][r+1]+1ll*(n-r)*f[t^1][l][r])%mod;
FOR(l,1,n) FOR(r,l,n) f[t][l][r] =(1ll*g[l][r]*f[t^1][l][r] + ls[l-1][r] + rs[l][r+1])%mod;
}
FOR(i,1,n){
int ans = 0;
FOR(l,1,i) FOR(r,i,n) ans = (ans + f[t][l][r])%mod;
printf("%d ",ans);
}
return 0;
}
C++11(clang++ 3.9) 解法, 执行用时: 597ms, 内存消耗: 3684K, 提交时间: 2020-04-01 16:26:53
#include<bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=a;i<=b;++i)
#define ROF(i,a,b) for(int i=a;i>=b;--i)
const int mod=1e9+7;
int g[403][403],ls[403][403],rs[403][403],f[2][403][403],mx;
int n,q,a[500];
inline int v(int x)
{
return x*(x+1)>>1;
}
int main()
{
scanf("%d %d",&n,&q);
FOR(i,1,n) scanf("%d",&a[i]);
a[0]=a[n+1]=mod;
FOR(l,1,n)
{
mx=a[l];
FOR(r,l,n)
{
mx=max(mx,a[r]);
if(min(a[l-1],a[r+1])>mx)
f[0][l][r]=(mx-min(a[l-1],a[r+1])+mod)%mod;
g[l][r]=(v(r-l+1)+v(l-1)+v(n-r))%mod;
}
}
int t=0;
FOR(i,1,q)
{
t^=1;
FOR(r,1,n)
FOR(l,1,r)
ls[l][r]=(ls[l-1][r]+1ll*(l-1)*f[t^1][l][r])%mod;
ROF(l,n,1)
ROF(r,n,l)
rs[l][r]=(rs[l][r+1]+1ll*(n-r)*f[t^1][l][r])%mod;
FOR(l,1,n)
FOR(r,l,n)
f[t][l][r]=(1ll*g[l][r]*f[t^1][l][r]+ls[l-1][r]+rs[l][r+1])%mod;
}
FOR(i,1,n)
{
int ans=0;
FOR(l,1,i)
FOR(r,i,n)
ans=(ans+f[t][l][r])%mod;
printf("%d ",ans);
}
return 0;
}