//#pragma GCC Optimize("O3")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll>pairll;
typedef pair<ll,pairll>pairlll;
typedef pair<pairll,pairll>pairllll;
typedef long double ld;
typedef pair<ll,string>pairls;
#define INF 1000000000000007
#define MOD 1000000007
#define pb push_back
#define fr first
#define sc second
#define endl '\n'
ll n,m,k,X,Y;
struct D{
ll a,b,h;
}d[100007];
map<ll,ll>f1,g1,f2,g2;
ll S(ll x,ll y){
ll res=1;
while(y>0){
if(y%2==1){
res*=x;
res%=MOD;
}
x*=x;
x%=MOD;
y/=2;
}
return res;
}
int main() {
cin>>n>>m>>k;
ll N=n;
ll M=m;
if(k==0){
cout<<(S(2,n)+S(2,m)-2)%MOD;
return 0;
}
for(int i=1;i<=k;i++){
char c;
cin>>c>>d[i].a>>d[i].b;
if(c=='+')d[i].h=1;
else d[i].h=0;
}
for(int i=1;i<=k;i++){
if(f1[d[i].a]==0){
f1[d[i].a]=1;
g1[d[i].a]=(d[i].b+d[i].h)%2;
n--;
}else{
if(g1[d[i].a]!=(d[i].b+d[i].h)%2){
X=1;
}
}
if(f2[d[i].b]==0){
f2[d[i].b]=1;
g2[d[i].b]=(d[i].a+d[i].h)%2;
m--;
}else{
if(g2[d[i].b]!=(d[i].a+d[i].h)%2){
Y=1;
}
}
}
if(N==1){
cout<<S(2,m)<<endl;
}else if(M==1){
cout<<S(2,n)<<endl;
}else if(X==1 && Y==1){
cout<<0<<endl;
}else if(X==0 && Y==1){
cout<<S(2,n)<<endl;
}else if(X==1 && Y==0){
cout<<S(2,m)<<endl;
}else{
cout<<(S(2,n)+S(2,m)-1)%MOD<<endl;
}
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
0 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
204 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
1 ms |
204 KB |
Output is correct |
7 |
Correct |
1 ms |
204 KB |
Output is correct |
8 |
Correct |
1 ms |
204 KB |
Output is correct |
9 |
Correct |
1 ms |
204 KB |
Output is correct |
10 |
Correct |
1 ms |
204 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
0 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
204 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
1 ms |
204 KB |
Output is correct |
7 |
Correct |
1 ms |
204 KB |
Output is correct |
8 |
Correct |
1 ms |
204 KB |
Output is correct |
9 |
Correct |
1 ms |
204 KB |
Output is correct |
10 |
Correct |
1 ms |
204 KB |
Output is correct |
11 |
Correct |
2 ms |
460 KB |
Output is correct |
12 |
Correct |
1 ms |
204 KB |
Output is correct |
13 |
Correct |
1 ms |
204 KB |
Output is correct |
14 |
Correct |
2 ms |
460 KB |
Output is correct |
15 |
Correct |
2 ms |
460 KB |
Output is correct |
16 |
Correct |
97 ms |
3820 KB |
Output is correct |
17 |
Correct |
98 ms |
3804 KB |
Output is correct |
18 |
Correct |
99 ms |
3940 KB |
Output is correct |
19 |
Correct |
92 ms |
3792 KB |
Output is correct |
20 |
Correct |
87 ms |
3808 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
0 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
204 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
1 ms |
204 KB |
Output is correct |
7 |
Correct |
1 ms |
204 KB |
Output is correct |
8 |
Correct |
1 ms |
204 KB |
Output is correct |
9 |
Correct |
1 ms |
204 KB |
Output is correct |
10 |
Correct |
1 ms |
204 KB |
Output is correct |
11 |
Correct |
2 ms |
460 KB |
Output is correct |
12 |
Correct |
1 ms |
204 KB |
Output is correct |
13 |
Correct |
1 ms |
204 KB |
Output is correct |
14 |
Correct |
2 ms |
460 KB |
Output is correct |
15 |
Correct |
2 ms |
460 KB |
Output is correct |
16 |
Correct |
97 ms |
3820 KB |
Output is correct |
17 |
Correct |
98 ms |
3804 KB |
Output is correct |
18 |
Correct |
99 ms |
3940 KB |
Output is correct |
19 |
Correct |
92 ms |
3792 KB |
Output is correct |
20 |
Correct |
87 ms |
3808 KB |
Output is correct |
21 |
Correct |
266 ms |
18876 KB |
Output is correct |
22 |
Correct |
1 ms |
204 KB |
Output is correct |
23 |
Correct |
269 ms |
18940 KB |
Output is correct |
24 |
Correct |
255 ms |
18952 KB |
Output is correct |
25 |
Correct |
251 ms |
18936 KB |
Output is correct |
26 |
Correct |
295 ms |
24944 KB |
Output is correct |
27 |
Correct |
279 ms |
24968 KB |
Output is correct |
28 |
Correct |
273 ms |
24936 KB |
Output is correct |
29 |
Correct |
306 ms |
24864 KB |
Output is correct |
30 |
Correct |
366 ms |
29688 KB |
Output is correct |