hunnu11461—數組求和問題（字首和）

題目連結：傳送門

數組求和問題

Time Limit: 1000ms, Special Time Limit:2500ms, Memory Limit:32768KB

Total submit users: 101, Accepted users: 90

Problem 11461 : No special judgement

Problem description

給定一個長度為n的數組，從這個數組裡面随機從前往後取m個數，使得這m個數的和是S，并且這m個數每相鄰的兩個數的下标相差為p。

Input

首先是一個整數t，表示有t組資料，每組資料首先是四個整數，n(1<=n<=100000),m(1<=m<=n),S(0<=S<=10^9), p(1<=p<=100000)意思如題目描述，接下來一行有n個非負數，都小于10^9，表示數組元素的值。

Output

對于每組資料，首先輸出”case #:”,#從一開始，接下來一個數就輸出方案總數。輸出格式詳見樣例。

Sample Input

3 10 2 5 2 1 2 1 3 1 3 2 2 3 2 5 2 10 1 5 5 5 5 5 6 3 10 2 4 2 4 4 4 4

Sample Output

case 1:3 case 2:4 case 3:1

解題思路：這裡如果間隔p隻取1，想必問題變得相當簡單，求字首和rec[n]

再判斷rec[i]-rec[i-n]+data[i-n]是否等于s。現在p取任意數，依舊是求字首和，隻是數之間有個間隔p。

#include <cstdio>  
#include <cstring>  
#include <cmath>  
#include <iostream>  
#include <queue>
#include <set>
#include <string>
#include <stack>
#include <algorithm>
#include <map>
using namespace std;  
typedef __int64  ll;
const int N = 100080;
const int M = 5007;
const int INF = 0x3fffffff;
const int mod = 1e9+7;
const double Pi = acos(-1.0);
const double sm = 1e-9;

ll data[N],rec[N];

int main()
{
	int T,tot = 0;
	scanf("%d",&T);
	while( T-- ){
		int n,m,p;ll s;
		scanf("%d%d%d%d",&n,&m,&s,&p);
		for( int i = 1 ; i <= n ; ++i ){
			scanf("%I64d",&data[i]);
		}
		for( int i = 1 ; i <= p ; ++i ){
			rec[i] = data[i];
		}
		for( int i = 1 ; i+p <= n ; ++i ){
			rec[i+p] = data[i+p]+rec[i];
		}
		int ans = 0;
		for( int i = 1+m*p-p ; i <= n ; ++i ){
			if( (rec[i]-rec[i-(m-1)*p]+data[i-(m-1)*p]) == s ) ++ans;
		}
		printf("case %d:%d\n",++tot,ans);
	}
	return 0;
}