NC24215. [USACO 2019 Jan P]Train Tracking 2
描述
平时，Bessie会观察驶过的列车，记录车厢的编号。但是今天雾实在太浓了，Bessie一个编号也看不见！幸运的是，她从城市里某个可靠的信息源获知了列车编号序列的所有滑动窗口中的最小值。具体地说，她得到了一个正整数K，以及N−K+1个正整数c1,…,cN+1−K，其中ci是车厢i,i+1,…,i+K−1之中编号的最小值。
帮助Bessie求出满足所有滑动窗口最小值的对每节车厢进行编号的方法数量。由于这个数字可能非常大，只要你求出这个数字对10^9+7取余的结果Bessie就满意了。
Bessie的消息是完全可靠的；也就是说，保证存在至少一种符合要求的编号方式。
输入描述
输入的第一行包含两个空格分隔的整数N和K。余下的行包含所有的滑动窗口最小值c1,…,cN+1−K，每行一个数。
输出描述
输出一个整数：对每节车厢给予一个不超过10^9的正整数编号的方法数量对10^9+7取余的结果，满足车厢i,i+1,…,i+K−1之中编号的最小值等于ci，对于1≤i≤N−K+1均成立。
示例1
输入:
4 2 999999998 999999999 999999998
输出:
3
C++11(clang++ 3.9) 解法, 执行用时: 13ms, 内存消耗: 1784K, 提交时间: 2020-08-29 10:47:33
#include <cstdio>
const int mod = 1e9 + 7;
const int p = 1e9;
#define MAXN 100005
#define LL long long
int n, k;
LL c[MAXN];
LL result = 1;
LL dp[MAXN];
LL qkpow ( LL x, LL y ) {
LL res = 1;
while ( y ) {
if ( y % 2 ) res = ( res * x ) % mod;
x = ( x * x ) % mod;
y >>= 1;
}
return res % mod;
}
LL window ( LL val, LL len ) {
LL tmp = p - val;
LL tp = qkpow ( tmp, k );
dp[0] = dp[1] = 1;
for ( int i = 2;i <= len + 1;i ++ ) {
dp[i] = ( ( tmp + 1 ) * dp[i - 1] ) % mod;
if ( i - k - 1 >= 0 )
dp[i] = ( ( dp[i] - ( ( tp * dp[i - k - 1] ) % mod ) + mod ) % mod ) % mod;
}
return dp[len + 1] % mod;
}
int main() {
scanf ( "%d %d", &n, &k );
for ( int i = 1;i <= n - k + 1;i ++ )
scanf ( "%lld", &c[i] );
for ( int i = 1, j;i <= n - k + 1;i = j + 1 ) {
LL len;
j = i;
while ( c[i] == c[j + 1] )
j ++;
len = j - i + k;
if ( i != 1 && c[i - 1] > c[i] )
len -= k;
if ( j != n - k + 1 && c[j + 1] > c[i] )
len -= k;
if ( len > 0 )
result = ( result * window ( c[i], len ) ) % mod;
}
printf ( "%lld", result % mod );
return 0;
}
C++14(g++5.4) 解法, 执行用时: 13ms, 内存消耗: 1144K, 提交时间: 2020-08-29 22:27:04
#include <bits/stdc++.h>
using namespace std;
#define MAXN 100000
#define MOD 1000000007
int n, k, c[MAXN + 5], f[MAXN + 5];
int fpow(int x, int p) {
int ret = 1;
while (p) {
if (p & 1) ret = 1LL * ret * x % MOD;
x = 1LL * x * x % MOD;
p >>= 1;
}
return ret;
}
int solve(int v, int l) {
int p = 1000000000 - v, pk = fpow(p, k);
f[0] = f[1] = 1;
for (int i = 2; i <= l + 1; ++i) {
f[i] = 1LL * (p + 1) * f[i - 1] % MOD;
if(i - k - 1 >= 0) f[i] = (f[i] - 1LL * pk * f[i - k - 1] % MOD + MOD) % MOD;
}
return f[l + 1]; // 注意这里返回l+1而不是l，否则就会钦定a[l]为v了
}
int main() {
scanf("%d%d", &n, &k);
for (int i = 1; i <= n - k + 1; ++i) scanf("%d", &c[i]);
int ans = 1;
for (int i = 1, j, len; i <= n - k + 1; i = j + 1) {
j = i;
while (c[j+1] == c[i]) j++;
len = j - i + k;
if (i != 1 && c[i - 1] > c[i]) len -= k;
if (j != n - k + 1 && c[j + 1] > c[i]) len -= k;
if (len > 0) ans = 1LL * ans * solve(c[i], len) % MOD;
}
printf("%d\n", ans);
return 0;
}