题解 - Vijos

18

冲啊小笼包 LV 9 @ 8 年前

2333,过了2年，回过头1A了这题.

刚刚在读组合数学这本经典书,读到鸽巢原理的时候看到了类似这个题的一个例子，于是过来A了这题。分享下题解吧.也算给自己看书做个笔记。

书上的原例子是这样的。

假定有m个数的序列一定能取出一个连续的区间，使得这个区间被m整除。

这个命题可以用鸽巢原理证明(n+1个东西放入n个盒子里，必有一个盒子内东西有2个或2个以上)

回到例子
我们现在有M个数的序列,也就是说可以构成m个前缀和。（因为是连续区间嘛）我们让这M个数分别对M取余,很显然,因为对M取余数至多有m（0..m-1）种可能，也就是必有2个连续区间的和（就是前缀和）对M的余数相同。

那么这2个区间想减，得到的序列对M的余数肯定是0了，大家联立方程作差即可。
那么这个例子就证明了。

在这题里面,这个例子给了一个最大的启示，没错，对所有连续区间(也就是前缀和)除以K，必定有个余数，如果有2个序列余数相同，只要作差，就能被K整除！！！

那么我们只需要计算前缀和后，对所有的前缀和对K取余数,然后记录每个余数的数量,假如余8的情况有7种，那么每2个序列必定可以作差形成一个答案，只要ans = ans + C（7,2）就可以了，C为组合数公式。

PS：有一个特殊情况，就是当余数为0时，单个序列也是一种答案，因此还要再额外加一次余数为0的序列数。

然后输出ans，AC
（注意使用组合数公式时应该优化加快效率并且防止溢出）

参考代码

    ###C++ CODE
    #include <stdio.h>
    #include <math.h>
    #include <stdlib.h>
    #include <string.h>
    #include <string>
    #include <algorithm>
    #include <iostream>
    #include <ctype.h>
    #include <set>
    #include <map>
    #include <vector>
    using namespace std;

    typedef long long lint;
    lint a[500010],i,j,n,k,num,b[100010],ans;

    lint C(lint n, lint m){
            lint re = 1, i;
            if(m>(n-m))m = n - m;
            for(i = 1; i <= m; ++i){
                    re = re*(i+(n-m))/i;
            }
            return re;
    }


    int main(){
            scanf("%I64d%I64d",&n,&k); ans = 0;
            for(i = 1; i <= n; ++i){
                    scanf("%I64d",&num);
                    a[i] = a[i - 1] + num;
                    ++b[a[i] % k];
            }
            ans += b[0];
            for(j = 0; j < k; ++j){
                    if(b[j] >= 2){
                            ans += C(b[j],2) % 1234567;
                    }
            }
            printf("%I64d\n",ans % 1234567);
            return 0;
    }

8

larryzhong LV 9 @ 8 年前

#include <iostream>
using namespace std;

const int maxk = 100010, mod = 1234567;
int _count[maxk];

int main() {
    ios::sync_with_stdio(false);
    int n, k;
    cin >> n >> k;
    long long sum = 0, result = 0, x;
    for (int i = 1; i <= n; i++) {
        cin >> x;
        sum += x;
        if (sum % k == 0)
            result++;
        result = (result + _count[sum % k]) % mod;
        _count[sum % k]++;
    }
    cout << result << endl;
    return 0;
}

6

mobileliker LV 7 @ 6 年前

本文是实质是利用前缀数组的数学题
（1）利用连续数的数组的前缀和数组，即：

原数组： 1 2 6 3 7 4

前缀数组：0 1 3 9 12 19 23

连续数的和可以表示为对应前缀数组相减，即：

2 6 3 = 9 = 12 - 2

（2）题目的要求连续能被整除，那么相减能够被 3（K）整除，那么我们可以将前缀数组的值全部Mod K，即：

前缀数组：0 1 0 0 0 1 2

那么题目可转为从前缀数组任意取两个数，值相同的所有情况；

（3）那我们就建立一个投票箱（大小为K），累加所有结果的数量，即：

投票箱：ticket[0] = 4, ticket[1] = 2, ticket[2] = 1

总可能就等于对每个投票箱，任意取两个值的可能性，即：C（ticket[i]，2）= ticket[i] * (ticket[i] - 1) / 2

（4）另外本题还考虑结果为0的前缀值，它本身就满足能够被0整除了，所以还要在前面计算的基础上加上ticket[0]

（5）最后因为数可能很大超出long long，题目给出Mod 1234567，因此每次累加都要mod一次，防止溢出

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>

using namespace std;

int arr[500002];
int ticket[100002];

int main()
{
    //freopen("input.txt", "r", stdin);
    
    int i, j, tmp;
    int n, k;
    
    memset(ticket, 0, sizeof(ticket));
    
    scanf("%d%d", &n, &k);
    
    scanf("%d", &arr[0]);
    arr[0] = arr[0] % k;
    ticket[arr[0]]++;
    for(i = 1; i < n; ++i)
    {
        scanf("%d", &arr[i]);
        arr[i] = (arr[i - 1] + arr[i]) % k;
        ticket[arr[i]]++;
    }
    
//  for(i = 0; i < n; ++i) printf("%d ", arr[i]);
//  printf("\n");
//
//  for(i = 0;i < k; ++i) printf("%d ", ticket[i]);
//  printf("\n");

    long sum = ticket[0] % 1234567;
    for(int i = 0; i < k; ++i)
    {
        sum += ticket[i] * (ticket[i] - 1) / 2;
        sum = sum % 1234567;
    }
    
    printf("%ld\n", sum); 
    
    //fclose(stdin);
    
    return 0;
}

3

liuyiah LV 10 @ 8 年前

#include <cstdio>
#include <cstring>
int n,k,tmp;
unsigned long long sum=0,ans=0,R[100001];
int main(){
    scanf("%d%d",&n,&k);
    memset(R,0,sizeof(R));
    for (int i=1;i<=n;i++){
        scanf("%d",&tmp);
        sum+=tmp;
        if (sum%k==0) ans++;
        ans=(ans+R[sum%k])%1234567;
        R[sum%k]++;
    }
    printf("%I64d",ans);
}

1

guoqianli LV 8 @ 9 年前

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

xuyue LV 10 @ 7 年前

#include <iostream>
using namespace std;
long long a[500010],sum[500010],ge[100010];
int main()
{
int n,k;cin>>n>>k;ge[0]=1;
for(int i=1;i<=n;i++)cin>>a[i],sum[i]=(sum[i-1]+a[i])%k,ge[sum[i]]++;
long long sumsum=0;
for(int i=0;i<k;i++)sumsum=(sumsum+(ge[i]*(ge[i]-1))/2)%1234567;
cout<<sumsum;
return 0;
}
注意要用 long long防止溢出

0

PowderHan LV 10 @ 8 年前

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

int n,k,c;
unsigned long long sum=0,ans=0,R[100001];

int main()
{
    scanf("%d%d",&n,&k);
    for (int i=1;i<=n;i++)
    {
        scanf("%d",&c);
        sum+=c;
        if (sum%k==0) ans++;
        ans=(ans+R[sum%k])%1234567;
        R[sum%k]++;
    }
    cout<<ans<<endl;
    return 0;
}

0

PowderHan LV 10 @ 8 年前

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

int n,k,tmp;
unsigned long long sum=0,ans=0,R[100001];

int main()
{
    scanf("%d%d",&n,&k);
    for (int i=1;i<=n;i++)
    {
        scanf("%d",&tmp);
        sum+=tmp;
        if (sum%k==0) ans++;
        ans=(ans+R[sum%k])%1234567;
        R[sum%k]++;
    }
    cout<<ans<<endl;
    return 0;
}

0

氢氧化小2b LV 8 @ 8 年前

O(1)做法。
(sum[j]-sum[i]) mod k=0即sum[j] mod k=sum[i] mod k
进行计数并排列组合
测试数据 #0: Accepted, time = 0 ms, mem = 1204 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 1204 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 1204 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 1200 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 1204 KiB, score = 10
测试数据 #5: Accepted, time = 15 ms, mem = 1204 KiB, score = 10
测试数据 #6: Accepted, time = 15 ms, mem = 1204 KiB, score = 10
测试数据 #7: Accepted, time = 15 ms, mem = 1200 KiB, score = 10
测试数据 #8: Accepted, time = 46 ms, mem = 1200 KiB, score = 10
测试数据 #9: Accepted, time = 109 ms, mem = 1200 KiB, score = 10
Accepted, time = 200 ms, mem = 1204 KiB, score = 100
pascal program P1090; 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.

氢氧化小2b @ 8 年前

说错了是O(n)...

0

dfxxlyc LV 8 @ 8 年前

加了个输入优化，时间从3000ms直接变成1000ms
测试数据 #0: Accepted, time = 78 ms, mem = 43012 KiB, score = 10
测试数据 #1: Accepted, time = 109 ms, mem = 43012 KiB, score = 10
测试数据 #2: Accepted, time = 93 ms, mem = 43032 KiB, score = 10
测试数据 #3: Accepted, time = 93 ms, mem = 43020 KiB, score = 10
测试数据 #4: Accepted, time = 78 ms, mem = 43020 KiB, score = 10
测试数据 #5: Accepted, time = 93 ms, mem = 43020 KiB, score = 10
测试数据 #6: Accepted, time = 93 ms, mem = 43020 KiB, score = 10
测试数据 #7: Accepted, time = 109 ms, mem = 43020 KiB, score = 10
测试数据 #8: Accepted, time = 140 ms, mem = 43020 KiB, score = 10
测试数据 #9: Accepted, time = 156 ms, mem = 43012 KiB, score = 10
Accepted, time = 1042 ms, mem = 43032 KiB, score = 100
'''Java
import java.io.*;
import java.util.Scanner;

public class P1090 {

public static final int MOD_NUM=1234567;
public static void main(String[] args) throws IOException {
Scanner sc =new Scanner(new BufferedInputStream(System.in));
StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));

//while(in.nextToken()!=StreamTokenizer.TT_EOF){
in.nextToken();
int n =(int)in.nval;
in.nextToken();
int k=(int)in.nval;
in.nextToken();
int[] a =new int[n];
int[] b =new int[k];
a[0]=(int)in.nval;
int sum=a[0]%k;
b[sum]++;
for(int i=1;i<n;i++){
in.nextToken();
a[i]=(int)in.nval;
sum=(a[i]+sum)%k;
b[sum]++;
}
long count = b[0];
for(int i=0;i<k;i++){
count += ((b[i]-1)*b[i])/2;
}
count %= MOD_NUM;
out.println(count);
//}
out.flush();
}
}
'''Java

0

qig159357 LV 8 @ 8 年前

#include<cstdio>
#include<vector>
#include<map>
using namespace std;
int const mod=1234567;

vector<int> s;
map<int,int> f;
int n,k,ans=0;

int main()
{
    /*freopen("in","r",stdin);*/
    scanf("%d%d",&n,&k);
    s.push_back(0);
    for(int i=1;i<=n;i++)
    {
        int a;
        scanf("%d",&a);
        a=(a+s[i-1])%k;
        s.push_back(a);
    }
    for(int i=0;i<=n;i++)
    {
        if(f.count(s[i]))
        {
            ans= (f[s[i]]+ans)%mod;
            f[s[i]]++;
        }
        else
        {
            f[s[i]]=1;
        }
    }
    printf("%d\n",ans);
    return 0;
}

0

651291702@qq.com LV 8 @ 9 年前

#include <cstdio>
#include <vector>
using namespace std;
const int N1=500000+5;
const int N2=100000+5;
int n,m,a[N1],s[N1],ans=0;
vector <int > c[N2];
int main()
{
scanf("%d%d",&n,&m); s[0]=0;
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
c[0].push_back(0);
for(int i=1;i<=n;i++)
{s[i]=(s[i-1]+a[i])%m;
c[s[i]].push_back(i);
}
for(int i=1;i<=n;i++)
{
int k=s[i],j;
for(j=0;j!=c[k].size() && c[k][j]<=i;j++);
if(j!=0) ans+=(j-1); ans%=1234567;
}

printf("%d",ans);
return 0;
}

测试数据 #0: Accepted, time = 0 ms, mem = 5644 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 5648 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 5660 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 5704 KiB, score = 10
测试数据 #4: Accepted, time = 15 ms, mem = 5700 KiB, score = 10
测试数据 #5: Accepted, time = 78 ms, mem = 5964 KiB, score = 10
测试数据 #6: Accepted, time = 15 ms, mem = 6068 KiB, score = 10
测试数据 #7: Accepted, time = 125 ms, mem = 7148 KiB, score = 10
测试数据 #8: Accepted, time = 171 ms, mem = 7876 KiB, score = 10
测试数据 #9: Accepted, time = 296 ms, mem = 8824 KiB, score = 10

0

Cothrax LV 8 @ 9 年前

var count:array[0..100001] of qword;
  sum,ans:qword;
  each:integer;
  i,n,k:longint;

begin
  fillchar(count,sizeof(count),0);
  read(n,k);
  sum:=0;ans:=0;
  for i:=1 to n do begin
    read(each);
    sum:=sum+each;
    if (sum mod k)=0 then ans:=ans+1;
    ans:=(ans+count[sum mod k]) mod 1234567;
    count[sum mod k]:=count[sum mod k]+1;
  end;
  writeln(ans);
end.

0

BH_2 LV 8 @ 9 年前

/* ***********************************************
Author        :guanjun
Created Time  :2016/2/21 11:05:53
File Name     :vijosp1090.cpp
************************************************ */
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <math.h>
#include <stdlib.h>
#include <iomanip>
#include <list>
#include <deque>
#include <stack>
#define ull unsigned long long
#define ll long long
#define mod 90001
#define INF 0x3f3f3f3f
#define maxn 10000+10
#define cle(a) memset(a,0,sizeof(a))
const ull inf = 1LL << 61;
const double eps=1e-5;
using namespace std;
priority_queue<int,vector<int>,greater<int> >pq;
struct Node{
int x,y;
};
struct cmp{
    bool operator()(Node a,Node b){
        if(a.x==b.x) return a.y> b.y;
        return a.x>b.x;
    }
};

bool cmp(int a,int b){
    return a>b;
}
ll a[500100];
ll sum[500100];
ll b[100100];
int main()
{
    #ifndef ONLINE_JUDGE
    //freopen("in.txt","r",stdin);
    #endif
    //freopen("out.txt","w",stdout);
    int n,k;
    while(cin>>n>>k){
        cle(sum);
        cle(b);
        ll ans=0;
        for(int i=1;i<=n;i++){
            cin>>a[i];
            sum[i]=sum[i-1]+a[i];
            b[sum[i]%k]++;
        }
        for(int i=0;i<k;i++){
            //cout<<b[i]<<endl;
            if(i==0)ans+=b[0];
            ans=(ans+b[i]*(b[i]-1)/2)%1234567;
        }
        cout<<ans<<endl;
        //printf("%lld\n",ans);
    }
    return 0;
}

0

guoqianli LV 8 @ 9 年前

顶一下

帮他转载】

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　　说得好累啊
我自己都快被讲糊涂了呵呵
希望有不懂这道题目的人能看懂....
这样就不算白忙了

冲啊小笼包 @ 9 年前

并不是初中的。这类似数学的数列迭代求通项
居鲁士 @ 8 年前

666666

0

guoqianli LV 8 @ 9 年前

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

guoqianli LV 8 @ 9 年前

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

guoqianli LV 8 @ 9 年前

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

guoqianli LV 8 @ 9 年前

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

guoqianli LV 8 @ 9 年前

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　　说得好累啊
我自己都快被讲糊涂了呵呵
希望有不懂这道题目的人能看懂....
这样就不算白忙了

题解

125 条题解

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

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

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

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

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

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

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

连续数之和

信息

状态

开发

支持

题解

125 条题解

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

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

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

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

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

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

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

连续数之和

信息

状态

开发

支持

还没有账户？

登录