计算使用长度为 1,2,3,4,......m 的步长到达第 N 步的方法数。（其中 m<=n）

Question

我得到了一个顺序为 10⁵ 的数字 n。我必须找到使用长度 1 or 2 or 3 or.....or m 的步长从地面到达第 n^th 步的方法，这里 m<=n.

因为答案可能太大输出它取模 10⁹+7.

#include<iostream.h>
using namespace std;

#define ll long long
#define MOD 1000000007

ll countWays_(ll n, ll m){
    ll res[n];
    res[0] = 1; res[1] = 1;
    for (ll i=2; i<n; i++)
    {
       res[i] = 0;
       for (ll j=1; j<=m && j<=i; j++)
         res[i] =(res[i]%MOD+ res[i-j]%MOD)%MOD;
    }
    return res[n-1];
}

ll countWays(ll s, ll m){
    return countWays_(s+1, m);
}
int main (){
    scanf("%lld%lld",&s,&m);
    printf("%lld\n",countWays(s,m));
    return 0;
}

由于复杂度O(m*n)，我想降低它。

Answer 1

您的内部循环将 res[i-1] + res[i-2] + ... + res[i-m] 添加到结果中。

设s为res中前i个元素的总和。然后，您只需将 s[i-1] - s[i-m-1] 添加到结果中即可。

ll countWays_(ll n, ll m){
    ll res[n];
    res[0] = 1; res[1] = 1;
    s[0] = 1; s[1] = 2;
    for (ll i=2; i<n; i++)
    {
       if (i <= m)
           res[i] = s[i-1] % MOD;
       else
           res[i] = (s[i-1] - s[i - m - 1] + MOD) % MOD; 
       s[i] = (s[i-1] + res[i]) % MOD;
    }
    return res[n-1];
}

新的复杂度将为 O(n)。您甚至可以将 s 作为数组去掉，并使用单个变量并进行更多记账。

Answer 2

我认为可以使用变量 Sum 来存储 i-m+1 的 res 和，如下所示：

ll mod(ll a, ll b){ 
    return (a%b+b)%b; 
}
ll countWays_(ll n, ll m){
    ll res[n],sum;
    res[0] = 1; res[1] = 1;
    sum = res[0] + res[1];
    int head_sum = 0;
    for (ll i=2; i<n; i++)
    {
       if ((i - head_sum) > m) {
            sum=mod((sum- res[head_sum]),MOD);
            head_sum++;
       }  
       res[i] = sum;
       sum = mod((sum% MOD + res[i]% MOD),MOD);
    }
    return res[n-1];
}

计算使用长度为 1,2,3,4,......m 的步长到达第 N 步的方法数。（其中 m<=n）

Count Number of ways to reach Nth step using steps of lengths 1,2,3,4,......m.(where m<=n)

c++

algorithm

combinations

permutation

combinatorics