SRM684D2M DivFreed2

TopCoder Statistics - Problem Statement

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.

数列の隣り合う全ての要素が

のどちらかを満たす数列の数を で求める．

とする．数列に追加する可能なものを選ぶのでから考えると，より大きい，またはを約数に持たなければ良い．基本的に全て遷移可能として()，後に約数の場所の遷移を無かったことにすれば良い．

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65

ll dp[15][100005];
vector<ll> d[100005];

vector<ll> divisor(ll n) {
  vector<ll> res;
  for(ll i = 2; i*i <= n; i++) {
      if(n % i == 0) {
          res.push_back(i);
          if(i != n/i) res.push_back(n/i);
      }
  }
  return res;
}

class DivFreed2 {
  public:
  int count(int n, int k) {
      memset(dp, 0, sizeof(dp));

      rep(i, k + 1) {
          d[i].clear();
      }

      REP(i, 2, k + 1) {
          vector<ll> ret = divisor(i);
          ret.push_back(1);

          d[i].resize(ret.size());
          rep(j, ret.size()) {
              d[i][j] = ret[j];
          }
      }

      REP(i, 1, k + 1) {
          dp[1][i] = 1;
      }

      REP(i, 1, n) {
          ll sum = 0;
          REP(j, 1, k + 1) {
              sum += dp[i][j];
              sum %= MOD;
          }

          REP(j, 1, k + 1) {
              dp[i+1][j] += sum;
              dp[i+1][j] %= MOD;
          }

          REP(j, 1, k + 1) {
              rep(l, d[j].size()) {
                  dp[i+1][d[j][l]] -= dp[i][j];
              }
          }
      }

      ll ans = 0;
      rep(j, k + 1) {
          ans += dp[n][j];
          ans %= MOD;
      }

      return ans;
  }
};
Mar 15th, 2016
srm, topcoder, 動的計画法