USACO 2019 JAN Platinum 3 -- Train Tracking 2

发表于 | 更新于 | 分类于 | 评论数：

摘要

给你滑动窗口各位置的区间min，求原序列方案数

Pickupwin: 无从下手啊

Sol: 考虑下为什么区间min会变化

题面

解

官方题解

首先考虑所有值都相等，可以DP

一个变化代表确定某个位置的值，最终未确定的段就是上面的DP

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include <cstdio>

const int MOD=1000000007;
const int MAX=1000000000;
const int MAXN=5000011;

inline int mul(const int &a, const int &b){
	return (int)((1LL*a*b)%(long long)(MOD));
}

int pow(int t, int k){
	int r=1;
	while(k){
		if(k&1)	r=mul(r, t);
		t=mul(t, t);
		k>>=1;
	}
	return r;
}

inline void add(int &f, const int &v){
	f+=v;if(f>=MOD)	f-=MOD;
}

int N, K;

int Ans[MAXN];

int V[MAXN];

int F_[MAXN], *F=&F_[1];

int Deal(int l, int v){
	//printf("%d %d\n", l, v);
	if(l<=0)	return 1;
	int x=MAX-v;
	if(l<K)	return pow(x+1, l);
	F[-1]=1;F[0]=1;
	for(int i=1;i<K;++i)
		F[i]=mul(F[i-1], x+1);
	int tmp=pow(x, K-1);
	for(int i=K;i<=l;++i){
		F[i]=F[i-1];
		add(F[i], MOD-mul(F[i-K-1], tmp));
		F[i]=mul(F[i], x);
		add(F[i], F[i-1]);
	}
	return F[l];
}

int main(){
	
	freopen("tracking2.in", "r", stdin);
	freopen("tracking2.out", "w", stdout);
	
	scanf("%d%d", &N, &K);
	
	for(int i=1;i<=N-K+1;++i)	scanf("%d", &V[i]);
	
	for(int i=1;i<N-K+1;++i){
		if(V[i]<V[i+1])	Ans[i]=V[i];
		if(V[i]>V[i+1])	Ans[i+K]=V[i+1];
	}
	
	int ANS=1;
	
	int p=0;
	for(int i=1;i<=N;++i){
		if(Ans[i]){
			ANS=mul(ANS, Deal((i-1)-(p+1)+1, (Ans[i]<Ans[p])?(V[i-K]):((p+1)>(N-K+1)?V[N-K+1]:V[p+1])));
			p=i;
		}
	}
	ANS=mul(ANS, Deal(N-(p+1)+1, V[N-K+1]));
	
	printf("%d\n", ANS);
	
	return 0;
}

/*
6 3
999999998
999999999
999999998
999999998


*/