Index: SRM/519/1C.java
==================================================================
--- SRM/519/1C.java
+++ SRM/519/1C.java
@@ -1,32 +1,90 @@
-#include <iostream>
-#include <sstream>
-#include <iomanip>
-#include <vector>
-#include <string>
-#include <map>
-#include <set>
-#include <algorithm>
-#include <numeric>
-#include <iterator>
-#include <functional>
-#include <complex>
-#include <queue>
-#include <stack>
-#include <cmath>
-#include <cassert>
-#include <cstring>
-using namespace std;
-typedef long long LL;
-typedef complex<double> CMP;
+import java.math.BigInteger;
+
+public class VerySmoothDecompositions
+{
+   public int solve(String[] digits)
+   {
+      // とりあえずBigIntegerにする
+      String str = "";
+      for(String s : digits) str += s;
+      return solve(new BigInteger(str));
+   }
+   
+   int solve(BigInteger v)
+   {
+      // とりあえず普通に素因数分解する
+      int[] ps = {2,3,5,7,11,13};
+      int[] fs = {0,0,0,0, 0, 0};
+      for(int i=0; i<ps.length; ++i)
+         for(BigInteger p=BigInteger.valueOf(ps[i]); v.remainder(p).equals(BigInteger.ZERO); v=v.divide(p))
+            fs[i]++;
+      if( !v.equals(BigInteger.ONE) )
+         return 0; // 17以上の素因数があったら無理
+      return solve(fs[0], fs[1], fs[2], fs[3]); // 11 と 13 はそのまま使うしかないので無視
+   }
+
+   // ここからが本題   
+   int solve(int p2, int p3, int p5, int p7)
+   {
+       // dp23[a][b] = 「2がa個、3がb個、あるときに何通り作れるか」
+       int P2 = p2+1;
+       int P3 = p3+1;
+       int[] dp23 = new int[P2*P3]; dp23[0] = 1; // 0個0個なら1通り
+       {
+          // - {2}を作る可能性だけを考えた場合の数
+          // - {2,4}を作る可能性だけを考えた場合の数
+          // - ...
+          // - {2,4,8,16,3,9,6,12} を作る可能性を考えた全部の場合の数
+          // を、表を更新しながら順に求めていく
+          int[] k2 = {1,2,3,4,0,0,1,2};
+          int[] k3 = {0,0,0,0,1,2,1,1};
+          for(int i=0; i<k2.length; ++i)
+             // 例として {2,4,8,16,3,9} --> {2,4,8,16,3,9,6} の更新を考える
+             for(int a2=k2[i]; a2<=p2; ++a2)
+             for(int a3=k3[i]; a3<=p3; ++a3) {
+                //   「2がa個、3がb個あるときの {2,4,8,16,3,9,6} の作り方パターン数」
+                // = 「2がa個、3がb個あるときの {2,4,8,16,3,9} の作り方パターン数」
+                // + 「2がa-1個、3がb-1個あるときの {2,4,8,16,3,9,6} の作り方パターン数」」
+                dp23[a2*P3+a3] += dp23[(a2-k2[i])*P3+(a3-k3[i])];
+                dp23[a2*P3+a3] %= MODVAL;
+             }
+       }
+
+       // さらに 14 を作る場合の数を数える
+       int[] dp237 = dp23;
+       {
+          // 7が無限にあるとすると
+          //   「2がa個、3がb個あるときの {2,4,8,16,3,9,6,12,14} の作り方パターン数」
+          // = 「2がa個、3がb個あるときの {2,4,8,16,3,9,6,12} の作り方パターン数」
+          // + 「2がa-1個、3がb個あるときの {2,4,8,16,3,9,6,12,14} の作り方パターン数」」
+          // だが...
+          for(int a2=1; a2<=p2; ++a2)
+          for(int a3=0; a3<=p3; ++a3) {
+             dp237[a2*P3+a3] += dp237[(a2-1)*P3+a3];
+             dp237[a2*P3+a3] %= MODVAL;
+          }
+
+          // 7はp7個しかないので、
+          //   「2がa個、3がb個、7が無限個あるときの {2,4,8,16,3,9,6,12,14} の作り方パターン数」
+          // = 「2がa個、3がb個、7が無限個あるときの {2,4,8,16,3,9,6,12,14} の作り方パターン数」
+          // - 「2がa-p7-1個、3がb個、7が無限個あるときの {2,4,8,16,3,9,6,12,14} の作り方パターン数」
+          // で補正する
+          for(int a2=p2; a2-p7-1>=0; --a2)
+          for(int a3=0; a3<=p3; ++a3) {
+             dp237[a2*P3+a3] += MODVAL - dp237[(a2-p7-1)*P3+a3];
+             dp237[a2*P3+a3] %= MODVAL;
+          }
+       }
 
-class VerySmoothDecompositions { public:
-	int solve(vector <string> digits)
-	{
-	}
-};
-
+       // 10の個数と15の個数は全探索
+       int sum = 0;
+       for(int n10=0; n10<=p2 && n10<=p5; ++n10)
+       for(int n15=0; n15<=p3 && n10+n15<=p5; ++n15) {
+          sum += dp237[(p2-n10)*P3+(p3-n15)];
+          sum %= MODVAL;
+       }
+       return sum;
+   }
 
-
-// Powered by FileEdit
-// Powered by TZTester 1.01 [25-Feb-2003] : <cafelier&naoya_t>-custom
-// Powered by CodeProcessor
+   static final int MODVAL = 1000000009;
+}