首页 > > 程序设计 > C/C++ >

hdu 6093---Rikka with Number(计数)

2018-06-17 22:06:19来源：未知阅读 ()

题目链接

Problem Description

As we know, Rikka is poor at math. Yuta is worrying about this situation, so he gives Rikka some math tasks to practice. There is one of them:

In radix

Input

The first line contains a number

Output

For each testcase, print a single line with a single number -- the answer modulo

Sample Input

5 20

123456 123456789

Sample Output

114480

题意：一个数 x 如果用 d 进制进行表示，是0~d-1的一个排列（不能以0打头），那么这个数称为 “优数”，一个数只要存在任意一个 d 进制符合0~d-1的一个排列，那么就是“优数”,问L到R区间有多少个优数？

思路：按进制计算，找边界，一定存在dl和dr是边界，dl+1~dr-1 进制的所有排列都在L~R之间。

官方题解：

代码如下：

import java.math.BigInteger;
import java.util.Scanner;

public class Main {
    static int MAXN = 1600;
    static BigInteger[] dx = new BigInteger[MAXN];
    static long MOD = 998244353;
    static long [] fac = new long [MAXN];
    static void Init(){
        dx[0] = BigInteger.ZERO;
        dx[1] = BigInteger.ZERO;
        for(int i=2; i<MAXN; i++){
            dx[i] = BigInteger.ZERO;
            for(int j=i-1; j>=0; j--){
                dx[i] = dx[i].multiply(BigInteger.valueOf(i)).add(BigInteger.valueOf(j));
            }
        }
        fac[0] = fac[1] = 1;
        for(int i=2; i<MAXN; i++) fac[i]=fac[i-1]*i%MOD;
    }
    static int Low(BigInteger x){
        int low=0, high=MAXN-1;
        while(low < high){
            int mid = (low+high)/2;
            if(dx[mid].compareTo(x)>=0)high = mid;
            else low = mid+1;
        }
        return high;
    }
    public static void main(String[] args){
        Init();
        Scanner in = new Scanner(System.in);
        int T = in.nextInt();
        for(int cas=1; cas<=T; cas++){
            int [] vis = new int [MAXN];
            for(int i=0; i<MAXN; i++) vis[i] = 0;
            BigInteger L, R;
            L = in.nextBigInteger();
            R = in.nextBigInteger();
            int dl = 0, dr = 0;
            dl = Low(L)+1;
            dr = Low(R)-1;
            long ans = fac[dr]-fac[dl-1];
            ans = (ans%MOD+MOD)%MOD;
            if(dl > dr) ans = 0; 
            dl--; dr++;
            
            long ans2=0;
            BigInteger tmp = (BigInteger.valueOf(dl)).pow(dl-1);
            for(int i=dl; i>=1; i--){
                int top = L.divide(tmp).intValue();
                if(i==dl && top==0) { ans2 = (ans2+fac[dl]-fac[dl-1])%MOD; break; }
                int cnt=0;
                for(int o=top+1;o<dl;o++) if(vis[o]==0) cnt++;
                ans2 = (ans2+(cnt)*fac[i-1]%MOD)%MOD;
                if(vis[top] == 1) break;
                L = L.mod(tmp);
                if(i==1 && vis[top]==0) ans2=ans2+1;
                vis[top] = 1;
                tmp = tmp.divide(BigInteger.valueOf(dl));
            }
            
            long ans1 = 0;
            for(int i=0; i<MAXN; i++) vis[i] = 0;
            tmp = (BigInteger.valueOf(dr)).pow(dr-1);
            for(int i=dr; i>=1; i--)
            {
                int top = R.divide(tmp).intValue();
                if(i==dr && top==0) {ans1 = (ans1+fac[dr]-fac[dr-1]%MOD); break;}
                int cnt=0;
                for(int o=top+1;o<dr;o++) if(vis[o]==0) cnt++;
                ans1 = (ans1+(cnt)*fac[i-1]%MOD)%MOD;
                if(vis[top] == 1) break;
                R = R.mod(tmp);
                vis[top] = 1;
                tmp = tmp.divide(BigInteger.valueOf(dr));
            }
//            System.out.println("ans1 -> "+ans1);
//            System.out.println("ans2 -> "+ans2);
//            System.out.println("ans  -> "+ans);
//            System.out.println("DL -> "+dl);
//            System.out.println("DR -> "+dr);
            ans = ans+ans2 + fac[dr]-fac[dr-1]-ans1;
            if(dl==dr) ans=ans2-ans1;
            ans = (ans%MOD+MOD)%MOD;
            System.out.println(ans);
        }
    }
}