#include

#include

#define N 500000

int s[N+10];

int count[100010];

int main()

{

int n,k;

scanf("%d%d",&n,&k);

int i,a;

s[0]=0;

for(i=1;i

Program p1090;

var n,k,min,max:qword;

i,j,f:longint;

a:array[0..500000]of longint;

b:array[0..99999]of longint;

Begin

read(n);

readln(k);

for i:=1 to n do

begin

readln(f);

a[i]:=(a+f mod k)mod k;

inc(b[a[i]]);

end;

for i:=0 to k-1 do

begin

min:=b[i]-1;

min:=min*b[i]div 2;

inc(max,min);

end;

for i:=1 to n do

if (a[i]=0)

then inc(max);

writeln(max mod 1234567);

End.

这道关于连续段。。。对付连续段的利器就是——求和！

设Sum[i]=1..i的合

Sum(i..j):=Sum[j]-Sum;

那么Sum(i..j) mod k =0 意味着。。Sum[j]与Sum关于k同余

同样。。对于任何两个i,j(ij)。只要Sum[i]=Sum[j]都有一个连续段mod k 为0

于是思路就出来了。。对每个属于0..k-1的数i记录有多少个Sum[n] mod k=i。记为Num[i]

问题就转化成了找出对于每一个i的一个2排列。。自然是Num[i]*(Num[i]-1);

同时单个也算。。再加上Num[0]就OK了

Program p;

const

maxn = 500000;

maxk = 100000;

Var

Nums:array[0..maxk]of Longint;

Num,X,i,N,Sum,level,k:Longint;

Begin

Readln(N,k);Sum:=0;fillchar(Nums,sizeof(Nums),0);

For i := 1 to N do Begin

Readln(X);

Inc(Sum,X);Sum := Sum mod k;

Inc(Nums[Sum]);if Sum>level then level:=Sum; End;

For i:=level downto 0 do Begin

if Nums[i]=0 then continue;

Inc(Num,Nums[i]*(Nums[i]-1) div 2 );

Num := Num mod 1234567; End;

Writeln(Num+Nums[0]);

End.

var a,i,j,n,k:longint;

max,min:int64;

b:array[0..99999] of longint;

f:array[0..500000] of longint;

begin

readln(n,k);

fillchar(b,sizeof(b),0);

b[0]:=1;

f[0]:=0;

for i:=1 to n do begin

readln(a);

f[i]:=(f+a) mod k;

inc(b[f[i]]);

end;

max:=0;

for i:=0 to k-1 do begin

min:=b[i]-1;

min:=min*b[i] div 2;

inc(max,min);

end;

write(max mod 1234567);

end.

巨汗

参考的792123646牛的程序

自己没有任何思路

其实

本题只需记录到达相应位置时的余数

那么此数到达前面相应余数的片段肯定符合条件！

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

不错，不错。

不用没次都mod 1234567,其实int64就足够大了，最后一个mod 1234567就行了。

var a,i,j,n,k:longint;

max,min:int64;

b:array[0..99999] of longint;

f:array[0..500000] of longint;

begin

readln(n,k);

fillchar(b,sizeof(b),0);

b[0]:=1;

f[0]:=0;

for i:=1 to n do begin

readln(a);

f[i]:=(f+a) mod k;

inc(b[f[i]]);

end;

max:=0;

for i:=0 to k-1 do begin

min:=b[i]-1;

min:=min*b[i] div 2;

inc(max,min);

end;

write(max mod 1234567);

end.

var

i,j,n,k,ss,f,tot:longint;a:qword;

s:array[0..100000]of longint;

b:array[0..100000]of longint;

begin

readln(n,k);fillchar(s,sizeof(s),0);

for i:=1 to n do

begin

readln(a);

f:=a mod k;

s[i]:=(s+f)mod k;

inc(b[s[i]]);

end;

for i:=0 to k-1 do

begin

//if s[i]-s=0 then inc(tot);

{for j:=i to n do

begin

ss:=s[j]-s;

if ss=0 then inc(tot);

end;}

tot:=(tot+b[i]*(b[i]-1)div 2) mod 1234567;

end;

tot:=(tot+b[0])mod 1234567;

writeln(tot);

end.

为什么最后两个点过不了？

什么数据啊？晕……

这题的样例结果应该是11

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 9ms

├ 测试数据 10：答案正确... 88ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：97ms

#include "stdio.h"

int main()

{

int s[500010]={0},n,k,i,x,y,z;

scanf("%d %d\n",&n,&k);

y=0;

z=0;

for(i=1;i

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 25ms

├ 测试数据 10：答案正确... 87ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：112ms

为什么楼下的会对呢？

能否解释一下下？

var

a:array[0..500000]of longint;

n,k,i,x,ys,an:longint;

begin

fillchar(a,sizeof(a),0);

readln(n,k);

for i:=1to n do

begin

readln(x);

ys:=(ys+x)mod k;

an:=an+a[ys];

if ys=0

then inc(an);

an:=an mod 1234567;

inc(a[ys]);

end;

writeln(an);

end.

1001夜的故事

1001夜的故事

1001夜的故事

1001夜的故事

1001夜的故事

1001夜的故事

1001夜的故事

1001夜的故事

1001夜的故事

1001夜的故事

1001夜的故事

1001夜的故事

1001夜的故事

1001夜的故事

1001夜的故事

1001夜的故事

1001夜的故事

1001夜的故事

1001夜的故事

1001夜的故事

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 72ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：72ms

哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈

我是第1000个AC

我是第1000个AC

我是第1000个AC

我是第1000个AC

我是第1000个AC

我是第1000个AC

我是第1000个AC

我是第1000个AC

我是第1000个AC

我是第1000个AC

我是第1000个AC

我是第1000个AC

我是第1000个AC

我是第1000个AC

！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！

很简单的！！

Flag 　　Accepted

题号 　　P1090

类型(?) 　　数论 / 数值

通过 　　999人

提交 　　2851次

通过率 　　35%

难度 　　2

提交 讨论 题解 状态

我是第999个AC的！！！！

我都无奈了我就

我就无奈了我都

我就无都了我奈

靠~~~~~~~~~~没用INT64过不了~~~~~~

很水的题花了我半个小时~~~~~~~

var a:array[0..500000] of int64;

b:array[0..100000] of int64;

i,j,n,tot,k:longint;

begin

readln(n,k);

a[0]:=0;

fillchar(b,sizeof(b),0);

for i:=1 to n do begin readln(a[i]); a[i]:=a[i]+a; inc(b[a[i] mod k]) end;

for i:=0 to k do

begin

if b[i]*b[i]-1>=0 then

inc(tot,(b[i]*(b[i]-1)) shr 1);

if tot>=1234567 then tot:=tot mod 1234567;

end;

writeln(tot+b[0] mod 1234567);

end.

千万要注意最后mod 1234567！我就是忘了，结果wa了一半。。。。

怎么想到的 这种方法？？？