9-數對的個數

給一個正整數的序列ai,輸出共有多少對數字的和為s.

最多有10000000個數字，數字的最大值為100000（思考如果最大為1e9）如果結果過大，就輸出對1e9+7取模之後的結果。

代碼1（自己寫的）：

#include <iostream>
#include <stdio.h>
const int maxn = 100003;
#define mod 1000000007;

using namespace std;
int num[maxn];      //存儲某個數值的個數
int main()
{
    long int s,x;   //s為所求數對和,x為數值
    int n;            //n為輸入的數值個數
    long sum = 0;       //數對個數
    scanf("%ld%ld",&s,&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%ld",&x);
        num[x]++;
    }
    for(int i=0;i<=s/2;i++)
    {
        if(i == (s-i))
            {
                sum = (sum+(num[i]*(num[i]-1)/2))%mod;
            }
        else
            sum = (sum+num[i]*num[s-i])%mod;
    }
    printf("%ld\n",sum);

    return 0;
}
           

代碼2（西交wrong）：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <map>
#define MOD 1000000007
using namespace std;
const int maxn = 100005;
typedef pair<int,int> P;
int main()
{
    int n,s,x;
    long long res=0;
    cin>>n>>s;
    memset(num,0,sizeof(num));
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&x);
        num[x]++; //
    }
    for(int i=0;i<=s/2;i++) //(a,b) a<=b
    {//0 1 2 3   7 6 5 4
        if(i==s-i) res=(res+1ll*num[i]*(num[i]-1)/2)%MOD;
        else res=(res+1ll*num[i]*num[s-i])%MOD;
        //1 1 1 1
    }
    cout<<res<<endl;
    //sort(a+1,a+1+n);
    //O(n)
    //0 0 1 1 1 1 1 2 2 2 2 2 3 3 3 3 3     //先排序，然後首尾指針同時向内掃
      //|   |       |          |
    /*
    for(int i=1;i<=n;i++)                   //暴力解法
    {
        if(a[i]>s) break;
        for(int j=i+1;j<=n;j++) //1 2he 2 1
            if(a[i]+a[j]==s) res++;
    }
    */
    //cout<<res%1000000007<<endl;
   return 0;
}

           

（感謝西交wrong學長提供以上題目練習）