#include <bits/stdc++.h>
#define FAST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);cerr.tie(0)
#define mp make_pair
#define xx first
#define yy second
#define pb push_back
#define pf push_front
#define popb pop_back
#define popf pop_front
#define all(x) x.begin(),x.end()
#define ff(i,a,b) for (int i = a; i < b; i++)
#define fff(i,a,b) for (int i = a; i <= b; i++)
#define bff(i,a,b) for (int i = b-1; i >= a; i--)
#define bfff(i,a,b) for (int i = b; i >= a; i--)
using namespace std;
long double typedef ld;
unsigned int typedef ui;
long long int typedef li;
pair<int,int> typedef pii;
pair<li,li> typedef pli;
pair<ld,ld> typedef pld;
vector<vector<int>> typedef graph;
unsigned long long int typedef ull;
//const int mod = 998244353;
const int mod = 1000000007;
//Note to self: Check for overflow
#define int li
int power(int a, int n)
{
li c=1;
while (n)
{
if (n&1) (c*=a)%=mod;
a=(li)a*a%mod,n>>=1;
}
return c;
}
bool nemozerow=false;
bool nemozecol=false;
map<int,bool> row;
map<int,bool> col;
int odg=0;
int matra[7][7];
void rekurz(int i, int j, int n, int m)
{
if (j>m) j=1,i++;
if (i>n)
{
odg++;
/*cout<<"mogucnost:"<<endl;
fff(i,1,n)
{
fff(j,1,m) cout<<matra[i][j]<<" ";
cout<<endl;
} cout<<endl;*/
}
else if (i==1 || j==1)
{
if (!matra[i][j])
{
matra[i][j]=1;
rekurz(i,j+1,n,m);
matra[i][j]=-1;
rekurz(i,j+1,n,m);
matra[i][j]=0;
}
else rekurz(i,j+1,n,m);
}
else
{
if (matra[i][j])
{
if (matra[i][j]+matra[i-1][j]+matra[i][j-1]+matra[i-1][j-1]!=0) return;
rekurz(i,j+1,n,m);
}
else
{
if (matra[i-1][j]+matra[i][j-1]+matra[i-1][j-1]+1==0) matra[i][j]=1,rekurz(i,j+1,n,m),matra[i][j]=0;
if (matra[i-1][j]+matra[i][j-1]+matra[i-1][j-1]-1==0) matra[i][j]=-1,rekurz(i,j+1,n,m),matra[i][j]=0;
}
}
}
int solve()
{
int n,m,k; cin>>n>>m>>k;
bool edgecase=(k==0);
while (k--)
{
char signe;
int y,x; cin>>signe>>y>>x;
bool booligne=(signe=='+')^(y&1)^(x&1);
if (row.count(y) && booligne!=row[y]) nemozerow=true;
if (col.count(x) && booligne!=col[x]) nemozecol=true;
row[y]=booligne,col[x]=booligne;
}
if (nemozerow && nemozecol) return 0;
int ans=0;
if (!nemozerow)
{
(ans+=power(2,n-(int)row.size()))%=mod;
bool isparan=false,isneparan=false;
for (auto it : row) if (it.yy) isparan=true; else isneparan=true;
if (!isparan || !isneparan) ans--;
}
if (!nemozecol)
{
(ans+=power(2,m-(int)col.size()))%=mod;
}
if (edgecase) ans--;
return ans;
}
int solvebrute()
{
int n,m,k; cin>>n>>m>>k;
if (n>5 || m>5) return 0;
while (k--)
{
char signe;
int y,x; cin>>signe>>y>>x;
matra[y][x]=(signe=='+'?1:-1);
}
rekurz(1,1,n,m);
return odg;
}
signed main()
{
FAST;
cout<<solve()<<"\n";
/*fff(T,1,1000)
{
nemozerow=false;
nemozecol=false;
row.clear();
col.clear();
odg=0;
fff(i,0,6) fff(j,0,6) matra[i][j]=0;
int ocevidnolos=solve();
int dobar=solvebrute();
cout<<": "<<ocevidnolos<<" "<<dobar<<endl<<endl;
if (dobar!=ocevidnolos) cout<<"FATAL ERROR ==============================="<<endl<<endl<<"FATAL ERROR ==============================="<<endl<<endl<<"FATAL ERROR ==============================="<<endl<<endl<<"FATAL ERROR ==============================="<<endl<<endl<<"FATAL ERROR ==============================="<<endl<<endl<<endl;
}*/
}
//Note to self: Check for overflow
/*
5 5 2
- 5 1
+ 5 5
4 4 3
- 4 1
+ 4 4
+ 3 4
2 2 4
+ 1 1
+ 2 2
- 1 2
- 2 1
*/
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Correct |
0 ms |
212 KB |
Output is correct |
9 |
Correct |
0 ms |
212 KB |
Output is correct |
10 |
Correct |
0 ms |
212 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Correct |
0 ms |
212 KB |
Output is correct |
9 |
Correct |
0 ms |
212 KB |
Output is correct |
10 |
Correct |
0 ms |
212 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
1 ms |
316 KB |
Output is correct |
13 |
Correct |
1 ms |
212 KB |
Output is correct |
14 |
Correct |
1 ms |
340 KB |
Output is correct |
15 |
Correct |
1 ms |
340 KB |
Output is correct |
16 |
Correct |
49 ms |
900 KB |
Output is correct |
17 |
Correct |
50 ms |
884 KB |
Output is correct |
18 |
Correct |
52 ms |
976 KB |
Output is correct |
19 |
Correct |
55 ms |
860 KB |
Output is correct |
20 |
Correct |
58 ms |
932 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Correct |
0 ms |
212 KB |
Output is correct |
9 |
Correct |
0 ms |
212 KB |
Output is correct |
10 |
Correct |
0 ms |
212 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
1 ms |
316 KB |
Output is correct |
13 |
Correct |
1 ms |
212 KB |
Output is correct |
14 |
Correct |
1 ms |
340 KB |
Output is correct |
15 |
Correct |
1 ms |
340 KB |
Output is correct |
16 |
Correct |
49 ms |
900 KB |
Output is correct |
17 |
Correct |
50 ms |
884 KB |
Output is correct |
18 |
Correct |
52 ms |
976 KB |
Output is correct |
19 |
Correct |
55 ms |
860 KB |
Output is correct |
20 |
Correct |
58 ms |
932 KB |
Output is correct |
21 |
Correct |
118 ms |
8284 KB |
Output is correct |
22 |
Correct |
0 ms |
320 KB |
Output is correct |
23 |
Correct |
115 ms |
8268 KB |
Output is correct |
24 |
Correct |
114 ms |
8268 KB |
Output is correct |
25 |
Correct |
110 ms |
8268 KB |
Output is correct |
26 |
Correct |
111 ms |
11180 KB |
Output is correct |
27 |
Correct |
109 ms |
11272 KB |
Output is correct |
28 |
Correct |
110 ms |
11192 KB |
Output is correct |
29 |
Correct |
131 ms |
11256 KB |
Output is correct |
30 |
Correct |
140 ms |
13288 KB |
Output is correct |