Description
给出(n,k,l)，问有多少种构造长度为(n)的序列(a)方法，使(a_i<l)且((a_1 ext{and} a_2) ext{or} (a_2 ext{and} a_3) ext{or} cdots ext{or} (a_{n-1} ext{and} a_n)=k)。
(n,k leq 2^{60},l leq 60)。
Solution
位运算一定要按位做！！！
按位做之后，问题就由非常大的整数问题转化为了01的问题。
那么考虑(k=0)时，不能出现有相邻的(a_i)都是1。因此我们可以(DP)一下。定义(f_{i,0})表示第(i)位填0的前(i)位没有相邻1的方案数，(f_{i,1})同理。有：
因此(f_{i,0}=f_{i-1,0}+f_{i-2,0})。答案是(f_{n,0}+f_{n,1}=f_{n,0}+f_{n-1,0}=f_{n+1,0})。而(f_{i,0})是线性递推式，是可以矩阵快速幂优化的（事实上这就是一个斐波那契数列，以下斐波那契数列记为(f_i)）。
接下来考虑(k=1)，即需要存在一对连续1。我们可以借鉴( ext{CF559C})的思想——枚举第一个连续1，那么之前不能存在连续1，后面可以随便。那么有
处理这个问题可以引入一个新的函数(g)，定义
那么有
考虑构造矩阵来算(g)。有
Discovery（戴睿同学的做法）
事实上，我们还可以用容斥来解决(k=1)的问题。总共有(2^n)中方案，接下来减去没有连续(1)的方案数（也就是(k=0)的答案）。简单多了= =。
但这让我们发现了一个关于斐波那契数列(下标从0开始)的恒等式：
要证明这个恒等式，我们可以将等式两边分别看做两个生成函数的系数，如果两个生成函数相等则恒等式成立。
(sumlimits_{i=1}^{n-1}f_{i-1} imes 2^{n-i-1}= sumlimits_{i=0}^{n-2}f_{i} imes 2^{n-i-2})可以看做斐波那契数列与等比数列的卷积，那么左边的生成函数封闭表达式即为
右边是系数相减，可以看做两个生成函数相减。(2^n)的生成函数是(dfrac{1}{1-2x})，(f_{n+1})的生成函数是(dfrac{dfrac{1}{1-x-x^2}-f_0}{x}=dfrac{1+x}{1-x-x^2})。那么右侧的生成函数是(dfrac{1}{1-2x}-dfrac{1+x}{1-x-x^2})，化简得
由于左边系数的下标是(n-2)，因此左边的生成函数要乘以(x^2)。因此左右相等，因此命题得证。
推斐波那契数列的通项公式
(F(x)=f_0+f_1x+f_2x^2+f_3x^3+ cdots)
(xF(x)=f_0x+f_1x^2+f_2x^3+f_3x^4+ cdots)
(x^2F(x)=f_0x^2+f_1x^3+f_2x^4+f_3x^5+ cdots)
(F(x)-xF(x)=f_0+f_0x^2+f_1x^3+cdots=x^2F(x)+1)
(F(x)=dfrac{1}{1-x-x^2})
考虑将(F(x))的封闭表达式表达成(dfrac{a_1}{1-a_2x})这样的等比数列的形式。
考虑将(F(x))进行裂项：
(F(x)=dfrac{a}{1-phi_1x} + dfrac{b}{1-phi_2x})
其中可以解得(phi_1=dfrac{sqrt 5+1}{2},phi_2=dfrac{1-sqrt 5}{2})
(a(1-phi_2x)+b(1-phi_1x)=1)恒成立
所以
解得
q'z
所以
因此系数是(f_n=dfrac{1}{phi_1-phi_2}(phi_1^n-phi_2^n))
Code
/*DennyQi 2019*/
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
#define int long long
using namespace std;
const int N = 100010;
const int P = 998244353;
const int INF = 0x3f3f3f3f;
inline int read(){
int x(0),w(1); char c = getchar();
while(c^'-' && (c<'0' || c>'9')) c = getchar();
if(c=='-') w = -1, c = getchar();
while(c>='0' && c<='9') x = (x<<3)+(x<<1)+c-'0', c = getchar(); return x*w;
}
int n,k,l,m,Fn,ans,cur,y;
inline int mul(const int& a, const int& b){ return 1ll*a*b%m; }
inline int add(const int& a, const int& b){ return (a+b>=m)?a+b-m:a+b; }
inline int sub(const int& a, const int& b){ return (a-b<0)?a-b+m:a-b; }
struct matrix{
int a[2][2];
matrix operator * (const matrix& X) const{
matrix res;
for(int i = 0; i < 2; ++i){
for(int j = 0; j < 2; ++j){
res.a[i][j] = 0;
for(int k = 0; k < 2; ++k){
res.a[i][j] = add(res.a[i][j],mul(a[i][k],X.a[k][j]));
}
}
}
return res;
}
};
matrix x,res;
inline int ksm(int x, int y){
int res = 1;
while(y>0){
if(y&1) res = mul(res,x);
y >>=1, x = mul(x,x);
}
return res;
}
#undef int
int main(){
#define int long long
// freopen("file.in","r",stdin);
n = read(), k = read(), l = read(), m = read();
if(l<=62&&(1ll<<l)<=k){
puts("0");
return 0;
}
res.a[0][0] = res.a[1][1] = 1;
x.a[0][1] = x.a[1][0] = x.a[1][1] = 1;
y = n;
while(y>0){
if(y&1) res = res*x;
y >>= 1, x = x*x;
}
Fn = add(res.a[0][1],res.a[1][1]);
ans = 1;
for(int i = 1; i <= l; ++i){
cur = (k&1);
k >>= 1;
if(cur == 0){
ans = mul(ans,Fn);
}else{
ans = mul(ans,sub(ksm(2,n),Fn));
}
}
printf("%lld
",ans%m);
return 0;
}