#include <bits/stdc++.h>
using namespace std;
const int N = 100010, mod = 5000011;
int f[N];
int main()
{
    int n, k, x = 0, tmp = 1;
    cin >> n >> k;
    f[0] = 1;
    for (int i = 1; i <= n; i += 1)
    {
        (f[i] += tmp) %= mod;
        if (i - k > 0)
        {
            (tmp += f[i - k]) %= mod;
        }
    }
    for (int i = 0; i <= n; i += 1)
    {
        (x += f[i]) %= mod;
    }
    cout << x << endl;
    return 0;
}

代码

# include <bits/stdc++.h>

using namespace std ;

const int N = 100010 , mod = 5000011 ;

int f [ N ] ;

int main ( )

{

    int n , k , x = 0 , tmp = 1 ;

    cin >> n >> k ;

    f [ 0 ] = 1 ;

    for ( int i = 1 ; i <= n ; i += 1 )

    {

        ( f [ i ] += tmp ) %= mod ;

        if ( i - k > 0 )

        {

            ( tmp += f [ i - k ] ) %= mod ;

        }

    }

    for ( int i = 0 ; i <= n ; i += 1 )

    {

        ( x += f [ i ] ) %= mod ;

    }

    cout << x << endl ;

    return 0 ;
    
}

本题属于动态规划