# Lời giải:
- Hãy thử dùng mệnh đề phủ định để giải quyết bài toán này
( có thể có cách tính trực tiếp chỉ là mình không nghĩ ra :))) ).
- Dễ thấy số cách tạo ra ma trận nhị phân (không nhất thiết phải thõa mãn yêu cầu) là:
$(2^m)^n$.
- Mệnh đề phủ định:
số cách tạo ra ma trận nhị phân mà tồn tại ít nhất một hàng chỉ chứa toàn số 0
hay ít nhất một cột chỉ chứa số 1.
- **Nhận xét**: Dễ thấy nếu chọn một cột chỉ chứa toàn số 1 thì sẽ không thể tồn tại một hàng chỉ chứa toàn
số 0 được, như vậy ta sẽ tách chúng ra và xử lý 2 trường hợp.
---
- **Trường hợp 1**: Số cách tạo ra một ma trận nhị phân tồn tại ít nhất một cột chỉ chứa số 1.
- Với k từ 1 -> m, cố định k cột chỉ chứa số 1 rồi tiến hành xáo các phần tử ở các cột còn lại sao cho không tồn tại thêm
một cột chỉ chứa số một nào khác.
- Số cách chọn ra k cột trong m cột là $C(k,m)$.
- Số cách để xáo m-k cột còn lại mà không có cột nào chỉ chứa số 1 là $(2^n-1)^{m-k}$.
- Tổng quát: $ \sum_{k=1}^m C(k,m) * (2^n-1)^{m-k} $.
- Nhận thấy rằng cách này không thức hiện được vì m <= 1e9 nên phải biến đổi để rút gọn công thức.
- Thấy công thức có dạng tương tự như một nhị thức newton nên biến đổi nó thành:
$ \sum_{k=0}^m C(k,m) * (2^n-1)^{m-k} *1^k - C(0,m) * (2^n-1)^{m-0}$
= $ (2^n)^m - (2^n-1)^m $
- **Công thức sau rút gọn**: $ (2^n)^m - (2^n-1)^m $
---
- **Trường hợp 2**: Số cách tạo ra một ma trận nhị phân tồn tại ít nhất một hàng chỉ chứa số 0
- Cách tính giống trường hợp một (kiểu ta lật lại 90 độ)
---
- **Đáp án**: $(2^m)^n$ - $(reSol(n,m) + reSol(m,n))$ với $reSol(n,m)$ = $ (2^n)^m - (2^n-1)^m $
- Độ phức tạp: O($log (m*n)$)
# Code
``` cpp
#include<bits/stdc++.h>
#define ll long long
#define nl '\n'
#define f0(i,a,b) for (int i = a, _b = b; i < _b; i++)
#define f1(i,a,b) for (int i = a, _b = b; i <= _b; i++)
#define rf(i,a,b) for (int i = a, _b = b; i >=_b; i--)
#define fi first
#define se second
#define Size(a) (int)a.size()
#define bit(mask, i) ((mask>>i)&1)
#define Mask(i) (1<<(i))
using namespace std;
const int Maxn = 1e5+5;
const int mod = 1e9+7;
const int inf32 = 2e9+5;
const long long inf64 = 2e18+7;
int n, m;
ll Pow(ll a, ll b)
{
ll res = 1;
while(b)
{
if (b&1) res = res * a % mod;
a = a * a % mod;
b/=2;
}
return res;
}
int reSol(int n, int m)
{
ll tmp = Pow(2,n);
return (Pow(tmp, m)-Pow(tmp-1,m)+mod)%mod;
}
int sol(int n, int m)
{
return (Pow(2,1ll*n*m) - (reSol(n, m) + reSol(m, n))%mod + mod)%mod;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> n >> m;
cout << sol(n, m);
return 0;
}
```
zxcvbnm0123toi
Created at
1 likes