链接
点击跳转
题解
可以发现每一位都是单独的，分开来做
d
p
dp
dp
f
i
,
0
/
1
,
0
/
1
f_{i,0/1,0/1}
fi,0/1,0/1表示长度为
i
i
i的
01
01
01序列，最后一位是
0
/
1
0/1
0/1，或起来的结果是
0
/
1
0/1
0/1的方案数
矩阵加速转移
代码
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define iinf 0x3f3f3f3f
#define linf (1ll<<60)
#define eps 1e-8
#define maxn 1000010
#define maxe 1000010
#define cl(x) memset(x,0,sizeof(x))
#define rep(_,__) for(_=1;_<=(__);_++)
#define em(x) emplace(x)
#define emb(x) emplace_back(x)
#define emf(x) emplace_front(x)
#define fi first
#define se second
#define de(x) cerr<<#x<<" = "<<x<<endl
using namespace std
;
using namespace __gnu_pbds
;
typedef long long ll
;
typedef pair
<int,int> pii
;
typedef pair
<ll
,ll
> pll
;
ll n
, l
, k
, mod
;
ll
read(ll x
=0)
{
ll c
, f(1);
for(c
=getchar();!isdigit(c
);c
=getchar())if(c
=='-')f
=-f
;
for(;isdigit(c
);c
=getchar())x
=x
*10+c
-0x30;
return f
*x
;
}
struct Matrix
{
ll n
, m
, a
[30][30];
ll
* operator[](ll x
){return a
[x
];}
Matrix(ll x
, ll y
)
{
n
=x
, m
=y
;
ll i
, j
;
rep(i
,n
)rep(j
,n
)a
[i
][j
]=0;
}
Matrix(vector
<vector
<ll
>> v
)
{
ll i
, j
;
n
=v
.size(), m
=v
[0].size();
rep(i
,n
)rep(j
,m
)a
[i
][j
]=v
[i
-1][j
-1]%mod
;
}
friend Matrix
operator*(Matrix a
, Matrix b
)
{
Matrix
t(a
.n
,b
.m
);
ll i
, j
, k
;
rep(i
,t
.n
)rep(k
,a
.m
)rep(j
,t
.m
)(t
[i
][j
]+=a
[i
][k
]*b
[k
][j
])%=mod
;
return t
;
}
void show()
{
ll i
, j
;
cerr
<<"Matrix "<<n
<<"*"<<m
<<":"<<endl
;
for(i
=1;i
<=n
;i
++)
{
for(j
=1;j
<=m
;j
++)cerr
<<a
[i
][j
];
cerr
<<endl
;
}
}
friend Matrix
operator^(Matrix a
, ll b
)
{
ll i
, j
;
Matrix
t(a
.n
,a
.m
), ans(a
.n
,a
.m
);
rep(i
,a
.n
)rep(j
,a
.m
)t
[i
][j
]=a
[i
][j
];
rep(i
,a
.n
)ans
[i
][i
]=1;
for(;b
;b
>>=1,t
=t
*t
)if(b
&1)ans
=ans
*t
;
return ans
;
}
};
struct EasyMath
{
ll prime
[maxn
];
bool mark
[maxn
];
ll
fastpow(ll a
, ll b
, ll c
)
{
ll
t(a
%c
), ans(1ll);
for(;b
;b
>>=1,t
=t
*t
%c
)if(b
&1)ans
=ans
*t
%c
;
return ans
;
}
void get_prime(ll N
)
{
ll i
, j
;
for(i
=2;i
<=N
;i
++)mark
[i
]=false;
*prime
=0;
for(i
=2;i
<=N
;i
++)
{
if(!mark
[i
])prime
[++*prime
]=i
;
for(j
=1;j
<=*prime
and i
*prime
[j
]<=N
;j
++)
{
mark
[i
*prime
[j
]]=true;
if(i
%prime
[j
]==0)break;
}
}
}
}em
;
int main()
{
cin
>>n
>>k
>>l
>>mod
;
if(k
>=(1ll<<l
) and l
<=62){cout
<<0;return 0;}
Matrix
f( { {2},{0},{1},{1} } );
Matrix
T( { {1,0,1,0}, {0,1,0,1}, {1,0,0,0}, {0,1,1,1} } );
f
= (T
^(n
-2)) * f
;
ll t
=0;
while(k
)t
+=k
&1, k
>>=1;
cout
<< ( em
.fastpow(f
[1][1]+f
[3][1],l
-t
,mod
) * em
.fastpow(f
[2][1]+f
[4][1],t
,mod
) ) %mod
;
return 0;
}
