2266: number（灵性数位dp）

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std ;

#define LL long long
int n ;
int times[1 << 10] ;
int b , s ;
LL result ;
// 注意result开longlong要不会爆炸

int main()
{

    cin >> n ;

    result = 0 ;
    memset(times , 0 , sizeof(times)) ;

    for(int i = 1 ; i <= n ; i++)
    {
        /*
        对从1到n的每个数字，分离每个数位上的数字，
        然后将1向左移动相应的位数，相同的数字移动的位置相同
        使用相同的数字组成的数，的s值是相同的
        而且s值每出现一次，都会出现前面s出现次数的数对对数
        */
        s = 0 ;
        int x = i ;
        while(x)
        {
            b = x % 10 ;
            x /= 10 ;
            s = s | (1 << b) ;
        }
        result += times[s] ;
        times[s] ++ ;
    }


    cout << result << endl ;

    return 0 ;
}