轻院校赛-zzuli 2266: number【用每位的二进制的幂的和来进行hash（映射）处理】

zzuli 2266: number

大致题意：

 

给定n，问有多少数对<x, y>满足：

x, y∈[1, n], x < y

           x, y中出现的[0, 9]的数码种类相同

输入

一个整数n (n <= 107)

输出

输出一个数即答案

样例输入          

30 

样例输出        

  3

---

大致思路：

　　N的值其实也不是很大，可以考虑跑一次循环把每个值全部分离一次，然后将用二进制上的第0-第9位的‘1’来表示数码0-9，并且要用数组进行标记防止加了两次！

 

　　至于hash2 同样因为2^10也就1204，其实开到1000就够了！

 

　　在hash2中1--1000每个数字都代表一种种类！

 

　　求得是两个同种类型的组合，n个同类数可以构成n*(n-1)种不重不漏的组合！

---

AC 题解：

 #define N 2005

 int main(){

     int n;

     int hash2[];

     while(scanf("%d",&n)!=EOF){

         memset(hash2,,sizeof(hash2));

         for(int i=;i<=n;i++){

             int x=i;

             int vis[]={};

             int val=;

             while(x>){

                 int y=x%;

                 if(!vis[y]){

                     val+= <<y;

                     vis[y]=;

                 }

                 x/=;

             }

             hash2[val]++;

         }

         ll ans=;

         for(int i=;i<=;i++){

             if(hash2[i]>=){

               //  printf("%d %d\n",i,hash2[i]);

                 ans+=(ll)hash2[i]*(ll)(hash2[i]-)/(ll);

             }

         }

         printf("%lld\n",ans);

     }

     return ;

 }

（头文件都私奔去了！）