QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#668021#7900. Gifts from Knowledgezyq_313WA 23ms36964kbC++142.7kb2024-10-23 10:42:262024-10-23 10:42:30

Judging History

你现在查看的是最新测评结果

  • [2024-10-23 10:42:30]
  • 评测
  • 测评结果:WA
  • 用时:23ms
  • 内存:36964kb
  • [2024-10-23 10:42:26]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define DEBUG 0

// #define int long long
#define endl '\n'

#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define yes cout << "Yes\n"
#define no cout << "No\n"


#define lc u << 1 
#define rc u << 1 | 1
#define lowbit(x) x & -x

#define sz(x) (int(x.size()))
#define all(x) x.begin(), x.end()

#define rep(i, l, r) for (ll i = (l); i <= (r); ++ i)
#define per(i, l, r) for (ll i = (l); i >= (r); -- i)

#define mst(x, bit) memset(x, bit, sizeof(x))
#define mem(a, x) memset(a, x, sizeof a)
#define mep(a, x) memcpy(a, x, sizeof x)

#define pll(x) cout << x << endl

using db = double;
using ll = long long;
using pdd = pair<db, db>;
using pll = pair<ll, ll>;
using pii = pair<int, int>;

const int mod = 1e9 + 7;

ll qpow(ll a,ll b) { ll ans=1; while(b){if(b&1)ans=ans*a%mod;a=a*a%mod;b>>=1;}return ans; }
ll qpow(ll a,ll b,ll p) { ll ans=1;while(b){if(b&1)ans=ans*a%p;a=a*a%p;b>>=1;}return ans; }
ll inv(ll x) { return qpow(x,mod-2,mod);}
ll inv(ll x,ll p){return qpow(x,p-2,p); }

const int N = 1e6 + 10;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;

int n, m;
string s[N];
int f[N * 2];

int find(int x){
	if (x != f[x]) f[x] = find(f[x]);
	return f[x];
}

void merge(int a, int b) {
    a = find(a); b = find(b);
    if(a == b) return ;
    f[b] = a;
}

int qsmi(int a, int b, int mod){
	int res = 1; while (b) {if (b & 1) res = res * a % mod; b >>= 1; a = a * a % mod;} 
	return res;
}


void solve(){

	cin >> n >> m;
	
	for (int i = 0; i <= n * 2; i ++) f[i] = i;
	
 	for (int i = 1; i <= n; i ++){ cin >> s[i]; s[i] = " " + s[i]; }
	for (int i = 1; i <= m; i ++) {
		int sum = 0;
		for (int j = 1; j <= n; j ++) sum += (s[j][i] == '1');
		if (sum > 2){ cout << 0 << endl; return ; }
	}
	
	
	for (int i = 1, r = m; i <= r; i ++, r --){
		vector<int> mr[2];
		for (int j = 1; j <= n; j ++){
			if (s[j][i] == '1') mr[0].push_back(j);
			if (s[j][r] == '1') mr[1].push_back(j); 
		}
		
		if (mr[0].size() == 2) merge(mr[0][0], mr[0][1] + n), merge(mr[0][1], mr[0][0] + n);
		if (mr[1].size() == 2) merge(mr[1][0], mr[1][1] + n), merge(mr[1][1], mr[1][0] + n);
		for (auto o1 : mr[0]) for (auto o2 : mr[1]) {
			merge(o1, o2), merge(o1 + n, o2 + n);
			// cout << i << ' ' << o1 << ' ' << o2 << endl;
		}
	}
	
	for (int i = 1; i <= n; i ++){
		s[i] = "";
		if (f[find(i)] == f[find(i + n)]) {cout << 0 << endl; return ; }
	}
	
	int ans = 0;
	for (int i = 1; i <= 2 * n; i ++) ans += (f[i] == i);
	ans /= 2;
	
	
	cout << qsmi(2, ans, mod) << "\n";
}

int main(){
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t = 1;
    std::cin >> t;
    while (t--) solve();
    return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 5ms
memory: 35228kb

input:

3
3 5
01100
10001
00010
2 1
1
1
2 3
001
001

output:

4
0
2

result:

ok 3 number(s): "4 0 2"

Test #2:

score: 0
Accepted
time: 20ms
memory: 36496kb

input:

15613
10 10
0000000000
0000000000
0000000000
0000000000
0000000000
0000000000
0000000000
0000000000
0000000000
0000000000
15 8
00000000
00000000
00000000
00000000
00000000
00000000
00000000
00000000
00000000
00000000
00000000
00000000
00000000
00000000
00000000
1 5
00000
5 9
000000000
000000000
0000...

output:

1024
32768
2
32
32768
128
32
16
16
2
16384
16384
128
128
32768
8192
128
64
16384
2
4
2
4096
16
4096
1024
32768
32768
16384
8
128
2
16
4096
8192
32768
8192
8192
16
16384
16384
256
128
8
256
8
4096
512
2
4
32
32
2
64
512
1024
32768
32768
2
64
16384
16
8192
16
256
16
64
8192
8192
64
1024
2
32768
2
4
51...

result:

ok 15613 numbers

Test #3:

score: 0
Accepted
time: 16ms
memory: 35248kb

input:

15759
9 6
000000
000000
000000
000000
000000
000000
000000
000000
000000
5 15
010000000000000
000000000000000
000000000000000
000100000000000
000100000000000
14 12
000000000000
000000000000
000000000000
000000000000
000000000000
000000000000
000000000000
000000000000
000000000000
000000000000
000000...

output:

512
16
16384
512
1024
4096
32768
4
2
512
512
512
512
8
2
256
16
4096
512
64
16
4096
512
32
32768
8192
32
2048
128
16
4096
64
32768
256
32
16384
8
512
32
2048
8
16
1024
2048
128
64
32
8
512
8
8192
256
8192
32768
2
8
512
512
256
32
2
2048
8192
8
64
8
2
16384
32768
32768
1024
4096
16384
16384
128
256
4...

result:

ok 15759 numbers

Test #4:

score: 0
Accepted
time: 23ms
memory: 36960kb

input:

15734
3 6
000101
010000
001110
5 7
0010010
1000000
0101000
0000000
0000000
10 9
000000000
100000000
000000000
000000000
000010000
000000001
000000000
000000000
000000000
000000000
5 14
10000000000000
00001001000000
00000100000000
00000000000000
00000100000000
5 14
00000000000000
00010000000100
00000...

output:

0
16
512
16
32
4096
0
256
0
0
0
0
4096
8
1024
128
8192
0
128
0
2
0
0
32
64
0
0
0
4096
64
8
8
32
128
64
4096
2
512
16384
4
2
0
0
32
0
4096
8
0
8192
256
256
64
0
32
0
32
0
256
4
16384
1024
4
0
16
256
0
2048
64
8
0
0
32768
2048
512
2048
2
0
8192
0
2
2048
16
512
256
1024
0
0
2
32
512
16384
0
32
1024
102...

result:

ok 15734 numbers

Test #5:

score: 0
Accepted
time: 15ms
memory: 35108kb

input:

15616
14 3
000
000
000
000
100
000
000
000
000
000
001
001
001
000
15 5
00000
00000
00010
00000
00000
01000
00000
00000
00000
00001
00100
00000
00000
00000
10000
9 14
00000000000000
00000000000000
00100000010000
00001000100000
01010010000010
00000000000000
01000000000010
00100011000001
0000000000000...

output:

0
8192
0
64
0
512
0
8192
0
512
0
0
64
0
0
256
0
512
0
0
16
0
2048
0
256
0
1024
0
0
2
2
0
64
32
0
2
2
512
16
0
2
4
8192
0
0
1024
256
8
0
32
4
0
0
0
0
0
1024
4096
0
16384
32
0
2
4096
2
512
0
0
0
64
0
0
0
0
2
0
128
256
16
2
128
0
8
2
16384
0
0
2
0
0
0
128
0
0
0
0
0
2
4096
512
0
0
2
0
256
0
2
0
0
0
8
0
...

result:

ok 15616 numbers

Test #6:

score: 0
Accepted
time: 15ms
memory: 36304kb

input:

15525
5 1
1
0
0
0
0
14 15
000000000000000
000001000010000
000000000000000
000000000000000
000110000000000
000000000000001
000000000000000
000010000010000
000000000000000
001010000000000
000101000000000
000000000000100
000000000000000
000100010001000
14 15
000000000000000
000000000000000
000000000010...

output:

32
0
0
0
0
0
0
2
2
16384
0
0
0
2
0
0
0
0
32
0
2048
0
0
256
4096
0
0
512
0
0
0
0
16
0
0
0
0
0
0
0
1024
0
0
0
0
0
0
0
0
0
128
0
0
0
512
0
0
0
0
2
8
0
0
0
16
1024
0
0
0
32
8192
0
0
0
0
0
4
0
0
0
128
4
0
0
2048
0
0
2
32768
0
0
4096
0
2
0
0
0
8
2
0
0
0
0
32
0
0
0
0
0
2
0
8192
4096
0
0
0
0
512
0
0
0
4
0
0...

result:

ok 15525 numbers

Test #7:

score: 0
Accepted
time: 7ms
memory: 35556kb

input:

15547
5 7
1001011
0011001
1101011
0011011
0101011
3 14
11110100111110
01110111011111
11011111110111
4 4
1100
1110
0110
0101
9 9
000000000
101000100
001100100
100001000
000000010
100100000
010110000
000100110
110100000
5 8
10000001
10101011
11101010
01011110
10100111
12 12
000000100000
000000000010
0...

output:

0
0
0
0
0
0
2
0
0
0
0
0
16
0
2
0
0
0
2
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
2
2
0
0
0
0
2
0
0
0
0
0
0
0
0
0
16
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
2
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
2
0
0
0
0
0
0
0
0
0
0
2
0
0
0
0
2
0
0
0
0
0
0
2
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
2
...

result:

ok 15547 numbers

Test #8:

score: 0
Accepted
time: 11ms
memory: 35952kb

input:

15626
8 11
10000010011
01100000010
00000100010
10000010000
00001000000
10100000100
00101010011
00000011000
11 12
101000001000
000010010100
010001100001
000110101010
100010100000
100010000100
001100100000
010000100111
000011011101
000110010000
000000000000
15 8
00001000
00000000
00000000
00100000
000...

output:

0
0
0
2
0
1024
0
0
0
0
0
0
0
0
512
0
0
0
0
0
0
0
0
0
0
2
0
0
0
0
0
0
0
0
0
0
0
0
0
2
0
0
0
16
0
32768
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
4096
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
2
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1024
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 15626 numbers

Test #9:

score: 0
Accepted
time: 18ms
memory: 36708kb

input:

15537
5 1
0
0
0
1
0
10 6
000000
000000
000010
000000
000000
000100
000000
100000
000000
000000
8 3
001
010
000
000
000
000
000
000
3 15
000000001000000
000010000000110
000000000000000
11 3
000
000
000
100
000
000
000
000
000
000
010
1 12
000000110100
3 7
0000010
0000001
0010000
8 1
0
0
0
0
1
0
0
0
1...

output:

32
1024
256
8
2048
2
8
256
2048
64
16384
32
8
4
2048
256
2048
8
32
128
16
32768
256
4096
256
64
2
128
8192
64
16
32768
64
8
1024
128
4096
32
4
16
4
2
8
128
2
1024
2048
1024
16384
256
128
1024
64
512
2048
1024
256
64
32
32
2048
4096
1024
32768
4
4096
256
1024
8
8192
64
16384
2048
2048
16384
8
8192
16...

result:

ok 15537 numbers

Test #10:

score: 0
Accepted
time: 15ms
memory: 35808kb

input:

15581
4 4
0010
0001
0000
0000
9 14
00000000000000
00000000010000
00000000000000
10000001000000
00000100000010
00010000000000
00000000000000
00000000001000
00000000000100
6 11
00000000000
00000001000
01001000100
00000000000
00000000000
00000100001
14 13
0000000010001
0000000000000
0000000000000
00100...

output:

16
256
64
16384
16
32
32
64
16384
16384
2
16384
8
8192
8192
4096
128
32768
2
32
128
2048
32
32768
4096
2048
128
8
32768
256
256
16
256
4096
4
32768
4
16384
4
4
128
8192
4096
8192
2
8192
4096
2048
16384
1024
512
64
512
4096
2048
1024
2048
1024
8
16
16
1024
8
32
2
2048
1024
1024
16384
16384
64
512
512...

result:

ok 15581 numbers

Test #11:

score: 0
Accepted
time: 22ms
memory: 36388kb

input:

15614
12 9
000000001
000000100
000000000
000000000
000000000
000000000
000000010
010010000
000000000
000100000
000000100
000000001
5 5
01010
00000
10100
00000
00001
15 6
000000
000000
000000
000000
011001
000000
000000
000000
000000
000000
000000
000000
000000
000000
000000
2 7
1100000
0110001
13 5
...

output:

512
16
32768
0
4096
0
16384
2
8
8192
32
4
1024
0
16
8
4
64
0
2
2
2
1024
128
128
128
2
32
1024
32
1024
16
64
64
128
1024
512
0
4096
2
32
1024
4096
256
4
2
4096
2
32
64
2
2
0
0
128
16
16
16
4096
1024
2048
16
256
16
16
64
0
1024
0
4096
2
2
16
4
4
8192
1024
512
0
256
2
8
128
128
64
16
128
4096
64
1024
2...

result:

ok 15614 numbers

Test #12:

score: 0
Accepted
time: 18ms
memory: 36588kb

input:

15569
11 3
000
000
000
000
000
000
100
000
000
010
000
2 11
00010000100
11000001101
7 13
0000000000010
0000000100000
1010010000000
0000001001000
0100000000100
1000100000000
0000100000000
12 6
000100
000001
000000
000000
000000
010000
000001
000000
000010
000100
000000
000000
9 6
000000
001000
000010...

output:

2048
0
4
512
64
16384
512
1024
4096
32
256
16
16384
0
512
8192
4096
4
128
4
8
512
1024
8
0
4096
4
4
128
2
4
64
4
512
128
64
16
0
4096
128
1024
0
4
2
0
16
64
256
1024
2048
256
0
4
8
8
16
256
512
256
0
2
2
2048
256
512
2048
4096
512
2048
16
0
1024
4
16
2
8192
1024
32
4
1024
256
32
4096
32
16
32
128
12...

result:

ok 15569 numbers

Test #13:

score: 0
Accepted
time: 23ms
memory: 35560kb

input:

15535
9 13
0000100000001
0000000000100
0000000000000
1000000100010
0000001000000
0001000000000
0000000000000
0000000000010
0001000000000
8 11
00000100100
00000000000
01000000000
10001000100
00010001000
10000000000
00000010000
01000000000
5 13
1000100000000
0001000010110
0000000100000
0001000100110
0...

output:

64
16
2
16384
2
8
8
8
2048
4096
0
256
0
4096
0
0
2
2
128
1024
16384
4
512
8
512
0
1024
2048
32
16
4
4096
0
8
2048
4
256
4
64
4
0
128
8192
4096
512
2
64
8
1024
8
8
16
32
1024
16
1024
1024
8192
4
16384
0
4
256
2
64
8192
2
2
16
8192
0
64
16
0
8
0
2
4096
64
0
32
128
2
2
2
8
0
32
16
16384
2048
64
1024
4
...

result:

ok 15535 numbers

Test #14:

score: 0
Accepted
time: 15ms
memory: 35696kb

input:

15665
15 14
00000100100000
00000000001000
00000000000000
00001001000000
00000000000000
00000000000000
11000000000000
00000000000000
01000000000100
00000000000100
00000000000000
00000000000000
00000000000000
00000000010000
00000001001000
3 13
0010000010110
1101000100001
0001010000000
6 6
000100
00000...

output:

1024
0
32
2
256
256
4096
0
16384
16
64
16
256
2
2
0
256
2048
128
2
2048
2
8
2
2
4096
64
2
8
1024
0
128
512
64
512
64
128
4
256
16
128
16
2
4096
32
32
2
0
0
256
32
2
128
64
256
512
0
2
1024
0
0
512
4096
4
1024
0
8192
2
512
2048
64
0
0
64
0
32768
128
2
2048
512
16384
32
0
8
2
1024
2048
2
2048
4096
2
8...

result:

ok 15665 numbers

Test #15:

score: 0
Accepted
time: 7ms
memory: 35692kb

input:

68
835 480
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

0
0
0
0
0
524288
0
0
0
0
524288
0
0
0
0
0
0
0
0
262144
262144
0
262144
524288
1048576
131072
262144
262144
0
262144
0
0
524288
0
0
0
524288
0
0
65536
0
1048576
131072
524288
131072
0
131072
131072
0
0
131072
0
0
262144
0
65536
0
131072
0
0
0
0
262144
262144
0
0
524288
0

result:

ok 68 numbers

Test #16:

score: 0
Accepted
time: 4ms
memory: 36964kb

input:

45
249 416
0000000000000000000000000000000000000000000000000000000000100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
262144
0
0
0
0
131072
0
0
262144
131072
262144
262144
0
0
0
0
0
0
0

result:

ok 45 numbers

Test #17:

score: 0
Accepted
time: 0ms
memory: 36580kb

input:

59
60 930
00000000000000000000000000000000000000000000000000000000000000000000010000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001000001000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
65536
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0

result:

ok 59 numbers

Test #18:

score: -100
Wrong Answer
time: 4ms
memory: 35464kb

input:

58
902 434
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

0
0
0
0
16384
0
0
0
0
32768
16384
8192
32768
32768
0
0
8192
0
8192
16384
8192
2048
8192
4096
8192
16384
0
8192
4096
8192
32768
4096
32768
131072
32768
8192
0
16384
8192
32768
0
1024
16384
4096
8192
16384
8192
8192
32768
16384
8192
4096
16384
8192
8192
8192
16384
8192

result:

wrong answer 1st numbers differ - expected: '716352531', found: '0'