d78029fb4b 2011-09-21 kinaba: import java.math.BigInteger; d78029fb4b 2011-09-21 kinaba: d78029fb4b 2011-09-21 kinaba: public class VerySmoothDecompositions d78029fb4b 2011-09-21 kinaba: { d78029fb4b 2011-09-21 kinaba: public int solve(String[] digits) d78029fb4b 2011-09-21 kinaba: { d78029fb4b 2011-09-21 kinaba: // とりあえずBigIntegerにする d78029fb4b 2011-09-21 kinaba: String str = ""; d78029fb4b 2011-09-21 kinaba: for(String s : digits) str += s; d78029fb4b 2011-09-21 kinaba: return solve(new BigInteger(str)); d78029fb4b 2011-09-21 kinaba: } d78029fb4b 2011-09-21 kinaba: d78029fb4b 2011-09-21 kinaba: int solve(BigInteger v) d78029fb4b 2011-09-21 kinaba: { d78029fb4b 2011-09-21 kinaba: // とりあえず普通に素因数分解する d78029fb4b 2011-09-21 kinaba: int[] ps = {2,3,5,7,11,13}; d78029fb4b 2011-09-21 kinaba: int[] fs = {0,0,0,0, 0, 0}; d78029fb4b 2011-09-21 kinaba: for(int i=0; i<ps.length; ++i) d78029fb4b 2011-09-21 kinaba: for(BigInteger p=BigInteger.valueOf(ps[i]); v.remainder(p).equals(BigInteger.ZERO); v=v.divide(p)) d78029fb4b 2011-09-21 kinaba: fs[i]++; d78029fb4b 2011-09-21 kinaba: if( !v.equals(BigInteger.ONE) ) d78029fb4b 2011-09-21 kinaba: return 0; // 17以上の素因数があったら無理 d78029fb4b 2011-09-21 kinaba: return solve(fs[0], fs[1], fs[2], fs[3]); // 11 と 13 はそのまま使うしかないので無視 d78029fb4b 2011-09-21 kinaba: } d78029fb4b 2011-09-21 kinaba: d78029fb4b 2011-09-21 kinaba: // ここからが本題 d78029fb4b 2011-09-21 kinaba: int solve(int p2, int p3, int p5, int p7) d78029fb4b 2011-09-21 kinaba: { d78029fb4b 2011-09-21 kinaba: // dp23[a][b] = 「2がa個、3がb個、あるときに何通り作れるか」 d78029fb4b 2011-09-21 kinaba: int P2 = p2+1; d78029fb4b 2011-09-21 kinaba: int P3 = p3+1; d78029fb4b 2011-09-21 kinaba: int[] dp23 = new int[P2*P3]; dp23[0] = 1; // 0個0個なら1通り d78029fb4b 2011-09-21 kinaba: { d78029fb4b 2011-09-21 kinaba: // - {2}を作る可能性だけを考えた場合の数 d78029fb4b 2011-09-21 kinaba: // - {2,4}を作る可能性だけを考えた場合の数 d78029fb4b 2011-09-21 kinaba: // - ... d78029fb4b 2011-09-21 kinaba: // - {2,4,8,16,3,9,6,12} を作る可能性を考えた全部の場合の数 d78029fb4b 2011-09-21 kinaba: // を、表を更新しながら順に求めていく d78029fb4b 2011-09-21 kinaba: int[] k2 = {1,2,3,4,0,0,1,2}; d78029fb4b 2011-09-21 kinaba: int[] k3 = {0,0,0,0,1,2,1,1}; d78029fb4b 2011-09-21 kinaba: for(int i=0; i<k2.length; ++i) d78029fb4b 2011-09-21 kinaba: // 例として {2,4,8,16,3,9} --> {2,4,8,16,3,9,6} の更新を考える d78029fb4b 2011-09-21 kinaba: for(int a2=k2[i]; a2<=p2; ++a2) d78029fb4b 2011-09-21 kinaba: for(int a3=k3[i]; a3<=p3; ++a3) { d78029fb4b 2011-09-21 kinaba: // 「2がa個、3がb個あるときの {2,4,8,16,3,9,6} の作り方パターン数」 d78029fb4b 2011-09-21 kinaba: // = 「2がa個、3がb個あるときの {2,4,8,16,3,9} の作り方パターン数」 d78029fb4b 2011-09-21 kinaba: // + 「2がa-1個、3がb-1個あるときの {2,4,8,16,3,9,6} の作り方パターン数」」 d78029fb4b 2011-09-21 kinaba: dp23[a2*P3+a3] += dp23[(a2-k2[i])*P3+(a3-k3[i])]; d78029fb4b 2011-09-21 kinaba: dp23[a2*P3+a3] %= MODVAL; d78029fb4b 2011-09-21 kinaba: } d78029fb4b 2011-09-21 kinaba: } d78029fb4b 2011-09-21 kinaba: d78029fb4b 2011-09-21 kinaba: // さらに 14 を作る場合の数を数える d78029fb4b 2011-09-21 kinaba: int[] dp237 = dp23; d78029fb4b 2011-09-21 kinaba: { d78029fb4b 2011-09-21 kinaba: // 7が無限にあるとすると d78029fb4b 2011-09-21 kinaba: // 「2がa個、3がb個あるときの {2,4,8,16,3,9,6,12,14} の作り方パターン数」 d78029fb4b 2011-09-21 kinaba: // = 「2がa個、3がb個あるときの {2,4,8,16,3,9,6,12} の作り方パターン数」 d78029fb4b 2011-09-21 kinaba: // + 「2がa-1個、3がb個あるときの {2,4,8,16,3,9,6,12,14} の作り方パターン数」」 d78029fb4b 2011-09-21 kinaba: // だが... d78029fb4b 2011-09-21 kinaba: for(int a2=1; a2<=p2; ++a2) d78029fb4b 2011-09-21 kinaba: for(int a3=0; a3<=p3; ++a3) { d78029fb4b 2011-09-21 kinaba: dp237[a2*P3+a3] += dp237[(a2-1)*P3+a3]; d78029fb4b 2011-09-21 kinaba: dp237[a2*P3+a3] %= MODVAL; d78029fb4b 2011-09-21 kinaba: } d78029fb4b 2011-09-21 kinaba: d78029fb4b 2011-09-21 kinaba: // 7はp7個しかないので、 d78029fb4b 2011-09-21 kinaba: // 「2がa個、3がb個、7が無限個あるときの {2,4,8,16,3,9,6,12,14} の作り方パターン数」 d78029fb4b 2011-09-21 kinaba: // = 「2がa個、3がb個、7が無限個あるときの {2,4,8,16,3,9,6,12,14} の作り方パターン数」 d78029fb4b 2011-09-21 kinaba: // - 「2がa-p7-1個、3がb個、7が無限個あるときの {2,4,8,16,3,9,6,12,14} の作り方パターン数」 d78029fb4b 2011-09-21 kinaba: // で補正する d78029fb4b 2011-09-21 kinaba: for(int a2=p2; a2-p7-1>=0; --a2) d78029fb4b 2011-09-21 kinaba: for(int a3=0; a3<=p3; ++a3) { d78029fb4b 2011-09-21 kinaba: dp237[a2*P3+a3] += MODVAL - dp237[(a2-p7-1)*P3+a3]; d78029fb4b 2011-09-21 kinaba: dp237[a2*P3+a3] %= MODVAL; d78029fb4b 2011-09-21 kinaba: } d78029fb4b 2011-09-21 kinaba: } 28a087506a 2011-09-21 kinaba: d78029fb4b 2011-09-21 kinaba: // 10の個数と15の個数は全探索 d78029fb4b 2011-09-21 kinaba: int sum = 0; d78029fb4b 2011-09-21 kinaba: for(int n10=0; n10<=p2 && n10<=p5; ++n10) d78029fb4b 2011-09-21 kinaba: for(int n15=0; n15<=p3 && n10+n15<=p5; ++n15) { d78029fb4b 2011-09-21 kinaba: sum += dp237[(p2-n10)*P3+(p3-n15)]; d78029fb4b 2011-09-21 kinaba: sum %= MODVAL; d78029fb4b 2011-09-21 kinaba: } d78029fb4b 2011-09-21 kinaba: return sum; d78029fb4b 2011-09-21 kinaba: } 28a087506a 2011-09-21 kinaba: d78029fb4b 2011-09-21 kinaba: static final int MODVAL = 1000000009; d78029fb4b 2011-09-21 kinaba: }