题解

125 条题解

  • 17
    @ 2017-03-05 19:13:49

    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
    @ 2017-04-19 13:00:05
    #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
    @ 2018-07-18 21:27:42

    本文是实质是利用前缀数组的数学题
    (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
    @ 2016-08-10 17:53:23
    #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
    @ 2015-10-06 16:32:24

    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
    @ 2017-09-16 18:08:38

    #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
    @ 2017-05-08 07:50:02
    #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
    @ 2017-05-07 22:41:31
    #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
    @ 2016-11-07 13:23:09

    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.

  • 0
    @ 2016-10-07 13:48:24

    加了个输入优化,时间从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
    @ 2016-06-07 20:05:42
    #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
    @ 2016-05-04 20:46:08

    #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
    @ 2016-04-03 15:09:02
    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
    @ 2016-02-21 12:33:44
    /* ***********************************************
    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
    @ 2015-10-06 16:33:31

    顶一下

    帮他转载】

    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
    @ 2015-10-06 16:32:20

    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
    @ 2015-10-06 16:32:18

    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
    @ 2015-10-06 16:32:16

    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
    @ 2015-10-06 16:32:14

    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
    @ 2015-10-06 16:32:11

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

信息

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