题目
直接看讨论区题解就好了

此题由于方程中仅含位操作，所以首先可以考虑将k以二进制的形式分开来看每一位。
假设当前考虑的是k的第i位，那么这一位将由且仅由n个ai的第i位决定，其中，n个数的总情况数为2^n。
若k的第i位为0，那么a1, a2…an中，在第i位上必然不存在相邻的1，设所有满足不存在相邻1的情况数为x；
那么满足使k的第i位为1的情况数就是2^n - x，我们设y = 2^n - x。
于是若k在二进制的0 ~ L位中，存在p个1和q个0，ans即为 y^p * x^q。
对于解x的值，当n = 1，x = 2；当n = 2，x = 3；当n更大的时候，可以考虑第n位的两种情况，若第n位为0那么前n-1位只要满足“不存在相邻1”即可；若第n位为1，那么第n-1位必须为0，而前n-2位满足“不存在相邻1”即可。
于是得到转移方程：dp[n] = dp[n - 1] + dp[n - 2]，但是n比较大，无法O(n)递推，但是很庆幸这个转移方程就是Fibonacci数列，很容易想到使用矩阵快速幂进行加速求得某项的值，于是此题得解。
以上内容写的比较啰嗦…
但是友情提示一句，需要特判考虑无解的情况：）

#include<bits/stdc++.h> using namespace std; typedef long long ll; int l,m,cnt; ll n,k; struct M{ int a[2][2]; friend M operator*(M x,M y){ M z; for (int i=0;i<2;i++) for (int j=0;j<2;j++) z.a[i][j]=(1ll*x.a[i][0]*y.a[0][j]%m+1ll*x.a[i][1]*y.a[1][j]%m)%m; return z; } friend M operator^(M x,ll y){ M z; z.a[0][0]=z.a[1][1]=1; z.a[0][1]=z.a[1][0]=0; for (;y;y>>=1,x=x*x) if (y&1) z=z*x; return z; } }A,B; int pw(int x,ll y){ int z=1; for (;y;x=1ll*x*x%m,y>>=1) if (y&1) z=1ll*z*x%m; return z; } int main(){ scanf("%lld%lld%d%d",&n,&k,&l,&m); if (m==1 || l<64 && k>=(1ull<<l)) return puts("0"),0; A.a[0][0]=2;A.a[0][1]=3; B.a[0][1]=B.a[1][0]=B.a[1][1]=1; A=A*(B^(n-1)); for (;k;k^=k&(-k),cnt++); printf("%lld",(1ll*pw(A.a[0][0],l-cnt)*pw(pw(2,n)-A.a[0][0],cnt)%m+m)%m); }