Codeforces 551 D. GukiZ and Binary Operations

$>Codeforces \space 551 D. GukiZ and Binary Operations<$

题目大意 :给出 $n, \ k$ 求有多少个长度为 $n$ 的序列 $a$ 满足 $(a_1\ and \ a_2)or(a_2\ and \ a_3)or..or(a_{n-1}\ and \ a_n) = k$ 且 $a_i \leq k \leq 2^l$

并输出方案数在$\mod m $ 意义下的值

$0≤ n ≤ 10^{18},\ 0 ≤ k ≤ 10^{18}, \ 0 \leq l \leq 64, \ 1 \leq m \leq 10^9 + 7$

解题思路 :

考虑对于二进制按位拆开来考虑，设某一位最终为 $i$ 的方案为 $g_i \ (i = 0 / 1)$

因为位与位之间相互不影响，由此可以得到 $Ans = \sum_{i = 0}^{l - 1} g_{(2^i and \space k)} $

问题转化为如何求出 $g_i$, 观察发现 $g_i$ 只要求出一个，另外一个就是 $2^n - g_i$

仔细分析后发现 $g_0$ 比较好求，设 $f_i$ 为前 $i$ 位的式子的结果为 $0$ 的方案

考虑第 $i$ 位后答案若要为 $0$ ，如果第 $i$ 位选 $1$，那么第 $i - 1$ 位必然选 $1$ ，方案数就是 $f_{i-2}$

否则第 $i$ 位选 $0$, 第 $i-1$ 位选什么都可以，方案数是 $f_{i-1}$ 所以有 $f_i = f_{i-1} + f_{i-2}$

发现式子其实就是斐波那契数列的递推式，用矩阵快速幂求出后把得到的 $g_0$ 和 $g_1$ 带回先前的式子算出答案即可

/*program by mangoyang*/

#include<bits/stdc++.h>

#define inf (0x7f7f7f7f)

#define Max(a, b) ((a) > (b) ? (a) : (b))

#define Min(a, b) ((a) < (b) ? (a) : (b))

typedef long long ll;

using namespace std;

template <class T>

inline void read(T &x){

    int f = 0, ch = 0; x = 0;

    for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = 1;

    for(; isdigit(ch); ch = getchar()) x = x * 10 + ch - 48;

    if(f) x = -x;

}

#define int ll

int n, k, l, Mod;

const int le = 2;

struct Matrix{

	int a[le+5][le+5];

	inline Matrix(){ memset(a, 0, sizeof(a)); }

	inline void write(){

		for(int i = 1; i <= le; i++, putchar('\n'))

			for(int j = 1; j <= le; j++) cout << a[i][j] << " ";

	}

};

inline Matrix Mult(Matrix A, Matrix B){

	Matrix C;

	for(int i = 1; i <= le; i++)

		for(int j = 1; j <= le; j++)

			for(int k = 1; k <= le; k++)

				(C.a[i][j] += A.a[i][k] * B.a[k][j]) %= Mod;

	return C;

}

inline Matrix Power(Matrix a, int b){

	Matrix ans = a; b--;

	for(; b; b >>= 1, a = Mult(a, a))

		if(b & 1) ans = Mult(ans, a);

	return ans;

}

inline ll Pow(int a, int b){

	int ans = 1;

	for(; b; b >>= 1, a = a * a % Mod)

		if(b & 1) ans = ans * a % Mod;

	return ans;

}

main(){

	read(n), read(k), read(l), read(Mod);

	if(l < 63 && k >= (1ll << l)) return puts("0"), 0;

	int all = Pow(2, n);

	Matrix A, B;

	A.a[1][1] = A.a[2][1] = 1;

	B.a[1][1] = B.a[1][2] = B.a[2][1] = 1;

	B = Power(B, n), A = Mult(B, A);

	int now = (all - A.a[1][1] + Mod) % Mod, ans = 1 % Mod;

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

		if((1ll << i) & k) (ans *= now) %= Mod;

			else (ans *= A.a[1][1]) %= Mod;

	cout << ans % Mod;

	return 0;

}

巴特西

Codeforces 551 D. GukiZ and Binary Operations

解题思路 :

最新文章

热门文章