问题 G: JS Window
时间限制: 2 Sec 内存限制: 512 MB
题目描述
JSZKC has an array A of N integers. More over, he has a Window of length M which means the Window can contain M continuous integers in the array.
At the begging, the Window is at the position 1 which means the Window contains the integers from position 1 to position M. Each time the Window move right by one until it reach the end. So after one move, the window contains position 2 to position M+1.
At each place, we can multiply all the integers in the window. Please calculate the product mod P at each position. As the output maybe very large, you should output the sum of these product.
For example, if the array is”2 3 7 11 13” with m=3 and P=5. So the product at position 1 is 2, at position 2 is 1 and at position 3 is 1. 2+1+1=4. So you should output 4.
At the begging, the Window is at the position 1 which means the Window contains the integers from position 1 to position M. Each time the Window move right by one until it reach the end. So after one move, the window contains position 2 to position M+1.
At each place, we can multiply all the integers in the window. Please calculate the product mod P at each position. As the output maybe very large, you should output the sum of these product.
For example, if the array is”2 3 7 11 13” with m=3 and P=5. So the product at position 1 is 2, at position 2 is 1 and at position 3 is 1. 2+1+1=4. So you should output 4.
输入
The input file contains several test cases, each of them as described below.
- The first line of the input contains three integers N,M,P (1 ≤ M≤ N≤ 1000000, 1 ≤ P≤ 1000000000), giving the length of the array, the length of the window and the number which we mod.
- The second line of the input contains four integers A[1],X,Y,Z(1 ≤ A[1],X,Y,Z≤ 1000000000). For i>1, A[i]=X*A[i-1]^2+Y* A[i-1]+Z
There are no more than 10 test cases. And the sum of N is no more than 10000000.
输出
One line per case, an integer indicates the answer
样例输入
5 1 130495969
3 3 0 2
样例输出
84928588
meaning
n个数，每次取m个连续的数，求积模p再求和。
solution
想到了就很水的题
分块，每块长度为m，每块计算前缀积和后缀积
没有恰好落在块上的区间，可以看作前一块的后缀积×后一块的前缀积。
tips
和不要模p。
a[1]要模p。
code
#define IN_LB() freopen("C:\\Users\\acm2018\\Desktop\\in.txt","r",stdin)
#define OUT_LB() freopen("C:\\Users\\acm2018\\Desktop\\out.txt","w",stdout)
#define IN_PC() freopen("C:\\Users\\hz\\Desktop\\in.txt","r",stdin)
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1000005;
typedef long long ll;
ll n,m,p,x,y,z;
ll a[maxn];
ll ex[maxn],su[maxn];
int main() {
// IN_LB();
while(scanf("%lld%lld%lld",&n,&m,&p)!=EOF) {
scanf("%lld%lld%lld%lld",&a[0],&x,&y,&z);
a[0]%=p;
for(int i=1; i<n; i++) {
a[i] = (a[i-1]*a[i-1]%p*x%p+y*a[i-1]%p+z)%p;
}
for(int i=0; i<n; i++) {
if(i%m==0) {
ex[i] = a[i];
} else
ex[i] = a[i]*ex[i-1]%p;
}
for(int i=n-1; i>=0; i--) {
if((i+1)%m==0||i==n-1) {
su[i] = a[i];
} else
su[i] = a[i]*su[i+1]%p;
}
ll ans = 0;
for(int i=m-1; i<n; i++) {
if((i+1)%m==0) {
ans+=ex[i];
} else
ans+=(ex[i]*su[i-m+1])%p;
}
printf("%lld\n",ans);
}
return 0;
}