「CJOJ2724」Number

Description

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

x，y 属于 [1,n] 且 x<y
x与y中出现的 [0,9] 的数码种类相同。

Input

一个整数 n 。

Output

输出一个数即所求满足条件的数对答案。

Sample Input

Sample Output

Hint

数据范围与约定
对于30% 的数据，(n<=10^3)
对于100的数据，(n<=10^7)

题解

这道题目的做法很妙，因为x，y由同样的数字构成，所以我们把每一位数字安排在一个二进制位上，就是一位一位搞。具体看代码。

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<iostream>
#include<algorithm>
#define file(a) freopen(a".in","r",stdin);freopen(a".out","w",stdout);
#define re register
#define ll long long
using namespace std;

inline int gi(){
	int sum=0,f=1;char ch=getchar();
	while(ch>'9' || ch<'0'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0' && ch<='9'){sum=(sum<<3)+(sum<<1)+ch-'0';ch=getchar();}
	return f*sum;
}
const int maxn=10010;
ll v[maxn];
int main(){
	int i,j,k,n,m;
	scanf("%d",&n);
	ll ans=0;
	for(i=1;i<=n;i++){
            int x=i,now=0;
            while(x){
                int k=x%10;
                now|=1<<k;
                x/=10;
            }
            ans+=v[now]++;
        }
	printf("%lld
",ans);
	return 0;
}