Problem D. GukiZ and Binary Operations
Solution
一位一位考虑，就是求一个二进制序列有连续的1的种类数和没有连续的1的种类数。
没有连续的1的二进制序列的数目满足f[i]=f[i-1]+f[i-2],恰好是斐波那契数列。
数据范围在10^18，用矩阵加速计算，有连续的1的数目就用2^n-f[n+1]
最后枚举k的每一位,是1乘上2^n-f[n+1],是0乘上f[n+1]
注意以上需要满足 2^l>k。并且这里l的最大值为64，需要特判。
#include <bits/stdc++.h> using namespace std; typedef unsigned long long ll;
const int N = ;
ll n, k, l, m; struct Mat {
ll mat[N + ][N + ];
} A, B; Mat operator * ( Mat a, Mat b )
{
Mat c;
memset ( c.mat, , sizeof c.mat );
for ( int k = ; k < N; k++ )
for ( int i = ; i < N; i++ )
for ( int j = ; j < N; j++ )
( c.mat[i][j] += ( a.mat[i][k] * b.mat[k][j] ) % m ) %= m;
return c;
} Mat operator ^ ( Mat a, ll pow )
{
Mat c;
for ( int i = ; i < N; i++ )
for ( int j = ; j < N; j++ )
c.mat[i][j] = ( i == j );
while ( pow ) {
if ( pow & ) c = c * a;
a = a * a;
pow >>= ;
}
return c;
} ll quickp( ll x )
{
ll s = , c = ;
while( x ) {
if( x & ) s = ( s * c ) % m;
c = ( c * c ) % m;
x >>= ;
}
return s;
}
int main()
{
ios::sync_with_stdio( );
Mat p, a;
p.mat[][] = , p.mat[][] = ;
p.mat[][] = , p.mat[][] = ;
a.mat[][] = , a.mat[][] = ;
a.mat[][] = , a.mat[][] = ;
cin >> n >> k >> l >> m; ll ans = ;
if( l == || ( 1uLL << l ) > k ) {
ans++;
p = p ^ n;
a = a * p;
ll t1 = a.mat[][], t2 = ( m + quickp( n ) - t1 ) % m;
for( int i = ; i < l; ++i ) {
if( k & ( 1uLL << i ) ) ans = ( ans * t2 ) % m;
else ans = ( ans * t1 ) % m;
}
} cout << ans%m << endl; }