Robię wszędzie modulo k, mój algorytm jest iteracyjny i wykorzystuje sumy prefiksowe żeby można było się rozeznać ile wcześniejszych 6 pozycji nie zawiera w sobie pułapki.
Z resztą pokażę swój kod:
#include <iostream>
#include <vector>
#include <string>
using namespace std;
int getSum(vector<int> & prefix, int a, int b)
{
if(a < 0)//gdyby sie okazalo ze i-6 jest ujemne
a = 0;
return prefix[b+1] - prefix[a];
}
int main(int argc, const char * argv[]) {
int n,k;
cin >> n >> k;
char jumps[n];
vector<int> prefix(n+1);
prefix[0] = 0;
for(int i = 0; i < n; i++)
{
cin >> jumps[i];
if(jumps[i] == '1')
prefix[i+1] = prefix[i] + 1;
else
prefix[i+1] = prefix[i];
}
vector<int> ways(1);//kolejne ilosci sposobów dojscia
ways[0] = 1;//tj. start
for(int i = 1; i < n; i++)
{
if(jumps[i] == '1')
{
ways.push_back(0);//nowa pozycja
for(int j = 1; j <= getSum(prefix, i-6, i-1); j++)
ways[ways.size()-1] = (ways[ways.size()-1]+ways[ways.size()-j-1])%k;//ilosc dojsc do nowej pozycji = suma dojsc do poprzednich pozycji oddalonych na odleglosc nie wieksza niz 6
}
}
cout << ways[ways.size()-1] % k << endl;//ostateczny wynik
return 0;
}