usrbin吧 关注:310贴子:45,934

求助一道题~~

只看楼主收藏回复


Two distinct positive integer numbers with decimal notations of the same length are called similar, if their decimal notations can be obtained from each other by permuting the digits.
How many numbers from the segment [l, r] have exactly one similar number in that segment?
Input
The input file contains two integer numbers l and r (1 ≤ l ≤ r ≤ 1015).
Output
Output one integer number — the sought amount.



1楼2010-12-25 15:11回复
    上面1015是10^15...
    sample input
    10 99
    sample output
    72
    http://acm.sgu.ru/problem.php?contest=0&problem=420


    2楼2010-12-25 15:21
    回复
      2025-11-04 05:23:41
      广告
      不感兴趣
      开通SVIP免广告
      很粗糙的算法:
      设Sn={(a1,a2..,an)|a1>=a2>=..>=an && n<=15 && 0<=ai<=9},可以算得|S1|+|S2|+...+|Sn|<4*10^6,这就可以做文章了
      l前面补0拼成和r一样长度,设k=|r|.对于任意非负整数b=b1b2...bk,可以从左到右算出每个Sk排列<=b的数目f(b)。统计f(r)-f(l)=2的组合数再乘以2即可
      算法时间复杂度O(4*10^6*15)
      


      3楼2010-12-25 21:16
      回复
        应该是f(r)-f(l-1)=2


        4楼2010-12-25 21:17
        回复
          usrbin神犇大概看错题目了...我一开始也看错了...
          题目要求similar number(相似数)只能有一个,而且是在[L,R]范围内。
          所以神马 f[R] - f[L-1] 这类的想法直接破碎 TwT
          


          5楼2010-12-25 21:46
          回复
            回复:5楼
            没错啊?我要求的就是[L,R]里某个组合出现的数目f=f(R)-f(L-1),如果=2不就累加吗?


            7楼2010-12-25 21:49
            回复
              啊。。。对。。是这样。。但是怎么在O(k)的时间里算出在 <= b的个数?


              8楼2010-12-25 21:55
              回复
                回复:8楼
                考虑第i位,1-(i-1)位与b相同,[0,bi)的时候第i+1->第k位可以取任何数字,因此每个组合[c1,c2,..c10](c1+c2+..+c10)组合的数目=(k-i)!/pi(c[i]!),累加上去..


                9楼2010-12-25 21:59
                回复
                  2025-11-04 05:17:41
                  广告
                  不感兴趣
                  开通SVIP免广告
                  回复:6楼
                  不过你这个方法显然比我的更好..WS我的吧


                  10楼2010-12-25 22:12
                  回复
                    我勒个去...这光头不是孟非么.....


                    11楼2010-12-25 22:14
                    回复
                      回复:11楼
                      http://tieba.baidu.com/f?kz=962636186


                      12楼2010-12-25 22:15
                      回复
                        我有更好的想法。。。


                        IP属地:上海13楼2010-12-26 11:35
                        回复
                          蛋蛋姐赐教~


                          14楼2010-12-26 23:07
                          回复
                            问下java里面有自动排序且去掉重复数值的函数麽


                            IP属地:上海15楼2011-09-14 16:19
                            回复