描述
题解
这个题真的很让人出乎意料……没成想,1e7
的数据酱紫搞竟然能在 0.7s
内搞定。
首先,我们暴力获得数组 a[] ,然后使用尺取法,先获取一个满足题意的 l = 1, r = ?, cnt = k 的区间,接着呢,很明显只要右区间大于 r 都是好区间,然后尺取法往后继续查找刚好满足
代码不难,但是一开始很难相信这是可行的。事后想想也是,像这种海量数据的情况,时间消耗很大一部分在 I/O 阶段,而题目中也刚好提到,为了避免这个阶段的影响,而想到了这个绝妙的方法……咳咳,这个题就先酱紫吧。
代码
#include <cstdio>
using namespace std;
typedef long long ll;
const int MAXN = 1e7 + 10;
ll n, k, T, b, c, p;
ll res = 0;
ll a[MAXN];
void solve()
{
for (int i = 1; i <= n; i++)
{
a[i] = (a[i - 1] * b + c);
if (a[i] >= p)
{
a[i] %= p;
}
}
int l = 1, r = 1, cnt = 0;;
while (r <= n)
{
if (a[r] >= T)
{
cnt++;
}
if (cnt == k)
{
break;
}
r++;
}
while (r <= n && r - l + 1 >= k)
{
res += (n - r + 1);
if (a[l] >= T)
{
while (r <= n)
{
r++;
if (a[r] >= T)
{
break;
}
}
}
l++;
}
}
int main()
{
scanf("%lld%lld%lld%lld%lld%lld%lld",
&n, &k, &T, a, &b, &c, &p);
solve();
printf("%lld\n", res);
return 0;
}