连续数列和问题

关于7的迷题
Description

给你n个数，分别是a[1],a[2],...,a[n]。

求一个最长的区间[x,y]， 使得区间中的数(a[x],a[x+1],a[x+2],...,a[y-1],a[y])的和能被7整除。

输出区间长度。若没有符合要求的区间，输出0。

Format
Input
第一行给出数字N，1≤N≤50,000

接下来N个数字，值在[0…1,000,000]

Output
如题

Samples
输入数据 1
7
3
5
1
6
2
14
10
输出数据 1
5
Hint

选取区间

[5,1,6,2,14]

其总和为7的倍数

#include<bits/stdc++.h>
using namespace std;
int n,a,s,l[7],r[7],ans; 
int main()
{
	scanf("%d",&n);
	memset(l,-1,sizeof(l));
	l[0]=0;
	for(int i=1;i<=n;++i)
	{
		scanf("%d",&a);
		s=(s+a)%7;
		if(l[s]==-1)
		    l[s]=i;
		r[s]=i;
	}
	for(int i=0;i<=6;++i)
	    if(l[i]!=-1)
		   ans=max(ans,r[i]-l[i]);
	printf("%d",ans);
}

给你N个数字，每个数字不是1就是-1 问多少个连续的数列和为0
# Format
## Input
第一行为N， ,N小于等于1e6
第二行为N个用空格隔开的1和-1序列。
## Output
总方案数MOD 999999的值
# Samples
```input1
9
-1 1 -1 -1 -1 1 1 -1 -1
``` ```
output1
8 ```
Hint

例如第1个数字到第2个数字 第2个到第7个数字 第6个到第9个数字 它们的和均为0 一共有8种情况 此题需要用到数组来保存来数字

#include<bits/stdc++.h>
using namespace std;
#define int long long
long long n,m,ans;
int  v[2200000]; 
int a[1002001],sum[1002001];
main()
{
	cin>>n;
	
	int temp=1000000;
	v[0+temp]=1;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		sum[i]=sum[i-1]+a[i];
		ans=(ans+v[sum[i]+temp])%999999;
		v[sum[i]+temp]++;
	}
	cout<<ans;
	return 0;
}

求方案

Description
有 n 个正整数排成一行。你的目的是要从中取出一个或连续的若干个数，使它们的和能够被 k 整除。

例如，有 6 个正整数，它们依次为 1; 2; 6; 3; 7; 4。

若 k = 3，则你可以取出 1; 2; 6，或者 2; 6; 3; 7，也可以仅仅取出一个 6 或者 3 使你所取的数之和能被 3 整除。

当然，满足要求的取法不止以上这 4 种。事实上，一共有 7 种取法满足要求。

给定 n 和 k，以及这 n 个数。

你的任务就是确定从这 n 个数中取出其中一个数或者若干连续的数，使它们的和能被 k 整除有多少方法。

记 Ha = 1234567，由于取法可能很多，

因此你只需要输出它 mod Ha 的值即可

Format
Input
第一行为两个整数 n; k。

以下 n 行每行一个正整数，描述这个序列。

1 <= n <= 500000; 1 <= k <= 100000

Output
输出一个整数，为答案 mod Ha 的结果。

Samples
输入数据 1
6 3
1
2
6
3
7
4
输出数据 1
7

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 110;
int n, k, ans;
int b[N];

int main ()
{
	
	
	scanf ("%d %d", &n, &k);
	b[0] = 1;
	for (int i = 1, x, sum = 0; i <= n; i ++) 
	{
		scanf ("%d", &x);
	    sum = (sum + x) % k;
	    ans += b[sum];
	    b[sum] ++;
	}
	printf ("%d\n", ans);
	
}
/*
*/

P01236. Divisible Subsequence

Description
给出一个数列，希望你从中找出一些连续的子数列,要求子序列的元素之和能被N整除

Format
Input
第一行给出数字D，N。 D代表数列一共有多少个元素，N代表被整除的数 下面一行给出D个数字， 每个数字范围在[1, 1000000000]

1 <= d < = 1000000

1<= N <=50000.

Output
一共有多少个子序列满足条件

Samples
输入数据 1
3 3
1 2 3
输出数据 1
3
【样例解释】

你可以取[1,2],[1,2,3],[3]这三个子数列

#include<cstdio>
using namespace std;
long long n,k,sum[1000005];
long long ans,qwq;
int main(){sum[0]=1;
scanf("%d%d",&n,&k);
for(int i=1,x;i<=n;i++){
scanf("%d",&x);
qwq=(qwq+x)%k;
sum[qwq]+=1;
}
for(int i=0;i<k;i++)
if(sum[i]>=1)
ans+=(sum[i]*(sum[i]-1))/2;
printf("%lld",ans);
return 0;
}

#include <bits/stdc++.h>
 
using namespace std;
 
const int N = 1e5 + 110;
int n, k;
int b[N];
long long ans;
 
int main ()
{
     
     
    scanf ("%d %d", &n, &k);
    b[0] = 1;
    for (int i = 1, x, sum = 0; i <= n; i ++)
    {
        scanf ("%d", &x);
        sum = (sum + x) % k;
        ans += b[sum];
        b[sum] ++;
    }
    cout<<ans<<endl;
     
}

P05537. 连续子序列之和

Description
给你一个N，再给出这个数字 问有多少连续子序列之和等于 K

Format
Input
第一行给出N，K 接下来给出N个数字

1≤N≤2×10^5

∣Ai∣≤10^9

∣K∣≤10^15

Output
如题目

Samples
输入数据 1
6 5
8 -3 5 7 0 -4

输出数据 1
3
输入数据 2
4 3
3 3 3 3
输出数据 2
4

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m,ans;
map<int,int> v; 
int a[202001],sum[202001];
main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		sum[i]=sum[i-1]+a[i];
		ans+=v[sum[i]-m];
		v[sum[i]]++;
	}
	cout<<ans;
	return 0;
}