分块 | FFY's Blog

题意

$n$个格子，现在要把它分成若干段相邻的块，要求每块不超过$m$个格子。块数不限。求分法总数对$Q$取模的结果。

题解

首先想到$n^2$ 的做法,我们定义$f[i]$表示划分到$i$时的合法方案的数量,不难想到转移方程:$f[i]= \sum_{j=max(0,i-m)}^{i-1}f[j]$
复杂度是$(0)n^2$
然而数据范围是$10^6$,我们需要继续优化;
观察转移方程我们发现$f[i]$实际上等于一段连续区间的和,我们可以用前缀和来优化DP,这样时间复杂度就降到了$(o)n$,这道题就解决了

#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
const int maxn=1e6+10;
int t,n,m,mod;
ll f[maxn],s[maxn];
int main()
{
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d%d",&n,&m,&mod);
        memset(f,0,sizeof f);
        f[0]=1;s[0]=1;
        for(int i=1;i<=n;i++)
        {
            if(!(i-m))f[i]=s[i-1];
            else f[i]=(s[i-1]-s[i-m-1])%mod;//记得取模
            s[i]=(s[i-1]+f[i]);
//            for(int j=max(0,i-m);j<i;j++)
//            f[i]+=f[j];
        }
        printf("%lld\n",f[n]);
    }
    return 0;
}