2024牛客D1

发表于 更新于

A

​ Given two integer \(n\) and \(m\), among all the sequence containing n non-negative integers less than \(2^m\), you need to count the number of such sequences \(A\) that there exists a non-empty subsequence of \(A\) in which the bitwise AND of the integers is \(1\).

​ Since the answer may be very large, output it modulo a positive integer \(q\).

Input

​ The only line contains three integers \(n,m,q\). (\(1 \le n,m \le 5000, 1 \le q \le 10^9\))

Output

​ Output a line containing an integer, denoting the answer.

Sample input 1

1
2 3 998244353

Sample output 1

1
17

Sample input 2

1
5000 5000 998244353

Sample output 2

1
2274146

Solution:牛客2024D1TA_哔哩哔哩_bilibili

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include<bits/stdc++.h>
#define f(i,l,r) for (int i=l; i<=r; i++)
#define int long long

using namespace std;

const int maxn = 5e3 + 5;
int n,m,mo;
int C[maxn][maxn];

void pre() {
	f(i,1,5000)
		C[i][i] = C[i][0] = 1;
	f(i,2,5000)
		f(j,1,i - 1) {
			C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % mo;			
		}

}

int ksm(int x,int y) {
	int ans = 1;
	while (y) {
		if (y & 1)
			(ans *= x) %= mo;
		y >>= 1;
		(x *= x) %= mo;
	}
	return ans;
}

signed main() {
	cin>>n>>m>>mo;
	pre();
	if (m == 1) {
		int ans = ksm(2,n) - 1;
		if (ans < 0) ans += mo;
		cout<<ans<<'\n';
		return 0; 
	}
	int ans = 0;
	
	f(i,0,n) {
		int tmp = ksm(ksm(2,i) - 1,m - 1);
		if (tmp < 0) tmp += mo;
		int oth = ksm(ksm(2,n - i),m - 1);
		int cnt = ((tmp * oth) % mo * C[n][i]) % mo;
		(ans += cnt) %= mo; 
	}
	if (ans < 0) ans += mo;
	cout<<ans<<'\n';
	return 0;
}

B

​ Given two integer \(n\) and \(m\), among all the sequence containing n non-negative integers less than \(2^m\), you need to count the number of such sequences \(A\) that there exists at least two different non-empty subsequence of \(A\) in which the bitwise AND of the integers is \(1\).

​ Since the answer may be very large, output it modulo a positive integer \(q\).

Input

​ The only line contains three integers \(n,m,q\). (\(1 \le n,m \le 5000, 1 \le q \le 10^9\))

Output

​ Output a line containing an integer, denoting the answer.

Sample input 1

1
2 3 998244353

Sample output 1

1
7

Sample input 2

1
5000 5000 998244353

Sample output 2

1
530227736

Solution: 牛客2024D1TB_哔哩哔哩_bilibili

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
#include<bits/stdc++.h>
#define f(i,l,r) for (int i=l; i<=r; ++i)
#define int long long

using namespace std;

const int maxn = 5e3 + 5;
int n,m,mo,ans1,ans2;
int C[maxn][maxn],dp[maxn][maxn];
int f[maxn];

int ksm(int x,int y) {
	int ans = 1;
	while (y) {
		if (y & 1)
			(ans *= x) %= mo;
		y >>= 1;
		(x *= x) %= mo;
	}
	return ans;
}

void pre() {
	f(i,1,5000)
		C[i][i] = C[i][0] = 1;
	f(i,2,5000)
		f(j,1,i - 1) {
			C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % mo;			
		}
	f[0] = 1;
	f(i,1,5000) 
		f[i] = (f[i - 1] << 1) % mo;
	//dp[i][j] = ksm(2^i - 1 - j, m - 1)
	dp[0][0] = 0;
	f(i,1,n) {  // j in [0,i]
		for (int j=1; j<=i; j+=2)
			dp[i][j] = (dp[i - 1][((1 + j) >> 1) - 1] * f[m - 1]) % mo;
		for (int j=0; j<=i; j+=2)
			dp[i][j] = ksm(f[i] - 1 - j,m - 1);
	}
}

void solve1() {
	pre();
	int ans = 0;
	
	f(i,0,n) {
		int v = f[i] - 1; if (v < 0) v += mo;
		int tmp = (ksm(f[i], m - 1) - ksm(v,m - 1)) % mo;
		if (tmp < 0) tmp += mo;
		int oth = ksm(f[n - i],m - 1);
		int cnt = ((tmp * oth) % mo * C[n][i]) % mo;
		ans += cnt;
	}
	ans = (ksm(f[n],m) - ans) % mo;
	if (ans < 0) ans += mo;
	ans1 = ans;
}
signed main() {
// 	freopen("in.in","r",stdin);
// 	freopen("1.out","w",stdout); 
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin>>n>>m>>mo;
	if (mo == 1) {
		cout<<"0\n";
		return 0;
	}
	solve1();
	if (m == 1) {
		int final = f[n] - n - 1; final %= mo; if (final < 0) final += mo;
		cout<<final<<'\n';
		return 0; 
	}
	
	f(i,0,n) { // i: the number of how many entry with the least significant bit being 1
		if (i > m - 1) break;
		int sum = 0;
		int p = f[i] - 1; 
		f(j,0,i) {
			//dp[i][j] = ksm(2^i - 1 - j, m - 1)
			int tmp = (dp[i][j] * C[i][j]) % mo;
			if (j & 1) tmp = (~tmp + 1);
			sum += tmp;	
		} 
		sum %= mo;
//		if (sum < 0) sum += mo;
		int oth = ksm(f[n - i],m - 1);
		int loc = ((sum * oth) % mo * C[n][i]) % mo;
		ans2 += loc;
		
	}
	int final = (ans1 - ans2) % mo; if (final < 0) final += mo;
	cout<<final<<'\n';
	return 0;
}

/*
	int sum = 0;
		f(j,0,i - 1) {
			int tmp = ksm(n - j,m - 1) * C[i][j];
			if (j & 1) tmp = -tmp; tmp %= mo;
			(sum += tmp) %= mo;
		}
*/