• branch=trunk inherited from [9165bd3629]
• sym-trunk inherited from [9165bd3629]

Modified SRM/519/1C.java from [7e698666b34915d4] to [805872cfb459b818].

     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  +}