[ABC132F] Small Products 题解

标签：lfloor cnt frac int 题解 rfloor Products Small dp

题意

一句话题意不用再翻译了吧。

思路

先考虑朴素的 dp，设 \(dp_{i,j}\) 表示长度为 \(i\) 结尾数字为 \(j\) 的序列的方案数，状态很好转移：

\[dp_{i,j}=\sum_{a=1}^{\lfloor \frac{N}{j} \rfloor}dp_{i-1,a} \]

这样时间复杂度是 \(\Theta(nk)\) 的，显然过不了。

考虑优化这个 dp。
我们发现 \(\lfloor \frac{N}{j} \rfloor\) 在一段区间内的值是一样的，自然想到整除分块。
我们预处理出每一块的 \(\lfloor \frac{N}{j} \rfloor\) 值 \(m_i\)、长度 \(len_i\) 和块的个数 \(cnt\)，这时的状态转移如下：

\[dp_{i,j}=\sum_{j=1}^{cnt}dp_{i,j-1}+dp_{i-1,cnt-j+1}\times len_{j} \]

这里状态中的 \(j\) 表示第 \(j\) 块。

时间复杂度 \(\Theta(\sqrt{n}k)\)。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod=1e9+7;
int n,m;
int dp[105][100005];
int a[100005],len[100005],cnt;
signed main(){
    scanf("%lld%lld",&n,&m);
    for(int l=1,r;l<=n;l=r+1){
        r=(n/(n/l));
        a[++cnt]=r;
        len[cnt]=r-l+1;
    }
    for(int i=1;i<=cnt;i++) dp[0][i]=1;
    for(int i=1;i<=m;i++){
        int d=cnt;
        for(int j=1;j<=cnt;j++){
            dp[i][j]=(dp[i][j-1]+len[j]*dp[i-1][d--]%mod)%mod;
        }
    }
    printf("%lld",dp[m][cnt]);
    return 0;
}

标签：lfloor,cnt,frac,int,题解,rfloor,Products,Small,dp
From： https://www.cnblogs.com/PerchLootie/p/18371166