P3131 [USACO16JAN]子共七Subsequences Summing to Sevens
斯德哥尔摩
2018-10-21 20:40:56
[P3131 [USACO16JAN]子共七Subsequences Summing to Sevens](https://www.luogu.org/problemnew/show/P3131)
首先前缀和没的说。
然后有个定理：
设$seven[i]$表示前缀和模$7$的值，若存在$i<=j$且$seven[j]==seven[i]$，则区间$(i,j]$的和为$7$的倍数。
于是我们可以$O(n)$扫出$seven[i]==j,j\in[0,6]$第一次出现的位置$begin[j]$和最后一次出现的位置$end[j]$。
然后答案为$\max\{end[j]-begin[j]+1|j\in[0,6]\}$。
附代码：
```cpp
#include<iostream>
#include<algorithm>
#include<cstdio>
#define MAXN 50010
using namespace std;
int n,ans=0;
int start[7],end[7];
long long sum[MAXN];
inline int read(){
int date=0,w=1;char c=0;
while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}
while(c>='0'&&c<='9'){date=date*10+c-'0';c=getchar();}
return date*w;
}
void work(){
for(int i=0;i<=6;i++)ans=max(ans,end[i]-start[i]);
printf("%d\n",ans);
}
void init(){
n=read();
sum[0]=0;
for(int i=1;i<=n;i++){
int x=read();
sum[i]=sum[i-1]+x;
if(!start[sum[i]%7])start[sum[i]%7]=i;
end[sum[i]%7]=i;
}
}
int main(){
init();
work();
return 0;
}
```