12593 - Next Generation Macaw

[magurmach]

The reason in simple, you are using trying to use more memory than available, use pointer as much as possible!

[magurmach]

Test Case:

Input:

Code: Select all

2
2000000000 100
1 1

Output:

Code: Select all

Case 1: 6678
Case 2: 2

[army007]

I am not sure why my code do not match the first case given here.
I have used the following recurrence:-

f(1) = f(2) = 2
f(n) = SUM(f(n-i)) ; 2 <= i <= k for n > 2

Here is my code:

Code: Select all

#include <cassert>
#include <algorithm>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
#include <valarray>
#include <functional>
#include <iterator>

using namespace std;

#define fo(i,j,n) for(i=j;i<n;++i)
#define Fo(i,j,n) for(i=n-1;i>=j;--i)
#define foo(i,j,v) fo(i,j,sz(v))
#define Foo(i,j,v) Fo(i,j,sz(v))
#define li(v) v.begin(),v.end()
#define sz(v) ((int)v.size())
#define CLR(a,v) memset((a),(v),sizeof(a))
#define equals(a,b) (fabs(a-b)<eps)
#define phl printf("Hello\n")

#define inf 1000000001
typedef long long Long;
//typedef __int64 Long;
#define pi (2*acos(0))
#define eps 1e-9

#define pb(x) push_back(x)
#define present(m,s) (m.find(s)!=m.end())

bool readn(int &n){ return scanf("%d",&n) == 1; }
//bool readl(Long &n)	{ return scanf("%lld",&n) == 1; }
bool readd(double &n){ return scanf("%lf",&n) == 1; }


const int maxn = 110, mod = 10007;

struct matrix;
void show(const matrix &T);

struct matrix{
    int row,col;
	Long a[maxn][maxn];
    void clear() { CLR(a,0); }
    void identity(){
        int i; this->clear(); fo(i,0,row) a[i][i] = 1;
    }
    matrix operator*(const matrix &b) const {
        int i,j,k;
        matrix c; c.row = row; c.col = b.col; c.clear();
        fo(i,0,row){
            fo(j,0,b.col){
                fo(k,0,col){
                    c.a[i][j] += ((a[i][k]%mod) * (b.a[k][j]%mod))%mod;
//                    c.a[i][j] += a[i][k] * b.a[k][j];
                    c.a[i][j] %= mod;
                }
            }
        }
		return c;
    }
    matrix operator^(int p)const{
        matrix res,x = (*this); res.row = row; res.col = col;
		res.identity();
        while(p){
            if(p&1) res = res*x;
            x = x*x;
            p >>= 1;
        }
        return res;
    }
};

void show(const matrix &T){
    int i,j;
    printf("[%dx%d]\n", T.row, T.col);
    fo(i,0,T.row){ fo(j,0,T.col){
        printf("%d ", T.a[i][j]);
    } printf("\n"); }
}

matrix M,A;
int n,k;

void constructA(){
    int i;
    A.row = k; A.col = 1;
    A.a[0][0] = A.a[1][0] = 2;
    fo(i,2,k){
        A.a[i][0] = A.a[i-1][0] + A.a[i-2][0];
    }
    reverse(A.a,A.a+k);
}

void constructM(){
    int i,j;
    M.row = M.col = k;
    M.a[0][0] = 0;
    fo(j,1,k) M.a[0][j] = 1;
    fo(i,1,k){
        fo(j,0,k){
            if(i = j+1) M.a[i][j] = 1;
            else M.a[i][j] = 0;
        }
    }
}

int ans(){
    if(n <= k) return A.a[k-n][0];
    matrix B,T = M^(n-k);
    B = T*A;
    return B.a[0][0];
}

int main(){
    int res,i,j,kase = 0,t;
    readn(t);
    while(t--){
        readn(n); readn(k);
        constructA(); constructM();
        res = ans();
        printf("Case %d: %d\n", ++kase, res);
    }
	return 0;
}