当前位置:首页 » Project Euler » 详细页

Investigating numbers with few repeated digits 题号:172 难度: 55 中英对照

How many 18-digit numbers n (without leading zeros) are there such that no digit occurs more than three times in n?

Solution

数位动态规划。 用bits表示当前10个数字的使用情况(用连续的2个二进制位来表示使用了0、1、2、3这四种状态)。 用pos表示当前枚举的位数,从高位往低位枚举。 需要使用一个二维数组来储存所有的pos和bits对应的答案以实现记忆化。

Code


public final class p172 {
    public static void main(String[] args) {
        long start=System.nanoTime();
        String result = run();        
        long end=System.nanoTime();
        System.out.println(result);
        System.out.println( (end-start)/1000000 + "ms" );
    }

	
    static public String run() {
    	for(int i=0;i<ans.length;i++) for(int j=0;j<ans[i].length;j++)
    		ans[i][j]=-1;
    	return ""+get(0,0);
    }

	static long ans[][] = new long[18][1 << 20];
	
	public static long get(int bits, int pos) {
		if (pos == 18) return 1;
		if (ans[pos][bits]>=0) return ans[pos][bits];//记忆化
		long sum = 0;
		for (int d=pos==0?1:0; d <= 9; d++)//如果不是首位,则可以从0开始,首位要避免前导零
			if (((bits >> (d + d)) & 3) != 3)
				sum += get(bits + (1 << (d + d)), pos + 1);
		return ans[pos][bits]=sum;
	}
}
227485267000992000
350ms