# hdu 6093-Rikka with Number(计数)

www.MyException.Cn  网友分享于：2013-08-16  浏览：0次
hdu 6093---Rikka with Number(计数)

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:

Input
The first line contains a number

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

Sample Input
2
5 20
123456 123456789

Sample Output
3
114480

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--){
}
}
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);
}
}
}