1 #include <iostream> | 1 import java.math.BigInteger; 2 #include <sstream> < > 2 3 #include <iomanip> | 3 public class VerySmoothDecompositions 4 #include <vector> < > 4 { 5 #include <string> | 5 public int solve(String[] digits) 6 #include <map> < > 6 { 7 #include <set> | 7 // とりあえずBigIntegerにする 8 #include <algorithm> | 8 String str = ""; 9 #include <numeric> | 9 for(String s : digits) str += s; 10 #include <iterator> | 10 return solve(new BigInteger(str)); 11 #include <functional> < 12 #include <complex> < > 11 } > 12 13 #include <queue> | 13 int solve(BigInteger v) 14 #include <stack> < > 14 { 15 #include <cmath> | 15 // とりあえず普通に素因数分解する 16 #include <cassert> | 16 int[] ps = {2,3,5,7,11,13}; 17 #include <cstring> | 17 int[] fs = {0,0,0,0, 0, 0}; 18 using namespace std; | 18 for(int i=0; i<ps.length; ++i) 19 typedef long long LL; | 19 for(BigInteger p=BigInteger.valueOf(ps[i]); v.remainder(p).equals(BigIn 20 typedef complex<double> CMP; | 20 fs[i]++; > 21 if( !v.equals(BigInteger.ONE) ) > 22 return 0; // 17以上の素因数があったら無理 > 23 return solve(fs[0], fs[1], fs[2], fs[3]); // 11 と 13 はそのまま使うしかないので無視 > 24 } > 25 > 26 // ここからが本題 > 27 int solve(int p2, int p3, int p5, int p7) > 28 { > 29 // dp23[a][b] = 「2がa個、3がb個、あるときに何通り作れるか」 > 30 int P2 = p2+1; > 31 int P3 = p3+1; > 32 int[] dp23 = new int[P2*P3]; dp23[0] = 1; // 0個0個なら1通り > 33 { > 34 // - {2}を作る可能性だけを考えた場合の数 > 35 // - {2,4}を作る可能性だけを考えた場合の数 > 36 // - ... > 37 // - {2,4,8,16,3,9,6,12} を作る可能性を考えた全部の場合の数 > 38 // を、表を更新しながら順に求めていく > 39 int[] k2 = {1,2,3,4,0,0,1,2}; > 40 int[] k3 = {0,0,0,0,1,2,1,1}; > 41 for(int i=0; i<k2.length; ++i) > 42 // 例として {2,4,8,16,3,9} --> {2,4,8,16,3,9,6} の更新を考える > 43 for(int a2=k2[i]; a2<=p2; ++a2) > 44 for(int a3=k3[i]; a3<=p3; ++a3) { > 45 // 「2がa個、3がb個あるときの {2,4,8,16,3,9,6} の作り方パター�盗煤v > 46 // = 「2がa個、3がb個あるときの {2,4,8,16,3,9} の作り方パターン�煤v > 47 // + 「2がa-1個、3がb-1個あるときの {2,4,8,16,3,9,6} の作り方パ�^ーン数」」 > 48 dp23[a2*P3+a3] += dp23[(a2-k2[i])*P3+(a3-k3[i])]; > 49 dp23[a2*P3+a3] %= MODVAL; > 50 } > 51 } > 52 > 53 // さらに 14 を作る場合の数を数える > 54 int[] dp237 = dp23; > 55 { > 56 // 7が無限にあるとすると > 57 // 「2がa個、3がb個あるときの {2,4,8,16,3,9,6,12,14} の作り方パター�盗煤v > 58 // = 「2がa個、3がb個あるときの {2,4,8,16,3,9,6,12} の作り方パターン数」 > 59 // + 「2がa-1個、3がb個あるときの {2,4,8,16,3,9,6,12,14} の作り方パタ�[ン数」」 > 60 // だが... > 61 for(int a2=1; a2<=p2; ++a2) > 62 for(int a3=0; a3<=p3; ++a3) { > 63 dp237[a2*P3+a3] += dp237[(a2-1)*P3+a3]; > 64 dp237[a2*P3+a3] %= MODVAL; > 65 } > 66 > 67 // 7はp7個しかないので、 > 68 // 「2がa個、3がb個、7が無限個あるときの {2,4,8,16,3,9,6,12,14} の作り方パターン数」 > 69 // = 「2がa個、3がb個、7が無限個あるときの {2,4,8,16,3,9,6,12,14} の作り方パターン数」 > 70 // - 「2がa-p7-1個、3がb個、7が無限個あるときの {2,4,8,16,3,9,6,12,14} の作り方パターン数」 > 71 // で補正する > 72 for(int a2=p2; a2-p7-1>=0; --a2) > 73 for(int a3=0; a3<=p3; ++a3) { > 74 dp237[a2*P3+a3] += MODVAL - dp237[(a2-p7-1)*P3+a3]; > 75 dp237[a2*P3+a3] %= MODVAL; > 76 } > 77 } 21 78 22 class VerySmoothDecompositions { public: | 79 // 10の個数と15の個数は全探索 23 int solve(vector <string> digits) | 80 int sum = 0; 24 { < > 81 for(int n10=0; n10<=p2 && n10<=p5; ++n10) > 82 for(int n15=0; n15<=p3 && n10+n15<=p5; ++n15) { > 83 sum += dp237[(p2-n10)*P3+(p3-n15)]; > 84 sum %= MODVAL; 25 } | 85 } 26 }; < > 86 return sum; 27 | 87 } 28 88 > 89 static final int MODVAL = 1000000009; 29 | 90 } 30 // Powered by FileEdit < 31 // Powered by TZTester 1.01 [25-Feb-2003] : <cafelier&naoya_t>-custom < 32 // Powered by CodeProcessor <