4

I'm given a number n of order 105. I've to find number of ways to reach nth step from ground using steps of length 1 or 2 or 3 or.....or m, here m<=n.

As the answer can be too large output it modulo 109+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;
}

As the complexity O(m*n), I want to reduce it.

vkstack
  • 1,582
  • 11
  • 24

2 Answers2

5

Your inner loop adds res[i-1] + res[i-2] + ... + res[i-m] to the result.

Let s be the sum of the first i elements in res. Then you can simply add s[i-1] - s[i-m-1] to the result.

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];
}

The new complexity will be O(n). You can even get rid of s as an array and use a single variable with a little more bookkeeping.

IVlad
  • 43,099
  • 13
  • 111
  • 179
2

I think use can use a variable Sum to store sum of res form i-m+1 to i like this:

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];
}
Vuong Long
  • 21
  • 3
  • srr, i've not tried it yet. for your code: my idea is store all value which you need to for j in a variable. (EX m=10, you need to go to step 100,you can step from 91,92..99 to step 100, i store all res[91], res[92]..res[100] in var sum so f[100] just equal sum) I see your code, i think your code give the wrong answer because your for from 1 then f[100] = f[1]+...f[10] – Vuong Long Aug 18 '15 at 10:58
  • bro i ran my code in a pogramming contest where i have to do it for m==3. it was accepted there. so knew that i am getting correct result for sample tests i run on my code.and the same test inputs i tried on dat of yours it is giving wrong result! – vkstack Aug 18 '15 at 11:45
  • I've test this code with your code in some test cases. It may return negative value by %. I've fix it. I hope this new code will be correct – Vuong Long Aug 18 '15 at 13:24
  • yes there were negative results due to which it seemed me if the code was wrong. Thnx bro! – vkstack Aug 18 '15 at 13:49