125 条题解
-
0
guoqianli LV 8 @ 2015-10-06 16:32:08
pOrz 340508965
转一下
var
a,i,k,n:longint;
sum:int64;
b:array[0..100000] of longint; //表示余数为j时sum的总个数
begin
readln(n,k);
sum:=0;
for i:=1 to n do
begin
readln(a);
inc(sum,a);
inc(b[sum mod k]); //更新相应的b[]
end;
sum:=b[0]; //刚才说的注意的地方
for i:=0 to k-1 do
sum:=(sum+(b[i]*(b[i]-1))shr 1) mod 1234567;
writeln(sum);
end.编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms├ 测试数据 10：答案正确... 0ms
Accepted 有效得分：100 有效耗时：0ms
噢耶 (^o^)/ 秒杀 呵呵很难得啊
先说说怎么做吧
SUM[i]是代表前i个数的和
当(SUM[i]-SUM[j]) MOD k=0 这时[j+1,i]就是满足的一个区间 一个方案了
而我们求的是(SUM[i]-SUM[j]) MOD k=0 这样的方案总个数
我们又可以推出 上式等价于SUM[i] MOD k=SUM[j] MOD k
所以我们就是求SUM[i] MOD k=SUM[j] MOD k 的方案个数了假设 sum[i],sum[j],..sum[k]（共bn个） 都是 MOD k 余数为k-1的sum
那么从上面bn个sum中任意选取两个就能得出(SUM[i]-SUM[j]) MOD k=0
那么在bn个sum中怎么配对呢（下面的sum[bn]表示上述bn个sum中的第n个sum）
很简单 先是sum[b1]与sum[b2] sum[b3] ...sumbn
然后sum[b2]与sum[b3] sum[b4] ...sumbn
然后sum[b3]与sum[b4] sum[b5] ...sumbn
............
最后sum[bn-1]与sum[bn] ( 1 个)方案总数=n-1+n-2+n-3+...+1=bn*(bn-1) div 2
（好像这是初中的知识吧？ 可是当时我看楼下的楼下的楼下....的题解 我一时竟然还不明白为什么）所以 当sum mod k的余数为k-1时有bn*(bn-1) div 2个方案总数了
就这样依次得出余数为k-1 k-2 k-3 ...0的时候方案总数 再相加一下得出答案所以在读入一个数的时候就计算sum然后计算sum mod k 的余数
而b[j]表示余数为j的sum个数 此时根据上面新得出的更新相应的b[j]这样在读入完毕之后就可以根据b[j]直接计算总方案数了
特别值得注意的是！！！！
计算余数为0的方案总数时候还要加上b[0] 也就是b[0]*(b[0]-1) div 2+b[0]
为什么？？ 因为余数为0的时候单独一个sum[i]就能成为一个方案了还有比如div 2可以用shr 1 这样可以加快速度
呼呼(～ o ～)~zZ 说得好累啊
我自己都快被讲糊涂了 呵呵
希望有不懂这道题目的人能看懂....
这样就不算白忙了 -
0
Orz 340508965
转一下
var
a,i,k,n:longint;
sum:int64;
b:array[0..100000] of longint; //表示余数为j时sum的总个数
begin
readln(n,k);
sum:=0;
for i:=1 to n do
begin
readln(a);
inc(sum,a);
inc(b[sum mod k]); //更新相应的b[]
end;
sum:=b[0]; //刚才说的注意的地方
for i:=0 to k-1 do
sum:=(sum+(b[i]*(b[i]-1))shr 1) mod 1234567;
writeln(sum);
end.编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms├ 测试数据 10：答案正确... 0ms
Accepted 有效得分：100 有效耗时：0ms
噢耶 (^o^)/ 秒杀 呵呵很难得啊
先说说怎么做吧
SUM[i]是代表前i个数的和
当(SUM[i]-SUM[j]) MOD k=0 这时[j+1,i]就是满足的一个区间 一个方案了
而我们求的是(SUM[i]-SUM[j]) MOD k=0 这样的方案总个数
我们又可以推出 上式等价于SUM[i] MOD k=SUM[j] MOD k
所以我们就是求SUM[i] MOD k=SUM[j] MOD k 的方案个数了假设 sum[i],sum[j],..sum[k]（共bn个） 都是 MOD k 余数为k-1的sum
那么从上面bn个sum中任意选取两个就能得出(SUM[i]-SUM[j]) MOD k=0
那么在bn个sum中怎么配对呢（下面的sum[bn]表示上述bn个sum中的第n个sum）
很简单 先是sum[b1]与sum[b2] sum[b3] ...sumbn
然后sum[b2]与sum[b3] sum[b4] ...sumbn
然后sum[b3]与sum[b4] sum[b5] ...sumbn
............
最后sum[bn-1]与sum[bn] ( 1 个)方案总数=n-1+n-2+n-3+...+1=bn*(bn-1) div 2
（好像这是初中的知识吧？ 可是当时我看楼下的楼下的楼下....的题解 我一时竟然还不明白为什么）所以 当sum mod k的余数为k-1时有bn*(bn-1) div 2个方案总数了
就这样依次得出余数为k-1 k-2 k-3 ...0的时候方案总数 再相加一下得出答案所以在读入一个数的时候就计算sum然后计算sum mod k 的余数
而b[j]表示余数为j的sum个数 此时根据上面新得出的更新相应的b[j]这样在读入完毕之后就可以根据b[j]直接计算总方案数了
特别值得注意的是！！！！
计算余数为0的方案总数时候还要加上b[0] 也就是b[0]*(b[0]-1) div 2+b[0]
为什么？？ 因为余数为0的时候单独一个sum[i]就能成为一个方案了还有比如div 2可以用shr 1 这样可以加快速度
呼呼(～ o ～)~zZ 说得好累啊
我自己都快被讲糊涂了 呵呵
希望有不懂这道题目的人能看懂....
这样就不算白忙了 -
0
Orz 340508965
转一下
var
a,i,k,n:longint;
sum:int64;
b:array[0..100000] of longint; //表示余数为j时sum的总个数
begin
readln(n,k);
sum:=0;
for i:=1 to n do
begin
readln(a);
inc(sum,a);
inc(b[sum mod k]); //更新相应的b[]
end;
sum:=b[0]; //刚才说的注意的地方
for i:=0 to k-1 do
sum:=(sum+(b[i]*(b[i]-1))shr 1) mod 1234567;
writeln(sum);
end.编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms├ 测试数据 10：答案正确... 0ms
Accepted 有效得分：100 有效耗时：0ms
噢耶 (^o^)/ 秒杀 呵呵很难得啊
先说说怎么做吧
SUM[i]是代表前i个数的和
当(SUM[i]-SUM[j]) MOD k=0 这时[j+1,i]就是满足的一个区间 一个方案了
而我们求的是(SUM[i]-SUM[j]) MOD k=0 这样的方案总个数
我们又可以推出 上式等价于SUM[i] MOD k=SUM[j] MOD k
所以我们就是求SUM[i] MOD k=SUM[j] MOD k 的方案个数了假设 sum[i],sum[j],..sum[k]（共bn个） 都是 MOD k 余数为k-1的sum
那么从上面bn个sum中任意选取两个就能得出(SUM[i]-SUM[j]) MOD k=0
那么在bn个sum中怎么配对呢（下面的sum[bn]表示上述bn个sum中的第n个sum）
很简单 先是sum[b1]与sum[b2] sum[b3] ...sumbn
然后sum[b2]与sum[b3] sum[b4] ...sumbn
然后sum[b3]与sum[b4] sum[b5] ...sumbn
............
最后sum[bn-1]与sum[bn] ( 1 个)方案总数=n-1+n-2+n-3+...+1=bn*(bn-1) div 2
（好像这是初中的知识吧？ 可是当时我看楼下的楼下的楼下....的题解 我一时竟然还不明白为什么）所以 当sum mod k的余数为k-1时有bn*(bn-1) div 2个方案总数了
就这样依次得出余数为k-1 k-2 k-3 ...0的时候方案总数 再相加一下得出答案所以在读入一个数的时候就计算sum然后计算sum mod k 的余数
而b[j]表示余数为j的sum个数 此时根据上面新得出的更新相应的b[j]这样在读入完毕之后就可以根据b[j]直接计算总方案数了
特别值得注意的是！！！！
计算余数为0的方案总数时候还要加上b[0] 也就是b[0]*(b[0]-1) div 2+b[0]
为什么？？ 因为余数为0的时候单独一个sum[i]就能成为一个方案了还有比如div 2可以用shr 1 这样可以加快速度
呼呼(～ o ～)~zZ 说得好累啊
我自己都快被讲糊涂了 呵呵
希望有不懂这道题目的人能看懂....
这样就不算白忙了 -
0
Orz 340508965
转一下
var
a,i,k,n:longint;
sum:int64;
b:array[0..100000] of longint; //表示余数为j时sum的总个数
begin
readln(n,k);
sum:=0;
for i:=1 to n do
begin
readln(a);
inc(sum,a);
inc(b[sum mod k]); //更新相应的b[]
end;
sum:=b[0]; //刚才说的注意的地方
for i:=0 to k-1 do
sum:=(sum+(b[i]*(b[i]-1))shr 1) mod 1234567;
writeln(sum);
end.编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms├ 测试数据 10：答案正确... 0ms
Accepted 有效得分：100 有效耗时：0ms
噢耶 (^o^)/ 秒杀 呵呵很难得啊
先说说怎么做吧
SUM[i]是代表前i个数的和
当(SUM[i]-SUM[j]) MOD k=0 这时[j+1,i]就是满足的一个区间 一个方案了
而我们求的是(SUM[i]-SUM[j]) MOD k=0 这样的方案总个数
我们又可以推出 上式等价于SUM[i] MOD k=SUM[j] MOD k
所以我们就是求SUM[i] MOD k=SUM[j] MOD k 的方案个数了假设 sum[i],sum[j],..sum[k]（共bn个） 都是 MOD k 余数为k-1的sum
那么从上面bn个sum中任意选取两个就能得出(SUM[i]-SUM[j]) MOD k=0
那么在bn个sum中怎么配对呢（下面的sum[bn]表示上述bn个sum中的第n个sum）
很简单 先是sum[b1]与sum[b2] sum[b3] ...sumbn
然后sum[b2]与sum[b3] sum[b4] ...sumbn
然后sum[b3]与sum[b4] sum[b5] ...sumbn
............
最后sum[bn-1]与sum[bn] ( 1 个)方案总数=n-1+n-2+n-3+...+1=bn*(bn-1) div 2
（好像这是初中的知识吧？ 可是当时我看楼下的楼下的楼下....的题解 我一时竟然还不明白为什么）所以 当sum mod k的余数为k-1时有bn*(bn-1) div 2个方案总数了
就这样依次得出余数为k-1 k-2 k-3 ...0的时候方案总数 再相加一下得出答案所以在读入一个数的时候就计算sum然后计算sum mod k 的余数
而b[j]表示余数为j的sum个数 此时根据上面新得出的更新相应的b[j]这样在读入完毕之后就可以根据b[j]直接计算总方案数了
特别值得注意的是！！！！
计算余数为0的方案总数时候还要加上b[0] 也就是b[0]*(b[0]-1) div 2+b[0]
为什么？？ 因为余数为0的时候单独一个sum[i]就能成为一个方案了还有比如div 2可以用shr 1 这样可以加快速度
呼呼(～ o ～)~zZ 说得好累啊
我自己都快被讲糊涂了 呵呵
希望有不懂这道题目的人能看懂....
这样就不算白忙了 -
0
Orz 340508965
转一下
var
a,i,k,n:longint;
sum:int64;
b:array[0..100000] of longint; //表示余数为j时sum的总个数
begin
readln(n,k);
sum:=0;
for i:=1 to n do
begin
readln(a);
inc(sum,a);
inc(b[sum mod k]); //更新相应的b[]
end;
sum:=b[0]; //刚才说的注意的地方
for i:=0 to k-1 do
sum:=(sum+(b[i]*(b[i]-1))shr 1) mod 1234567;
writeln(sum);
end.编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms├ 测试数据 10：答案正确... 0ms
Accepted 有效得分：100 有效耗时：0ms
噢耶 (^o^)/ 秒杀 呵呵很难得啊
先说说怎么做吧
SUM[i]是代表前i个数的和
当(SUM[i]-SUM[j]) MOD k=0 这时[j+1,i]就是满足的一个区间 一个方案了
而我们求的是(SUM[i]-SUM[j]) MOD k=0 这样的方案总个数
我们又可以推出 上式等价于SUM[i] MOD k=SUM[j] MOD k
所以我们就是求SUM[i] MOD k=SUM[j] MOD k 的方案个数了假设 sum[i],sum[j],..sum[k]（共bn个） 都是 MOD k 余数为k-1的sum
那么从上面bn个sum中任意选取两个就能得出(SUM[i]-SUM[j]) MOD k=0
那么在bn个sum中怎么配对呢（下面的sum[bn]表示上述bn个sum中的第n个sum）
很简单 先是sum[b1]与sum[b2] sum[b3] ...sumbn
然后sum[b2]与sum[b3] sum[b4] ...sumbn
然后sum[b3]与sum[b4] sum[b5] ...sumbn
............
最后sum[bn-1]与sum[bn] ( 1 个)方案总数=n-1+n-2+n-3+...+1=bn*(bn-1) div 2
（好像这是初中的知识吧？ 可是当时我看楼下的楼下的楼下....的题解 我一时竟然还不明白为什么）所以 当sum mod k的余数为k-1时有bn*(bn-1) div 2个方案总数了
就这样依次得出余数为k-1 k-2 k-3 ...0的时候方案总数 再相加一下得出答案所以在读入一个数的时候就计算sum然后计算sum mod k 的余数
而b[j]表示余数为j的sum个数 此时根据上面新得出的更新相应的b[j]这样在读入完毕之后就可以根据b[j]直接计算总方案数了
特别值得注意的是！！！！
计算余数为0的方案总数时候还要加上b[0] 也就是b[0]*(b[0]-1) div 2+b[0]
为什么？？ 因为余数为0的时候单独一个sum[i]就能成为一个方案了还有比如div 2可以用shr 1 这样可以加快速度
呼呼(～ o ～)~zZ 说得好累啊
我自己都快被讲糊涂了 呵呵
希望有不懂这道题目的人能看懂....
这样就不算白忙了 -
0
Orz 340508965
转一下
var
a,i,k,n:longint;
sum:int64;
b:array[0..100000] of longint; //表示余数为j时sum的总个数
begin
readln(n,k);
sum:=0;
for i:=1 to n do
begin
readln(a);
inc(sum,a);
inc(b[sum mod k]); //更新相应的b[]
end;
sum:=b[0]; //刚才说的注意的地方
for i:=0 to k-1 do
sum:=(sum+(b[i]*(b[i]-1))shr 1) mod 1234567;
writeln(sum);
end.编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms├ 测试数据 10：答案正确... 0ms
Accepted 有效得分：100 有效耗时：0ms
噢耶 (^o^)/ 秒杀 呵呵很难得啊
先说说怎么做吧
SUM[i]是代表前i个数的和
当(SUM[i]-SUM[j]) MOD k=0 这时[j+1,i]就是满足的一个区间 一个方案了
而我们求的是(SUM[i]-SUM[j]) MOD k=0 这样的方案总个数
我们又可以推出 上式等价于SUM[i] MOD k=SUM[j] MOD k
所以我们就是求SUM[i] MOD k=SUM[j] MOD k 的方案个数了假设 sum[i],sum[j],..sum[k]（共bn个） 都是 MOD k 余数为k-1的sum
那么从上面bn个sum中任意选取两个就能得出(SUM[i]-SUM[j]) MOD k=0
那么在bn个sum中怎么配对呢（下面的sum[bn]表示上述bn个sum中的第n个sum）
很简单 先是sum[b1]与sum[b2] sum[b3] ...sumbn
然后sum[b2]与sum[b3] sum[b4] ...sumbn
然后sum[b3]与sum[b4] sum[b5] ...sumbn
............
最后sum[bn-1]与sum[bn] ( 1 个)方案总数=n-1+n-2+n-3+...+1=bn*(bn-1) div 2
（好像这是初中的知识吧？ 可是当时我看楼下的楼下的楼下....的题解 我一时竟然还不明白为什么）所以 当sum mod k的余数为k-1时有bn*(bn-1) div 2个方案总数了
就这样依次得出余数为k-1 k-2 k-3 ...0的时候方案总数 再相加一下得出答案所以在读入一个数的时候就计算sum然后计算sum mod k 的余数
而b[j]表示余数为j的sum个数 此时根据上面新得出的更新相应的b[j]这样在读入完毕之后就可以根据b[j]直接计算总方案数了
特别值得注意的是！！！！
计算余数为0的方案总数时候还要加上b[0] 也就是b[0]*(b[0]-1) div 2+b[0]
为什么？？ 因为余数为0的时候单独一个sum[i]就能成为一个方案了还有比如div 2可以用shr 1 这样可以加快速度
呼呼(～ o ～)~zZ 说得好累啊
我自己都快被讲糊涂了 呵呵
希望有不懂这道题目的人能看懂....
这样就不算白忙了 -
0
wang_yanheng LV 10 @ 2015-08-19 10:20:58
感谢340508965的题解，讲得很易懂。建议大家按 Ctrl + F 输入340508965 直达。
记住求和时一定要用 long long (即 int64)，否则最后一个点会爆 -
0
一眼看了题来源Matrix67，就觉得奇怪这道题怎么可能难度1。。。
我能说什么呢。。。大神们都是非常一致的回答。。。只是我想来想去也想不到这种方法。。。。。历经多次提交才终于AC，给出一种奇葩的做法。。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int a[500000];
int ml[100001];
int mr[100001];
int c,k;
void f(int l,int r){
int i,j;
if(l+100>r){ // 这里的100，本来是1，然后10，20，40，60，直到100 最后那个点才不超时。。。
for(i=l;i<r;i++){
int t= 0;
for(j=i;j<r;j++){
t += a[j];
if(t >= k) t-=k;
if(t == 0) c++;
}
}
return;
}
if(l+1==r){
if(a[l]==0) c++;
return;
}
//printf("%d,%d\n",l,r);int m = (l+r)>>1;
memset(ml,0,sizeof(ml));
memset(mr,0,sizeof(mr));
int t = 0;
for(i=m-1;i>=l;i--){
t += a[i];
ml[t % k]++;
}
t = 0;
for(i=m;i<r;i++){
t += a[i];
mr[t % k]++;
}
c += ml[0] * mr[0];
for(i=1;i<k;i++)
c += ml[i] * mr[k-i];
f(l,m);
f(m,r);
}int main()
{
int n;
scanf("%d%d",&n,&k);
int i,j;
for(i=0;i<n;i++){
scanf("%d",&a[i]);
a[i] = a[i] % k;
}f(0,n);
printf("%d",c % 1234567);
return 0;
} -
0
const
mo=1234567;
var
sum,ans:qword;
a:array[0..100000] of longint;
i,n,k,c:longint;begin
readln(n,k);
ans:=0; sum:=0; fillchar(a,sizeof(a),0); a[0]:=1;
for i:=1 to n do
begin
readln(c); c:=c mod k;
inc(sum,c); sum:=sum mod k;
inc(ans,a[sum]); ans:=ans mod mo;
inc(a[sum]);
end;
writeln(ans);
end. -
0
忘记去模了。。。WA50两次。。。
P1090连续数之和
Accepted记录信息
评测状态 Accepted
题目 P1090 连续数之和
递交时间 2014-10-20 21:22:23
代码语言 C++
评测机 上海红茶馆
消耗时间 340 ms
消耗内存 948 KiB
评测时间 2014-10-20 21:22:25评测结果
编译成功
测试数据 #0: Accepted, time = 0 ms, mem = 944 KiB, score = 10
测试数据 #1: Accepted, time = 15 ms, mem = 940 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 948 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 944 KiB, score = 10
测试数据 #4: Accepted, time = 15 ms, mem = 944 KiB, score = 10
测试数据 #5: Accepted, time = 15 ms, mem = 944 KiB, score = 10
测试数据 #6: Accepted, time = 15 ms, mem = 944 KiB, score = 10
测试数据 #7: Accepted, time = 31 ms, mem = 944 KiB, score = 10
测试数据 #8: Accepted, time = 109 ms, mem = 940 KiB, score = 10
测试数据 #9: Accepted, time = 140 ms, mem = 944 KiB, score = 10
Accepted, time = 340 ms, mem = 948 KiB, score = 100
代码
#include <iostream>
#include <cmath>
#include <stdio.h>
#include <algorithm>using namespace std;
int n , k;
int a[100000 + 2];
int i , j;
unsigned long long ans;
int x , y;
const int modd = 1234567;int abs( int a )
{
if( a < 0 )
return -a;
return a;
}int main()
{
while( scanf( "%d %d" , &n , &k ) != EOF )
{
for( i = 0 ; i < n ; i++ )
{
scanf( "%d" , &x );
y += x;
y %= k;
a[y]++;
}
a[0]++;
ans = ( a[0] * ( a[0] - 1 ) / 2 ) % modd;
for( i = 1 ; i < k ; i++ )
ans = ( ans + a[i] * ( a[i] - 1 ) / 2 ) % modd;
cout << ans % modd << endl;
}
return 0;
} -
0
第六十道AC
编译成功
测试数据 #0: Accepted, time = 0 ms, mem = 2404 KiB, score = 10
测试数据 #1: Accepted, time = 15 ms, mem = 2396 KiB, score = 10
测试数据 #2: Accepted, time = 15 ms, mem = 2392 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 2400 KiB, score = 10
测试数据 #4: Accepted, time = 15 ms, mem = 2392 KiB, score = 10
测试数据 #5: Accepted, time = 15 ms, mem = 2396 KiB, score = 10
测试数据 #6: Accepted, time = 15 ms, mem = 2400 KiB, score = 10
测试数据 #7: Accepted, time = 15 ms, mem = 2396 KiB, score = 10
测试数据 #8: Accepted, time = 93 ms, mem = 2396 KiB, score = 10
测试数据 #9: Accepted, time = 171 ms, mem = 2396 KiB, score = 10
Accepted, time = 354 ms, mem = 2404 KiB, score = 100
-
0
var n,k,i,tot,ans,x:longint;
a:array[0..100000] of longint;
begin
readln(n,k);fillchar(a,sizeof(a),0);a[0]:=1;
for i:=1 to n do
begin
readln(x);
tot:=(tot+x) mod k;
inc(a[tot]);
end;
for i:=0 to k do
if a[i]>1 then ans:=(ans+(a[i]*(a[i]-1)) div 2) mod 1234567;
write(ans);
end. -
0
-
0
jiaoyunhao LV 10 @ 2012-07-20 08:00:06
var
g:array[0..1000000] of longint;
t,p,k,n,i:longint;
tt,tot,x:int64;begin
readln(n,k); tt:=0; tot:=0;
for i:=0 to k do g[i]:=0; g[0]:=1;
for i:=1 to n do
begin read(x); tt:=tt+x; tt:=tt mod k;
tot:=(tot+g[tt]) mod 1234567;
inc(g[tt]); g[tt]:=g[tt] mod 1234567; end;
writeln(tot);
end. -
0
hjc5484855 LV 8 @ 2010-04-10 10:12:30
不好意思，发错位置了
-
0
SecretAgent LV 10 @ 2009-11-02 15:04:51
解释b[i]*(b[i]-1))shr 1 的意思
这个式子是这样的
b[i]*(b[i]-1)/2那么为什么是这个式子呢？
因为是有b[i]个数同余，
我们每次要从中拿出2个数进行组合
所以拿出的方案为C(2,b[i])全部加起来就是答案了
guoqianli
LV 8
@ 2015-10-06 16:32:08
