题目地址：http://codeforces.com/contest/551/problem/D

分析下公式能够知道，相当于每一位上放0或者1使得最后成为0或者1。假设最后是0的话，那么全部相邻位一定不能全是1，由于假设有一对相邻位全为1，那么这两个的AND值为1。又由于OR值是仅仅要有1。结果就为1。所以这位结果肯定为1。所以就推出了一个dp转移方程。dp[i][j]表示第i位上的数为j时的总个数。那么有：

dp[i][0]=dp[i-1][0]+dp[i-1][1];

dp[i][1]=dp[i-1][0];

设f[i]表示第i位上的总个数，即f[i]=dp[i][0]+dp[i][1].

所以，f[i]=dp[i-1][0]+dp[i-1][1]+dp[i-1][0]

f[i]=f[i-1]+dp[i-1][0]

f[i]=f[i-1]+dp[i-2][0]+dp[i-2][1]

f[i]=f[i-1]+f[i-2]

所以，推到最后可发现这是一个斐波那契！！

所以用矩阵高速幂求结果为0时的情况。然后为1的时候就是2^n-（结果为0的情况值）。

然后由于每一位都是独立的，所以分别推断每一位是0还是1，然后乘起来。

代码例如以下：

#include <iostream>

#include <string.h>

#include <math.h>

#include <queue>

#include <algorithm>

#include <stdlib.h>

#include <map>

#include <set>

#include <stdio.h>

#include <time.h>

using namespace std;

#define LL __int64

#define pi acos(-1.0)

//#pragma comment(linker, "/STACK:1024000000")

//const int mod=9901;

const int INF=0x3f3f3f3f;

const double eqs=1e-9;

const int MAXN=110000+10;

LL mod;

struct Matrix

{

        LL ma[3][3];

}init,res;

LL ksm(LL k, LL x)

{

        LL ans=1;

        while(k){

                if(k&1) ans=ans*x%mod;

                k>>=1;

                x=x*x%mod;

        }

        return ans;

}

Matrix Mult(Matrix x, Matrix y, int z)

{

        Matrix tmp;

        for(int i=0; i<z; i++) {

                for(int j=0; j<z; j++) {

                        tmp.ma[i][j]=0;

                        for(int k=0; k<z; k++) {

                                tmp.ma[i][j]+=x.ma[i][k]*y.ma[k][j];

                                if(tmp.ma[i][j]>=mod) tmp.ma[i][j]%=mod;

                        }

                }

        }

        return tmp;

}

Matrix Pow(Matrix x, LL k, int z)

{

        Matrix tmp;

        int i, j;

        for(i=0; i<z; i++) for(j=0; j<z; j++) tmp.ma[i][j]=(i==j);

        while(k) {

                if(k&1) tmp=Mult(tmp,x,z);

                x=Mult(x,x,z);

                k>>=1;

        }

        return tmp;

}

int main()

{

        LL n, k, l, x1, x2, ans, tmp, i;

        while(scanf("%I64d%I64d%I64d%I64d",&n,&k,&l,&mod)!=EOF){

                if(l<=62&&k>=((LL)1<<l)){

                        puts("0");

                        continue ;

                }

                init.ma[0][0]=init.ma[0][1]=1;

                init.ma[1][0]=1;

                init.ma[1][1]=0;

                res=Pow(init,n-2,2);

                tmp=ksm(n,(LL)2);

                x1=(res.ma[0][1]*2%mod+res.ma[0][0]*3%mod)%mod;

                x2=(tmp+mod-x1)%mod;

                ans=1;

                for(i=0;i<l;i++){

                        if(k&((LL)1<<i))

                                ans=ans*x2%mod;

                        else ans=ans*x1%mod;

                }

                printf("%I64d\n",ans%mod);

        }

        return 0;

}