#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define sz(a) (int)a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x,y) ((x+y-1)/(y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "YES" << endl
#define no cout << "NO" << endl
#define rep(i,n) for(int i = 0; i < n; ++i)
#define rep1(i,n) for(int i = 1; i <= n; ++i)
#define rev(i,s,e) for(int i = s; i >= e; --i)
#define trav(i,a) for(auto &i : a)
template<typename T>
void amin(T &a, T b) {
a = min(a,b);
}
template<typename T>
void amax(T &a, T b) {
a = max(a,b);
}
#ifdef LOCAL
#include "debug.h"
#else
#define debug(x) 42
#endif
/*
*/
const int MOD = 1e9 + 7;
const int N = 1e5 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;
struct Matrix {
vector<vector<ll>> a;
int n, m;
Matrix() {
}
Matrix(int row, int col) {
n = row, m = col;
a = vector<vector<ll>>(row, vector<ll>(col));
}
Matrix operator*(const Matrix &mat2) {
int n2 = mat2.n, m2 = mat2.m;
Matrix res(n, m2);
rep(i, n) {
rep(j, m2) {
rep(k, m) {
ll temp = (a[i][k] * mat2.a[k][j]) % MOD;
res.a[i][j] = (res.a[i][j] + temp) % MOD;
}
}
}
return res;
}
void exp(ll b) {
Matrix res(n, m);
Matrix curr = *this;
rep(i, n) res.a[i][i] = 1;
while (b) {
if (b & 1) res = res * curr;
curr = curr * curr;
b /= 2;
}
a = res.a;
}
};
void solve(int test_case)
{
ll m,n,k; cin >> m >> n >> k;
map<ll,ll> mp;
while(k--){
ll j,i; cin >> j >> i;
i--, j--;
mp[i] |= (1<<j);
}
mp[0] = 0;
mp[n-1] = 0;
bool dp[1<<m][1<<m];
memset(dp,0,sizeof dp);
auto f = [&](ll mask, ll bit){
if(mask&(1<<bit)) return 1;
else return 0;
};
{
dp[0][0] = 1;
queue<pll> q;
q.push({0,0});
while(!q.empty()){
auto [mask2,mask3] = q.front();
q.pop();
rep(i,m-1){
// 2 right, down left
if(!f(mask2,i) and !f(mask2,i+1) and !f(mask3,i)){
ll mask4 = mask2|(1<<i)|(1<<(i+1));
ll mask5 = mask3|(1<<i);
if(!dp[mask4][mask5]){
q.push({mask4,mask5});
dp[mask4][mask5] = 1;
}
}
// 2 right, down right
if(!f(mask2,i) and !f(mask2,i+1) and !f(mask3,i+1)){
ll mask4 = mask2|(1<<i)|(1<<(i+1));
ll mask5 = mask3|(1<<(i+1));
if(!dp[mask4][mask5]){
q.push({mask4,mask5});
dp[mask4][mask5] = 1;
}
}
// 1 up left, 2 down
if(!f(mask2,i) and !f(mask3,i) and !f(mask3,i+1)){
ll mask4 = mask2|(1<<i);
ll mask5 = mask3|(1<<i)|(1<<(i+1));
if(!dp[mask4][mask5]){
q.push({mask4,mask5});
dp[mask4][mask5] = 1;
}
}
// 1 up right, 2 down
if(!f(mask2,i+1) and !f(mask3,i) and !f(mask3,i+1)){
ll mask4 = mask2|(1<<(i+1));
ll mask5 = mask3|(1<<i)|(1<<(i+1));
if(!dp[mask4][mask5]){
q.push({mask4,mask5});
dp[mask4][mask5] = 1;
}
}
}
}
}
Matrix base(1,1<<m);
ll ptr = 1;
rep(mask,1<<m){
if((mp[0]^mask) == ((1<<m)-1)){
rep(mask2,1<<m){
base.a[0][mask2] = dp[mask][mask2];
}
}
}
Matrix mat(1<<m,1<<m);
rep(i,1<<m){
ll mask1 = ((1<<m)-1)^i;
rep(j,1<<m){
mat.a[i][j] = dp[mask1][j];
}
}
for(auto [i,bad_mask] : mp){
if(i == 0) conts;
ll k = i-ptr;
auto base_copy = base;
auto mat_copy = mat;
mat_copy.exp(k);
base = base*mat_copy;
Matrix base2(1,1<<m);
rep(mask,1<<m){
if(mask&bad_mask){
base.a[0][mask] = 0;
}
else{
ll more = (1<<m)-1;
more ^= mask;
more ^= bad_mask;
rep(mask2,1<<m){
base2.a[0][mask2] = base.a[0][mask]*dp[more][mask2];
}
}
}
base = base2;
ptr = i;
}
ll ans = base.a[0][0];
if(ans) yes;
else no;
}
int main()
{
fastio;
int t = 1;
// cin >> t;
rep1(i, t) {
solve(i);
}
return 0;
}
Compilation message
ltrominoes.cpp: In member function 'Matrix Matrix::operator*(const Matrix&)':
ltrominoes.cpp:74:13: warning: unused variable 'n2' [-Wunused-variable]
74 | int n2 = mat2.n, m2 = mat2.m;
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
379 ms |
1116 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
1 ms |
348 KB |
Output is correct |
| 5 |
Runtime error |
274 ms |
524288 KB |
Execution killed with signal 9 |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
476 KB |
Output is correct |
| 2 |
Incorrect |
13 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
8032 ms |
1116 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
