编程题
#include
using namespace std;
typedef pair pi;
typedef long long ll;
typedef vector vi;
#define mp make_pair
#define sz(x) (int)x.size()
#define pb push_back
#define f first
#define s second
const int MOD = 1000000007;
const int MX = 1000000000;
int ad(int a, int b, int mod = MOD) { return (a+b)%mod; }
int sub(int a, int b, int mod = MOD) { return (a-b+mod)%mod; }
int mul(int a, int b, int mod = MOD) { return ((ll)a*b)%mod; }
int AD(int& a, int b, int mod = MOD) { return a = ad(a,b,mod); }
int SUB(int& a, int b, int mod = MOD) { return a = sub(a,b,mod); }
int MUL(int& a, int b, int mod = MOD) { return a = mul(a,b,mod); }
int countseq(int mnval, int K, int len){
int succ = MX - mnval;
int DP[len + 2];
int pows[K + 1];
int powslow[K + 1];
pows[0] = 1;
powslow[0] = 1;
for (int i = 1; i <= K; i++){
pows[i] = mul(pows[i - 1], succ + 1);
powslow[i] = mul(powslow[i - 1], succ);
}
DP[0] = 1;
DP[1] = 1;
for (int i = 2; i <= min(K, len); i++){
DP[i] = pows[i - 1];
}
if (len < K){
return pows[len];
}
for (int i = K; i <= len; i++){
DP[i + 1] = DP[i];
SUB(DP[i + 1], mul(DP[i - K], powslow[K - 1]));
MUL(DP[i + 1], succ);
AD(DP[i + 1], DP[i]);
}
return DP[len + 1];
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int N, K; cin >> N >> K;
vi in(N - K + 1);
for (int i = 0; i < N - K + 1; i++){
cin >> in[i];
}
vector comp;
int cur = -1;
int cnt = 0;
for (int i = 0; i < N - K + 1; i++){
if (cur == in[i]){
++cnt;
}
else{
if (cnt) comp.pb(mp(cur, cnt));
cur = in[i];
cnt = 1;
}
}
comp.pb(mp(cur, cnt));
if (comp.size() == 1){
cout << countseq(comp[0].f, K, N) << endl;
}
else{
int res = 1;
for (int i = 0; i < sz(comp); i++){
int a = comp[i].f;
int len;
if (i == 0){
if (comp[1].f > comp[0].f){
len = comp[0].s - 1;
}
else{
len = comp[0].s + K - 1;
}
}
else if (i == sz(comp) - 1){
if (comp[i - 1].f > comp[i].f){
len = comp[i].s - 1;
}
else{
len = comp[i].s + K - 1;
}
}
else{
if (comp[i - 1].f > comp[i].f){
if (comp[i + 1].f > comp[i].f){
len = max(0, comp[i].s - K - 1);
}
else{
len = comp[i].s - 1;
}
}
else{
if (comp[i + 1].f > comp[i].f){
len = comp[i].s - 1;
}
else{
len = comp[i].s + K - 1;
}
}
}
MUL(res, countseq(a, K, len));
}
cout << res << endl;
}
}