1 -#include <iostream> 2 -#include <sstream> 3 -#include <iomanip> 4 -#include <vector> 5 -#include <string> 6 -#include <map> 7 -#include <set> 8 -#include <algorithm> 9 -#include <numeric> 10 -#include <iterator> 11 -#include <functional> 12 -#include <complex> 13 -#include <queue> 14 -#include <stack> 15 -#include <cmath> 16 -#include <cassert> 17 -#include <cstring> 18 -using namespace std; 19 -typedef long long LL; 20 -typedef complex<double> CMP; 1 +import java.math.BigInteger; 2 + 3 +public class VerySmoothDecompositions 4 +{ 5 + public int solve(String[] digits) 6 + { 7 + // とりあえずBigIntegerにする 8 + String str = ""; 9 + for(String s : digits) str += s; 10 + return solve(new BigInteger(str)); 11 + } 12 + 13 + int solve(BigInteger v) 14 + { 15 + // とりあえず普通に素因数分解する 16 + int[] ps = {2,3,5,7,11,13}; 17 + int[] fs = {0,0,0,0, 0, 0}; 18 + for(int i=0; i<ps.length; ++i) 19 + for(BigInteger p=BigInteger.valueOf(ps[i]); v.remainder(p).equals(BigInteger.ZERO); v=v.divide(p)) 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} の作り方パターン数」 46 + // = 「2がa個、3がb個あるときの {2,4,8,16,3,9} の作り方パターン数」 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} の作り方パターン数」 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: 23 - int solve(vector <string> digits) 24 - { 25 - } 26 -}; 27 - 79 + // 10の個数と15の個数は全探索 80 + int sum = 0; 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; 85 + } 86 + return sum; 87 + } 28 88 29 - 30 -// Powered by FileEdit 31 -// Powered by TZTester 1.01 [25-Feb-2003] : <cafelier&naoya_t>-custom 32 -// Powered by CodeProcessor 89 + static final int MODVAL = 1000000009; 90 +}