Sum Zero
Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65535/32768 K (Java/Others)
Problem Description
There are 5 Integer Arrays and each of them contains no more than 300 integers whose value are between -100,000,000 and 100,000,000, You are to find how many such groups (i,j,k,l,m) can make A[0][i]+A[1][j]+A[2][k]+A[3][l]+A[4][m]=0. Maybe the result is too large, you only need tell me the remainder after divided by 1000000007.
Input
In the first line, there is an Integer T(0<T<20), means the test cases in the input file, then followed by T test cases.
For each test case, there are 5 lines Integers, In each line, the first one is the number of integers in its array.
Output
For each test case, just output the result, followed by a newline character.
Sample Input
1
3 4 -2 3
5 -5 -1 -7 -10 -1
5 -10 2 4 -6 2
2 -4 -1
5 -7 -7 -1 -4 -6
Sample Output
Author
Sempr|CrazyBird|hust07p43
Source
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<iostream>
#include<cstdio>
#include<cmath>
#include<string>
#include<queue>
#include<algorithm>
#include<stack>
#include<cstring>
#include<vector>
#include<list>
#include<bitset>
#include<set>
#include<map>
#include<time.h>
using namespace std;
#define LL long long
#define bug(x) cout<<"bug"<<x<<endl;
const int N=5e4+10,M=1e5+10,inf=1e9+10;
const LL INF=1e18+10,mod=1e9+7;
const double eps=(1e-8),pi=(4*atan(1.0));
int si[10];
int a[6][310];
struct handhash
{
const static int side=1e5+7;
vector<int>v[M];
vector<int>nu[M];
void init()
{
for(int i=0;i<side;i++)
v[i].clear(),nu[i].clear();
}
void add(int x)
{
int z=(abs(x))%side;
for(int i=0;i<v[z].size();i++)
if(v[z][i]==x)
{
nu[z][i]++;
return;
}
v[z].push_back(x);
nu[z].push_back(1);
}
int query(int x)
{
int z=(abs(x))%side;
for(int i=0;i<v[z].size();i++)
if(v[z][i]==x)return nu[z][i];
return 0;
}
}mp;
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
mp.init();
for(int i=1;i<=5;i++)
{
scanf("%d",&si[i]);
for(int j=1;j<=si[i];j++)
scanf("%d",&a[i][j]);
}
for(int i=1;i<=si[1];i++)
for(int j=1;j<=si[2];j++)
mp.add(a[1][i]+a[2][j]);
LL ans=0;
for(int k=1;k<=si[3];k++)
for(int i=1;i<=si[4];i++)
for(int j=1;j<=si[5];j++)
ans+=mp.query(-a[3][k]-a[4][i]-a[5][j]);
printf("%lld\n",ans%mod);
}
return 0;
}
Sum Zero
Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65535/32768 K (Java/Others)
Total Submission(s): 1055 Accepted Submission(s): 312
Problem Description
There are 5 Integer Arrays and each of them contains no more than 300 integers whose value are between -100,000,000 and 100,000,000, You are to find how many such groups (i,j,k,l,m) can make A[0][i]+A[1][j]+A[2][k]+A[3][l]+A[4][m]=0. Maybe the result is too large, you only need tell me the remainder after divided by 1000000007.
Input
In the first line, there is an Integer T(0<T<20), means the test cases in the input file, then followed by T test cases.
For each test case, there are 5 lines Integers, In each line, the first one is the number of integers in its array.
Output
For each test case, just output the result, followed by a newline character.
Sample Input
1
3 4 -2 3
5 -5 -1 -7 -10 -1
5 -10 2 4 -6 2
2 -4 -1
5 -7 -7 -1 -4 -6
Sample Output
Author
Sempr|CrazyBird|hust07p43
Source
hdu 1895 Sum Zero hash
原文:http://www.cnblogs.com/jhz033/p/7608851.html