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

Coin partitions 题号:78 难度: 30 中英对照

Let p(n) represent the number of different ways in which n coins can be separated into piles. For example, five coins can be separated into piles in exactly seven different ways, so p(5)=7.

OOOOO
OOOO   O
OOO   OO
OOO   O   O
OO   OO   O
OO   O   O   O
O   O   O   O   O

Find the least value of n for which p(n) is divisible by one million.


Solution

题目可变形为:将数字$x$拆分为无序的正整数的和的方案数即可。 采用动态规划,设$dp[x]$表示将数字$x$拆分为无序的正整数的和的方案数,那么对所有的数$i$,可以对所有$j(j \geq i)$产生$dp[j-i]$的贡献。 需要注意答案可能很大,但我们只关心末尾的$6$位,所以将答案每次模上$1000000$,最后判断答案是否为$0$即可。

Code



public final class p78 {
    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 int dp[]=new int[60000];
    static public String run(){
    	dp[0]=1;
    	for(int i=0;i<dp.length;i++){
    		for(int j=i;j<dp.length;j++){
    			dp[j]+=dp[j-i];
    			dp[j]%=1000000;
    		}
    	}
    	for(int i=0;i<dp.length;i++)
    		if(dp[i]==0) return ""+i;
    	return null;
	}
    
    
    
    
	
}
55374
9728ms