连续数列和问题
关于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;
}