H - Count Multiset 解説 by penguinman
サイズ \(k\) の多重集合 \(A\) の個数を数える代わりに、長さ \(k\) の単調非減少正整数列 \(A'=(A'_1,A'_2,\ldots,A'_k)\) の個数を数えることを考えます。
さらにこのままでは見通しが悪いので、差分を取った数列、すなわち以下の漸化式で表される長さ \(k\) の数列 \(B=(B_1,B_2,\ldots,B_k)\) の個数を数えることを考えます。
- \(B_1=A'_1\)
- \(B_i=A'_i-A'_{i-1}\ (2 \leq i \leq k)\)
するとこの問題は以下のように言い換えることが可能です。
\(k=1,2,\ldots,N\) について、以下の \(3\) つの条件をすべて満たす非負整数列 \(B=(B_1,B_2,\ldots,B_k)\) の個数を数えよ。
- \(\sum_{i=1}^{k} B_i \times (k-i-1) = N\)
- \(0\) が \(M\) 個以上連続する箇所が存在しない。すなわち \(B_i=B_{i+1}=\cdots=B_{i+M-1}=0\) となるような整数 \(i\) が存在しない。
- \(B_1\) は正
ここで \(B\) の添字を反転させます。すると上記の言い換えは以下のようになります。
\(k=1,2,\ldots,N\) について、以下の \(3\) つの条件をすべて満たす非負整数列 \(B=(B_1,B_2,\ldots,B_k)\) の個数を数えよ。
- \(\sum_{i=1}^{k} B_i \times i = N\)
- \(0\) が \(M\) 個以上連続する箇所が存在しない。すなわち \(B_i=B_{i+1}=\cdots=B_{i+M-1}=0\) となるような整数 \(i\) が存在しない。
- \(B_k\) は正
これでかなり見通しが良くなりました。
\(0 \leq x,y \leq N\) を満たす整数対 \((x,y)\) について、\(f(x,y)\) を以下のように定めます。
- 以下の \(3\) つの条件をすべて満たす非負整数列 \(B=(B_1,B_2,\ldots,B_x)\) の個数
- \(\sum_{i=1}^{x} B_i \times i = y\)
- \(0\) が \(M\) 個以上連続する箇所が存在しない。すなわち \(B_i=B_{i+1}=\cdots=B_{i+M-1}=0\) となるような整数 \(i\) が存在しない。
- \(B_x\) は正
\(f(x,y)\) は \(p \leq x\) および \(q \leq y\) を満たす \(f(p,q)\) の集合を用いて再帰的に計算することが可能であるため、動的計画法による求値が可能であり、愚直に求めた場合の計算量は \(O(N^3M)\) となります。しかしここで累積和等を用いて工夫しながらの計算をすると、その計算量を \(O(N^2)\) まで落とすことが可能です。
よってこの問題を解くことができました。
実装例 (C++)
#include<bits/stdc++.h>
using namespace std;
const int mod = 998244353;
int main(){
int N,M; cin >> N >> M;
vector<vector<int>> dp(N+1,vector<int>(N+1));
dp[0][0] = 1;
vector<int> sum(N+1);
sum[0] = 1;
for(int i=1; i<=N; i++){
for(int j=i; j<=N; j++){
dp[i][j] = sum[j-i]+dp[i][j-i];
dp[i][j] %= mod;
}
for(int j=0; j<=N; j++){
sum[j] += dp[i][j];
sum[j] %= mod;
if(M <= i){
sum[j] -= dp[i-M][j];
sum[j] %= mod;
}
}
}
for(int i=1; i<=N; i++){
int ans = dp[i][N];
if(ans < 0) ans += mod;
cout << ans << endl;
}
}
投稿日時:
最終更新: