Codeforces - 474D - Flowers - 构造

https://codeforces.com/problemset/problem/474/D

这道题挺好的，思路是这样。

我们要找一个01串，其中0的段要被划分为若干个连续k的0。

我们设想一个长度为n的合法串是怎么被构造出来的，要么是上一个合法串后面直接连接1，要么是上一个合法串后面连接k个连续的0，那么每个0一一对应于一段连续的0。

所以dp[i]=dp[i-1]+dp[i-k]。

想出来就觉得不难了。

#include<bits/stdc++.h>

using namespace std;

#define ll long long

int t,k;

int a,b;

int dp[];

int sum[];

int main(){

    scanf("%d%d",&t,&k);

    for(int i=;i<=k-;i++){

        dp[i]=;

    }

    dp[k]=;

    for(int i=k+;i<=;i++){

        dp[i]=(dp[i-]+dp[i-k])%;

    }

    for(int i=;i<=;i++){

        sum[i]=(sum[i-]+dp[i])%;

    }

    for(int i=;i<t;i++){

        scanf("%d%d",&a,&b);

        printf("%d\n",(sum[b]-sum[a-]+)%);

    }

}

巴特西

Codeforces - 474D - Flowers - 构造 - 简单dp

最新文章

热门文章