こういう風にルートが出てくるの、こどふぉだとよく見るね。
ありがちなのが、長さ の線分を整数長ごとに分割するとき、分割の中に登場する長さの種類は 通りしかないとか、そういう形でよく出てくる。
問題概要
整数 が与えれる。
長さ の正の整数列であって、どの隣り合う二要素の積も 以下であるようなものの個数を、1000000007 で割ったあまりをもとめよ。
制約
考えたこと
すごくシンプルで好きな問題!!!!!
そしていかにもルートが出て来そうな雰囲気をもった問題。具体的には例えば だと
- 1
- 2
- 3
- 4
- 5, 6
- 7, 8
- 9, 10, 11, 12
- 13〜24
という風に本質的に 8 種類の数値だけを考えればよいことがわかったりする。そのこころは、例えば
- 7 も 8 もその次に来れる整数の最大値は 3 で変わらない
という感じ。おおむね あたりを境に様相が前後で変わっていて、前半の上から順と、後半の下から順とがペアになっているイメージである。より正確には、上から順にレイヤー という風に分けたとき
- レイヤー の次にこれる数はレイヤー 未満の数である
という風になっている。よってレイヤーの個数は概ね 個になっている ( 個の場合もあることに注意)
DP へ
上記のようなレイヤー分けができたならば、各レイヤー j に含まれる数値の種類数を num[ j ] とすると、
- dp[ i ][ j ] := 長さ i の正数列であって、最後尾のレイヤーが j であるものの個数
として
- dp[ i + 1 ][ j ] = ( dp[ i ][ k ]) × num[ j ]
として計算できる。このままだと の計算量になってしまうが、DP を累積和を用いて高速化することで の計算量になる。
#include <iostream> #include <vector> #include <cstring> using namespace std; // modint: mod 計算を int を扱うように扱える構造体 template<int MOD> struct Fp { long long val; constexpr Fp(long long v = 0) noexcept : val(v % MOD) { if (val < 0) v += MOD; } constexpr int getmod() { return MOD; } constexpr Fp operator - () const noexcept { return val ? MOD - val : 0; } constexpr Fp operator + (const Fp& r) const noexcept { return Fp(*this) += r; } constexpr Fp operator - (const Fp& r) const noexcept { return Fp(*this) -= r; } constexpr Fp operator * (const Fp& r) const noexcept { return Fp(*this) *= r; } constexpr Fp operator / (const Fp& r) const noexcept { return Fp(*this) /= r; } constexpr Fp& operator += (const Fp& r) noexcept { val += r.val; if (val >= MOD) val -= MOD; return *this; } constexpr Fp& operator -= (const Fp& r) noexcept { val -= r.val; if (val < 0) val += MOD; return *this; } constexpr Fp& operator *= (const Fp& r) noexcept { val = val * r.val % MOD; return *this; } constexpr Fp& operator /= (const Fp& r) noexcept { long long a = r.val, b = MOD, u = 1, v = 0; while (b) { long long t = a / b; a -= t * b; swap(a, b); u -= t * v; swap(u, v); } val = val * u % MOD; if (val < 0) val += MOD; return *this; } constexpr bool operator == (const Fp& r) const noexcept { return this->val == r.val; } constexpr bool operator != (const Fp& r) const noexcept { return this->val != r.val; } friend constexpr ostream& operator << (ostream &os, const Fp<MOD>& x) noexcept { return os << x.val; } friend constexpr istream& operator >> (istream &is, Fp<MOD>& x) noexcept { return is >> x.val; } friend constexpr Fp<MOD> modpow(const Fp<MOD> &a, long long n) noexcept { if (n == 0) return 1; auto t = modpow(a, n / 2); t = t * t; if (n & 1) t = t * a; return t; } }; const int MOD = 1000000007; using mint = Fp<MOD>; long long N, K; mint dp[110][111000]; mint sdp[111000]; long long num[111000]; mint solve() { // 各レイヤーの数値の個数 int iter = 0; for (int i = 1; i <= N;) { int j = N / i; if (i <= j) num[iter++] = 1, ++i; // 前半 else num[iter++] = N/j - i + 1, i = N/j + 1; // 後半 } // DP memset(dp, 0, sizeof(dp)); dp[0][0] = 1; for (int k = 0; k < K; ++k) { memset(sdp, 0, sizeof(sdp)); for (int j = 0; j <= iter; ++j) sdp[j+1] = sdp[j] + dp[k][j]; for (int j = 0; j < iter; ++j) dp[k+1][j] = sdp[iter - j] * mint(num[j]); } // 集計 mint res = 0; for (int j = 0; j <= iter; ++j) res += dp[K][j]; return res; } int main() { cin >> N >> K; cout << solve() << endl; }