BZOJ 4574: [Zjoi 2016] 세그먼트 트리/UOJ #196.[ZJOI 2016] 라인 트리 dp

4574: [Zjoi2016] 세그먼트 트리

Time Limit: 30 Sec Memory Limit: 256 MBSubmit: 357 Solved: 117 [Submit][Status][Discuss]

Description

작은 유카가 제목을 만났다. 서열이 하나 있다. a1,a_2,?,a_n,q회 조작, 매번 한 구간 내의 수를 구간 내의 최대치로 바꾸고 마지막 개수가 얼마인지 물어본다.어린 유카는 아주 빠르게 라인 트리를 사용해 이 문제를 해결했다.그래서 지혜로운 꼬마 유카는 만약에 조작이 랜덤이라면 이 q회 조작에서 매번 같은 확률로 랜덤으로 하나의 구간 [l,r](1≤l≤r≤n)을 선택한 다음에 이 구간 내의 수를 구간 내 최대치로 변경한다(이런 구간은 모두 (n(n+1)/2개)/2개가 있으니 주의한다). 마지막 각 수의 기대 크기는 얼마나 될까?유카는 랜덤을 좋아하기 때문에 입력한 서열도 랜덤이다(랜덤으로 데이터 규모와 약속을 볼 수 있다).개수에 대한 기대 곱하기 (((n (n (n + 1)/2) 를 출력합니다 ^q 다시 10
^9+7 모드의 값입니다.

Input

첫 번째 줄은 두 개의 정수 n, q를 포함하고 서열의 개수와 조작의 개수를 나타낸다.다음 1행은 n개의 비음정수 a1, a2 포함...an.N<=400,Q<=400

Output

출력은 모두 1줄로 n개의 정수를 포함하여 각 수의 답안을 표시한다

Sample Input

5 5 1 5 2 3 4

Sample Output

3152671 3796875 3692207 3623487 3515626
나 진짜 전재 잘한다.
여기 엄청 빠른 코드가 있어요.
이것은 bzoj에서 영광 T로 떨어진 코드입니다.

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include

using namespace std;

typedef long long ll;

inline int read()
{
	int x=0,f=1;char ch=getchar();
	while(ch'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch<='9'&&ch>='0'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
	return x*f;
}
void print(ll x)
{if(x<0)putchar('-'),x=-x;if(x>=10)print(x/10);putchar(x%10+'0');}

const int N=410,mod=int(1e9)+7;

int n,q,L,R,rank[N],a[N],pos[N];

ll f[2][N][N],A[N][N],sum[N][N],cnt[N];

void DP(int x)
{
	register int i,j,k;
	for(i=L;i<=R;++i)for(j=L;j<=R;++j)f[0][i][j]=f[1][i][j]=0;
	f[0][L][R]=1;
	for(k=1;k<=q;++k)
	{
		ll val=0;
		for(i=L;i<=R;++i)
		{
			val=0;
			for(j=R;j>=i;j--)
			{f[k&1][i][j]=val;val=(val+f[(k-1)&1][i][j]*(n-j))%mod;}
		}
		for(j=L;j<=R;++j)
		{
			val=0;
			for(i=L;i<=j;++i)
			{f[k&1][i][j]=(f[k&1][i][j]+val)%mod;val=(val+f[(k-1)&1][i][j]*(i-1))%mod;}
		}
		for(i=L;i<=R;++i)for(j=i;j<=R;++j)
		f[k&1][i][j]=(f[k&1][i][j]+f[(k-1)&1][i][j]*A[i][j])%mod;
	}
	for(i=L;i<=R;++i)
	{
		ll val=0;
		for(j=R;j>=i;j--)
		{
			(val+=f[q&1][i][j])%=mod;
			(sum[j][rank[x]]+=val)%=mod;
		}
	}
}

inline bool cmp(int x,int y){return a[x]