http://acm.timus.ru/problem.aspx?space=1&num=1310
题目中说的 “the lexicographically increasing list”
10 和 2 谁更小呢，我刚开始没管这么多，直接按数的大小算的，把 2 放在了 10 的前面
然后也过了，但是题意是不是这个意思？
思路：
数位DP + 二分
代码：
import java.math.BigInteger;
import java.util.Scanner; public class Main { /**
* @param args
*/
static final int N = 105;
static final int M = 55;
static final BigInteger[][][] dp=new BigInteger[N][M][M];
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner in = new Scanner(System.in);
for(int i=0;i<N;++i){
for(int j=0;j<M;++j){
for(int l=0;l<M;++l){
dp[i][j][l]=BigInteger.ZERO;
}
}
}
int n,m,k;
BigInteger b;
n=in.nextInt();
m=in.nextInt();
k=in.nextInt();
b=in.nextBigInteger();
b=b.add(BigInteger.ONE);
dp[0][1][0]=BigInteger.ONE;
for(int i=0;i<n;++i){
for(int l=0;l<k;++l){
BigInteger tmp=BigInteger.ZERO;
for(int j=1;j<=m;++j){
tmp=tmp.add(dp[i][j][l]);
}
for(int w=1;w<=m;++w){
dp[i+1][w][(l+w)%k]=dp[i+1][w][(l+w)%k].add(tmp);
}
}
}
BigInteger l=BigInteger.ZERO;
BigInteger r =BigInteger.valueOf(m).pow(n).subtract(BigInteger.ONE); while(l.compareTo(r)<=0){
BigInteger mid=l.add(r).divide(BigInteger.valueOf(2L));
BigInteger tmp=gnum(mid,n,m,k); if(tmp.compareTo(b)>=0){
r=mid.subtract(BigInteger.ONE);
}
else{
l=mid.add(BigInteger.ONE);
}
}
int[] a = new int[n];
BigInteger M = BigInteger.valueOf((long)(m));
for(int i=0;i<n;++i){
a[i]=l.mod(M).intValue()+1;
l=l.divide(M);
}
for(int i=n-1;i>=0;--i){
System.out.print(a[i]);
if(i>0)System.out.print(" ");
}
System.out.println(); }
public static BigInteger gnum(BigInteger mid,int n,int m,int mod){
BigInteger M = BigInteger.valueOf((long)(m));
int[] a = new int[n];
for(int i=0;i<a.length;++i){
a[i]=mid.mod(M).intValue()+1;
mid=mid.divide(M);
}
BigInteger tmp=BigInteger.ZERO;
int k=0;
for(int i=n-1;i>=0;--i){
for(int j=a[i]-1;j>=1;--j){
tmp=tmp.add(dp[i+1][j][k]);
}
if(i==0){
tmp=tmp.add(dp[i+1][a[i]][k]);
}
k=( (k-a[i])%mod+mod)%mod;
}
return tmp;
} }