题解 CF431C 【k-Tree】

览遍千秋 · 2020-02-23 22:09:54 · 题解

问题描述

CF413C

LG-CF413C

题解

求有多少权值为 n ，路径中有边权不小于 d 的 → 所有权值为 n 的路径总数-所有边权均小于 d 。

设 f(i) 代表权值为 i 的路径总数 ， f(x)=\sum\limits_{i=x-k}^{x-1}{f(i)} 。

设 g(i) 代表权值为 i ，且路径中边权均小于 d ， g(x)=\sum\limits_{i=x-d+1}^{x-1}{g(i)} 。

答案为 f(n)-g(n) 。

\mathrm{Code}

#include<bits/stdc++.h>
using namespace std;

#define int long long

template <typename Tp>
void read(Tp &x){
    x=0;char ch=1;int fh=1;
    while(ch!='-'&&(ch>'9'||ch<'0')) ch=getchar();
    if(ch=='-') fh=-1,ch=getchar();
    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    x*=fh;
}

const int maxn=107;
const int mod=1000000007;

int f[maxn],g[maxn];
int n,d,k;

void Init(void){
    read(n);read(k);read(d);
}

void Work(void){
    f[0]=g[0]=1ll;
    for(int i=1;i<=n;i++){
        int st=max(0ll,i-k);
        for(int j=st;j<i;j++) f[i]=(f[i]+f[j])%mod;
        st=max(0ll,i-d+1);
        for(int j=st;j<i;j++) g[i]=(g[i]+g[j])%mod;
    }
    printf("%lld\n",((f[n]-g[n])%mod+mod)%mod);
}

signed main(){
    Init();
    Work();
    return 0;
}