T1: k的幂分拆
本题难度中等，完全背包模板题，以 \(k\) 的幂作为物品大小
记 dp[i][j] 表示使用若干个 \(k^0 \sim k^i\)，相加恰好为 \(j\) 的方案数
转移：
\( dp[i][j] = dp[i-1][j] + dp[i][j-k^i] \)
假设 \(n\) 是满足 \(k^n \leqslant m\) 的最大值，时间复杂度就是 \(O(nm)\)
这里 \(n \leqslant 20\)
代码实现
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
//const int mod = 998244353;
const int mod = 1000000007;
struct mint {
ll x;
mint(ll x=0):x((x%mod+mod)%mod) {}
mint operator-() const {
return mint(-x);
}
mint& operator+=(const mint a) {
if ((x += a.x) >= mod) x -= mod;
return *this;
}
mint& operator-=(const mint a) {
if ((x += mod-a.x) >= mod) x -= mod;
return *this;
}
mint& operator*=(const mint a) {
(x *= a.x) %= mod;
return *this;
}
mint operator+(const mint a) const {
return mint(*this) += a;
}
mint operator-(const mint a) const {
return mint(*this) -= a;
}
mint operator*(const mint a) const {
return mint(*this) *= a;
}
mint pow(ll t) const {
if (!t) return 1;
mint a = pow(t>>1);
a *= a;
if (t&1) a *= *this;
return a;
}
// for prime mod
mint inv() const {
return pow(mod-2);
}
mint& operator/=(const mint a) {
return *this *= a.inv();
}
mint operator/(const mint a) const {
return mint(*this) /= a;
}
};
istream& operator>>(istream& is, mint& a) {
return is >> a.x;
}
ostream& operator<<(ostream& os, const mint& a) {
return os << a.x;
}
int p[20];
mint dp[100005];
int main() {
int m, k;
cin >> m >> k;
int n = 0;
p[n] = 1;
while (p[n]*k <= m) {
p[n+1] = p[n]*k;
++n;
}
dp[0] = 1;
rep(i, n+1) {
for (int j = p[i]; j <= m; ++j) {
dp[j] += dp[j-p[i]];
}
}
cout << dp[m] << '\n';
return 0;
}