Warsaw University Contest Petrozavodsk, Thursday, January 31, 2008 F题，Gym100096F

题目分析：
集合双Hash
 1 #include<bits/stdc++.h>
 2 #define Mod1 1000000009
 3 #define Mod2 1000000007
 4 #define maxn 510
 5 #define LL long long 
 6 #define mp make_pair
 7 #define Pii pair<LL,LL>
 8 #define fi first
 9 #define se second
10 #define push_back
11 using namespace std;
12 LL hash1[maxn],hash2[maxn];
13 int n,seg[maxn];
14 LL ksm(LL base,LL m,LL mod){
15     LL res=1;
16     while(m){
17         if(m&1) res=(res*base)%mod;
18         base=(base*base)%mod;
19         m>>=1;
20     }
21     return res;
22 }
23 void pre_hash(){
24     int ans1=0,ans2=0;
25     for(int i=0;i<=500;i++){
26         hash1[i]=ksm(i,i+5,Mod1);
27         hash2[i]=ksm(i,i+5,Mod2);
28     }
29 }
30 Pii getHash(set<int> &str){
31     set<int>::iterator it;
32     LL ans1=0,ans2=0;
33     for(it=str.begin();it!=str.end();++it){
34         ans1=(ans1+hash1[*it])%Mod1;
35         ans2=(ans2+hash2[*it])%Mod2;
36     }
37     return mp(ans1,ans2);
38 }
39 set<int> s;
40 set<Pii> ss;
41 int main(){
42     freopen("numbereater.in","r",stdin);
43     freopen("numbereater.out","w",stdout);
44     pre_hash();
45     cin>>n;
46     for(int i=1;i<=n;i++) scanf("%d",&seg[i]);
47     for(int i=1;i<=n;i++){
48         s.clear();
49         for(int j=i;j<=n;j++){
50             s.insert(seg[j]);
51             ss.insert(getHash(s));
52         }
53     }
54     cout<<ss.size();
55     return 0;
56 }