题解 - Vijos

0
Star_Gym LV 3 @ 18 年前

O(n)也要150ms啊...
0
胡晓样 LV 3 @ 18 年前

cutedog,

你难道不能说得明白些???
0
LV 0 @ 18 年前

这个题O(N)的算法就可以了吧.

-1

wagnfzwxl LV 8 @ 8 年前

var
    count:array[0..100000] of longint;
    i,n,k,temp,tot,temp2:longint;
begin
    readln(n,k);    
    fillchar(count,sizeof(count),0);
    temp2:=0;count[0]:=1;
    for i:=1 to n do
        begin
            readln(temp);
            temp2:=(temp2+temp) mod k;
            inc(count[temp2]);
        end;
    tot:=0;
    for i:=0 to k-1 do
        if count[i]<>0 then
                begin
                    inc(tot,(count[i]*(count[i]-1)) shr 1);
                    tot:=tot mod 1234567;
                end;
   **writeln(tot);**
end.

-1

wagnfzwxl LV 8 @ 8 年前

var
    count:array[0..100000] of longint;
    i,n,k,temp,tot,temp2:longint;
begin
    readln(n,k);    
    fillchar(count,sizeof(count),0);
    temp2:=0;count[0]:=1;
    for i:=1 to n do
        begin
            readln(temp);
            temp2:=(temp2+temp) mod k;
            inc(count[temp2]);
        end;
    tot:=0;
    for i:=0 to k-1 do
        if count[i]<>0 then
                begin
                    inc(tot,(count[i]*(count[i]-1)) shr 1);
                    tot:=tot mod 1234567;
                end;
    writeln(tot);
end.

ID: 1090
难度: 5
分类: 其他 | 数学点击显示
标签: (无)
递交数: 3972
已通过: 1264
通过率: 32%
被复制: 20
上传者: matrix67