QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #53568 | #1790. 机器人游戏 | not_so_organic | 100 ✓ | 92ms | 5652kb | C++11 | 8.0kb | 2022-10-05 13:28:01 | 2022-10-05 13:28:09 |
Judging History
answer
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int N = 32, M = 1005, mod = 1e9 + 7;
int n, m, ans;
int a[M][105], len[M];
int pw2[M], pw3[M];
unsigned s[N][M][4];
int f[1 << 16], h[1 << 16], g1[1 << 16], g3[1 << 16];
int add(int x, int y) {
return x + y < mod ? x + y : x + y - mod;
}
int sub(int x, int y) {
return x < y ? x + mod - y : x - y;
}
void init() {
for (int i = 1; i <= m; i++) {
a[i][0] = 2;
char s[105];
cin >> (s + 1);
int l = strlen(s + 1);
for (int j = 1; j <= l; j++) {
if (s[j] == 'R')
a[i][++len[i]] = 2;
else if (s[j] == '0')
a[i][len[i]] = 0;
else if (s[j] == '1')
a[i][len[i]] = 1;
else {
if (a[i][len[i]] < 2)
a[i][len[i]] = 1 - a[i][len[i]];
else
a[i][len[i]] = 2 + 3 - a[i][len[i]];
}
}
}
for (int i = 0; i < n; i++)
for (int j = 1; j <= m; j++)
for (int t = 0; t < n; t++) {
if (t + len[j] < i || t > i)
s[i][j][2] |= 1u << t;
else
s[i][j][a[j][i - t]] |= 1u << t;
}
}
void add(int *g, int s, int r, int t, int v) {
if (s >> r & 1)
g[s & t] += v;
}
void bitw(int *a, int n) {
for (int l = 1; l < n; l <<= 1)
for (int *f = a; f != a + n; f += l)
for (int j = 0; j < l; j++, f++)
*f += f[l];
}
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> n >> m;
init();
pw2[0] = pw3[0] = 1;
for (int i = 1; i <= m; i++) {
pw2[i] = add(pw2[i - 1], pw2[i - 1]);
pw3[i] = 3ll * pw3[i - 1] % mod;
}
for (int r = 0; r < (n + 1) / 2; r++) {
int ban = 0, p = (1 << (r + 1)) - 1;
for (int j = 1; j <= m; j++)
if (r + len[j] >= n)
ban++;
fill(f, f + (1 << r), 1);
for (int i = 0; i < n; i++) {
memset(g1, 0, (1 << r) << 2), memset(g3, 0, (1 << r) << 2);
for (int j = 1; j <= m; j++) {
if (r + len[j] >= n)
continue;
int a = s[i][j][0] & p;
int b = s[i][j][1] & p;
int c = s[i][j][2] & p;
int d = s[i][j][3] & p;
int t = (1 << r) - 1;
g1[t]++;
add(g1, p ^ a ^ c, r, t, -1);
add(g1, p ^ a ^ d, r, t, -1);
add(g1, p ^ b ^ c, r, t, -1);
add(g1, p ^ b ^ d, r, t, -1);
add(g1, p ^ a ^ b ^ c, r, t, 1);
add(g1, p ^ a ^ b ^ d, r, t, 1);
add(g1, p ^ a ^ c ^ d, r, t, 1);
add(g1, p ^ b ^ c ^ d, r, t, 1);
add(g3, a, r, t, 1);
add(g3, b, r, t, 1);
add(g3, c, r, t, 1);
add(g3, d, r, t, 1);
}
bitw(g1, 1 << r), bitw(g3, 1 << r);
for (int s = 0; s < (1 << r); s++)
f[s] = 1ll * f[s] * pw2[m - ban - g1[s] - g3[s]] % mod * pw3[g3[s]] % mod;
}
for (int s = 0; s < (1 << r); s++)
if (__builtin_parity(s))
ans = sub(ans, f[s]);
else
ans = add(ans, f[s]);
}
for (int r = (n + 1) / 2; r < n; r++) {
int ban = 0, k = n - r;
for (int j = 1; j <= m; j++)
if (r + len[j] >= n)
ban++;
for (int s = 0; s < (1 << k); s++)
if (__builtin_parity(s))
f[s] = mod - 1;
else
f[s] = 1;
for (int i = 0; i < k; i++) {
int p = (1 << k) - 1;
memset(g1, 0, (1 << k) << 2), memset(g3, 0, (1 << k) << 2);
for (int j = 1; j <= m; j++) {
if (r + len[j] >= n)
continue;
int a = s[i][j][0] & p;
int b = s[i][j][1] & p;
int c = s[i][j][2] & p;
int d = s[i][j][3] & p;
int t = (1 << k) - 1;
g1[t]++;
g1[p ^ a ^ d]--;
g1[p ^ b ^ d]--;
g1[c]++;
g3[c]++;
}
bitw(g1, 1 << k), bitw(g3, 1 << k);
for (int s = 0; s < (1 << k); s++)
f[s] = 1ll * f[s] * pw2[m - ban - g1[s] - g3[s]] % mod * pw3[g3[s]] % mod;
}
for (int i = k; i < r; i++) {
for (int s = 0; s < (1 << k); s++)
f[s | 1 << k] = sub(0, f[s]);
int p = (1 << (k + 1)) - 1;
memset(g1, 0, (1 << (k + 1)) << 2), memset(g3, 0, (1 << (k + 1)) << 2);
for (int j = 1; j <= m; j++) {
if (r + len[j] >= n)
continue;
int tp = (1 << (i - k)) - 1;
int a = s[i][j][0] >> (i - k) & p;
int b = s[i][j][1] >> (i - k) & p;
int c = s[i][j][2] >> (i - k) & p;
int d = s[i][j][3] >> (i - k) & p;
if (s[i][j][0] & tp)
a |= 1;
if (s[i][j][1] & tp)
b |= 1;
if (s[i][j][2] & tp)
c |= 1;
if (s[i][j][3] & tp)
d |= 1;
int t = (1 << (k + 1)) - 1;
g1[t]++;
g1[p ^ a ^ d]--;
g1[p ^ b ^ d]--;
g1[c]++;
g3[c]++;
}
bitw(g1, 1 << (k + 1)), bitw(g3, 1 << (k + 1));
for (int s = 0; s < (1 << (k + 1)); s++) {
int x = s >> 1 | (s & 1);
h[x] = (h[x] + 1ll * f[s] * pw2[m - ban - g1[s] - g3[s]] % mod * pw3[g3[s]]) % mod;
f[s] = 0;
}
memcpy(f, h, (1 << k) << 2), memset(h, 0, (1 << k) << 2);
}
for (int i = r; i < n; i++) {
int l = k - (i - r), p = (1 << (l + 1)) - 1;
memset(g1, 0, (1 << l) << 2), memset(g3, 0, (1 << l) << 2);
for (int j = 1; j <= m; j++) {
if (r + len[j] >= n)
continue;
int tp = (1 << (r - l)) - 1;
int a = s[i][j][0] >> (r - l) & p;
int b = s[i][j][1] >> (r - l) & p;
int c = s[i][j][2] >> (r - l) & p;
int d = s[i][j][3] >> (r - l) & p;
if (s[i][j][0] & tp)
a |= 1;
if (s[i][j][1] & tp)
b |= 1;
if (s[i][j][2] & tp)
c |= 1;
if (s[i][j][3] & tp)
d |= 1;
int t = (1 << l) - 1;
g1[t]++;
add(g1, p ^ a ^ c, l, t, -1);
add(g1, p ^ a ^ d, l, t, -1);
add(g1, p ^ b ^ c, l, t, -1);
add(g1, p ^ b ^ d, l, t, -1);
add(g1, p ^ a ^ b ^ c, l, t, 1);
add(g1, p ^ a ^ b ^ d, l, t, 1);
add(g1, p ^ a ^ c ^ d, l, t, 1);
add(g1, p ^ b ^ c ^ d, l, t, 1);
add(g3, a, l, t, 1);
add(g3, b, l, t, 1);
add(g3, c, l, t, 1);
add(g3, d, l, t, 1);
}
bitw(g1, 1 << l), bitw(g3, 1 << l);
for (int s = 0; s < (1 << l); s++) {
h[s >> 1 | (s & 1)] = (h[s >> 1 | (s & 1)] + 1ll * f[s] * pw2[m - ban - g1[s] - g3[s]] % mod * pw3[g3[s]]) %
mod;
f[s] = 0;
}
if (i == n - 1)
ans = add(ans, add(h[0], h[1]));
memcpy(f, h, (1 << (l - 1)) << 2), memset(h, 0, (1 << l) << 2);
}
}
cout << ans;
}
詳細信息
Test #1:
score: 4
Accepted
time: 0ms
memory: 3600kb
input:
1 1 0
output:
3
result:
ok single line: '3'
Test #2:
score: 4
Accepted
time: 0ms
memory: 3640kb
input:
1 1 *
output:
3
result:
ok single line: '3'
Test #3:
score: 4
Accepted
time: 1ms
memory: 3672kb
input:
8 1 RRRR
output:
6561
result:
ok single line: '6561'
Test #4:
score: 4
Accepted
time: 2ms
memory: 3744kb
input:
16 1 1*RR0RRRR1RRR0*R
output:
228047430
result:
ok single line: '228047430'
Test #5:
score: 4
Accepted
time: 40ms
memory: 4704kb
input:
32 1 RRRRRRRRR*R0RRR*R*0RRRRRRRRRR1R*1R*
output:
456286566
result:
ok single line: '456286566'
Test #6:
score: 4
Accepted
time: 44ms
memory: 4792kb
input:
32 1 R11RRR*RR1RR0RRRR1RRRR*0R*RRRR1RRRRR1R*RRR
output:
987597859
result:
ok single line: '987597859'
Test #7:
score: 4
Accepted
time: 0ms
memory: 3788kb
input:
16 5 0RRR0 R*RRR RRRRRR RRR1R0R R1*RRRRRRRR1R1RR1RRR
output:
920870788
result:
ok single line: '920870788'
Test #8:
score: 4
Accepted
time: 41ms
memory: 4832kb
input:
32 5 RRRRRRRR1*RRR R1R*0R1R***1RRRRRRRRR**RRRRR01*01RR0R*R*RRR R0RRRRR0RRR0R0RRR0R*RRRR*RR0RR R1RRRRRRRRR*0RRRR1RR10R*RRR1R11RRRR01* 0R0R0RR0R11RRR0RR0RRR**1*RRR1RRRR0*0RR1R
output:
724757213
result:
ok single line: '724757213'
Test #9:
score: 4
Accepted
time: 40ms
memory: 4832kb
input:
32 5 R1*R*RRRRRRRRRRR01R*R0 1R0RRRR1RR1R***RR0R*RR*RRR*1RR 0 1RRRR0RRRRR1R1RRRR0RRR01R*R01 RRRRR1RRRRRR
output:
339267352
result:
ok single line: '339267352'
Test #10:
score: 4
Accepted
time: 44ms
memory: 4648kb
input:
32 5 RRR*0RR*RR1R1*R10RRRRRR1RRRR1 0RR*RRRRR*R*R0 0RRRR*RRR 0R1RRRRR0RRRRR0RRRR**0RRRRRRRRRRRRRRR RRRR01RR0R1R0R*R1RR10RRRRRRRR0RR*R0RRR1R
output:
305204884
result:
ok single line: '305204884'
Test #11:
score: 4
Accepted
time: 5ms
memory: 4368kb
input:
16 1000 RRRRRR1RRRRR*RRR RRR1RR*0RRR1RRR R0RR11RRR*RRRR0R0R R1 RRR1RRRRRR1RRR10* RR*RRR1RRRRRRRR RR RRRRRRRRR*R R* 1RRR*R00* R0R0R*RRRR RRRRR000RR R1R1R1*RRRRRR* RR1*0*1RRRRRR*RRRRRR RR RRRRRRR*R 0RR*RRRRRRRRRRRR10R RRR*RR1RRRR0RRR*0RRRR R*1R1RRRR1RRRRRRR RRRRRRRRR RRRRR*RRRRR RR0RR10RR11R * 0 R1*RR...
output:
278439170
result:
ok single line: '278439170'
Test #12:
score: 4
Accepted
time: 2ms
memory: 4236kb
input:
16 1000 * RRR0R*0RR *RRRRRRR0RRR1RRR1RRR R*RRRRRR11RRRRRRR1R R R0R 0RRRRRR1RRRRR RR**0*R0R 0***R*R*1R 11RRRRRRRRR1RR1 1RR RR1R RRRRR0R*R10RRR1RRR1R RR1R**RR10 1 RRRRRRRR* R1RRRRRRR0R*RR *RR*R1* R0RR RR1R0RR1*RRRRRRRR1 R RRR1RRRR1*RRRRR*RRR* RRR0RRRRR0RR0R1 RRRRRRRRRRRR R R0RR1RRR1RR1 **RRRRRR1*RRRR1...
output:
937144102
result:
ok single line: '937144102'
Test #13:
score: 4
Accepted
time: 52ms
memory: 5552kb
input:
32 1000 0 * 0 1 0 0 * * 0 0 * 1 * 0 1 * 0 0 1 1 1 1 * 0 1 0 0 1 1 * 1 0 0 1 * 0 0 0 * 1 * 0 * 0 * 0 0 * 0 * * 0 0 1 * 0 * 0 0 1 1 * 0 0 * 1 * * * 0 0 1 0 0 * * * 0 0 0 0 * * * 1 1 * 0 * 0 * 0 * 0 1 * * * * 0 1 0 0 * 0 0 * 0 1 * 0 * * 1 1 * 0 * 0 1 0 * 1 * 1 1 1 * 0 1 * * 1 0 1 1 0 0 0 0 0 0 0 1 * 1 ...
output:
675565814
result:
ok single line: '675565814'
Test #14:
score: 4
Accepted
time: 50ms
memory: 5564kb
input:
32 1000 * * 0 * * * 0 0 * 0 * 1 * * 0 0 1 1 1 0 0 * 0 1 0 * * 0 0 1 1 0 * 1 * * 0 0 1 0 * * 0 0 1 0 0 * * * 1 1 1 1 * 1 0 1 1 * 1 * 0 1 * * * * * 0 0 1 1 1 1 0 1 1 0 1 0 * * * * 1 0 1 0 0 1 0 0 1 1 0 1 * * 1 1 0 0 0 1 * 1 * 0 1 0 0 0 * 0 * 0 0 * 0 0 1 1 0 1 0 0 0 1 * 0 0 * 1 1 0 1 * * 1 1 1 0 1 1 1 ...
output:
969266411
result:
ok single line: '969266411'
Test #15:
score: 4
Accepted
time: 49ms
memory: 5560kb
input:
32 1000 1 0 0 1 0 1 0 * 0 1 1 0 0 1 0 1 0 0 1 0 * 0 * * * 0 0 * 0 1 0 0 0 1 0 0 * 0 0 * * * * 0 * 1 * 0 0 1 1 1 1 0 1 * * * 0 * 1 * 0 * 1 * 0 0 1 * * 1 1 * 0 0 1 1 * * 1 * 0 * * * 0 * 0 1 0 * * * 0 1 0 1 0 0 1 * * 0 0 0 0 1 * 1 1 * * 0 0 1 1 1 0 0 * * 1 * 1 * 1 * * * 0 0 0 1 1 1 0 1 0 * 1 * 1 0 0 1 ...
output:
648679786
result:
ok single line: '648679786'
Test #16:
score: 4
Accepted
time: 46ms
memory: 5568kb
input:
32 1000 R1R0RRRRR0R*R1RRRRR** RRR0R0RR*RRRR 1R*RR0R00RRR 0RRRRRRRRRRR R1RRRRRR0RR1RRR1 R0R RRR0RRRRRR**RRR*0RR0 0 R1RR1RRRRR0 RR0*R0RRRRRRR*1RRR R*1*RRR RRRRRRRRRR*1R00RR*0*RR00 RRRR1RRRRR RRR*RRR1RRR*RRR1RRR R0 1RRRRR*R1RRR*R1 RR1RRRRRR R1110*RRRRR***RRRR1RRRR 0*R00R1RR0RRR RRRRR100RR*RRRRR * 0R1RR...
output:
19340709
result:
ok single line: '19340709'
Test #17:
score: 4
Accepted
time: 53ms
memory: 5560kb
input:
32 1000 RR 1*RRRR1R R0R R0R*RRR*RR**R*R*RRR*RR R R0RRRRR101RRR 0RRR1RRRRR 0*R* RRRRRR0RRR1R0RR0R RRRR01R 1R0RRR0RRRRRR R0R1R **1RRRR1 R1R RR1RRRRRR0RRRRRR R*R11RRRR***RR*RRRR RRR1*0RRRR00*R*RRRR1R RRR *R*RRR RRRRRR*RR1RRR1RRRR RRRRR0RRRRRR RR11RR R1RRRRR R00RR1**RRRRRRRR1RRR *RR0RR*R1*RRRRR01*0R* RR...
output:
484551342
result:
ok single line: '484551342'
Test #18:
score: 4
Accepted
time: 54ms
memory: 5568kb
input:
32 1000 1R1RRRR R0*1RRR1RRRRRRRRRR0R0 0RRR RRR0RR*R*RRR 01RRRR0RRRRR*R0RRR*R RR* *RR1RRRRRRR*R RR1RRR**RRRR0RRRR* R**1RRRR0RRR0R1RR1R1RR1 RRRRR*10R RR*1R1RRRRR1RRR RR RRR**1R1RR1 RRR1RR0RR1*1RRRRR*R0R RRR* RRRRR11RR RRRRR1R*RR R1RRRRR**RR 0R*R10*RR1RRR 11R1R*RRR 1RRRRRR0RRRRRR0**RR R*1RRR1R0RRRRR * ...
output:
907694742
result:
ok single line: '907694742'
Test #19:
score: 4
Accepted
time: 53ms
memory: 5560kb
input:
32 1000 RRRRR0RR0RR RRRR*0RR0RRRRR*R0RR RR0 0RR 0RRRRRRRRRR0RRRR1R RRRR RRR R1RRRRR* RR1RRRRR0RR1 0RRR0 RRRR0RRRRRRRRRRR1 RR*RRR1R*R RRR*R*0RRR RRRRR RRRR1RRRR0R0RR*RR R R*11R1*RRRR RR0RRRR0R0RRRR*1R *RR0RR*R*RRR0 RR*R0*R1R1*RR10RR R*R RRRR 0RRRRRRRR RR001RR R1RRRRR* RR** 1RR10R*R RR1RRRRRRRRRRR* RR...
output:
424231090
result:
ok single line: '424231090'
Test #20:
score: 4
Accepted
time: 51ms
memory: 5652kb
input:
32 1000 1RRRRRRR*RR*RRR*R *RR RRRRRRR1RR01R1*R *11RRR0RR*RR1 RRRRR*R1RRRRRRR 1RR **RRRRR RRRRR1R1RR011R *R*RRR*R0*0R1*RRRRRRRR RRRR*RRRRR00RR RRRRRRR0RRRR0RR1*R1 000RRRRR1RR1R RR RRR0RRRRRR00R RRR1RRRRRRR*00RRRR RRRRRRR0R11RR0RR1 1RRRRR0R10RRR0RRR RRRRR0R1*RRR RRR*RRRRR0RRR*R RRRRR1R0RR RRRRR1RRRRRR...
output:
577668630
result:
ok single line: '577668630'
Test #21:
score: 4
Accepted
time: 49ms
memory: 5560kb
input:
32 1000 R0 0 11RR0RR RRRR0RR010000R RRRRRR*RRRRR0R*RRR RRRR RRRRRRRR R*RRRR1*0R R*RR**RRR0 * RRRR1R1*R1RR0RR01RRR0 RR1R0RR*1*RRRR0R*R* RRR*0RR*RR00RRR*RRR1*R 1R*R10RRRRRRR11RR1 RRRRRRRRRR0RR 0RR*R1R11RR*R*RRRR*R RRR *0R11RRR 1*1R R1R1R*0RR0RRR*00RR1RR1RR1 R1**RRRR1R*RRRRRRRR 1 **RRRR1RRRRR1RRR1*R** ...
output:
819220679
result:
ok single line: '819220679'
Test #22:
score: 4
Accepted
time: 51ms
memory: 5528kb
input:
32 1000 R0RRR00*R1R0R0R00RRRR RR*0RRRRRRRRRRRRR*0RRRRRR RRRRRRRRR 0R10RR1RRRR* RRRRRRR1RRRRRRRRR*RR1RRRRR00RRRRRRR R0RRR RRR1RRRRRR1RRR10*RRRRRR RRR*RRRRR*RR0RR RRRR01RRRRR RRR1RRRRRRRRR1R 0RRR1**RRR1R1R1RRRR*1RR1RRRRRRRR1R0RRRR*RRRR*R R*RRR0RRRRR R*RR1RRRRRRRRR*0RR*RR0R*RRRRRR*R1R1RRRR RR0RR*RRR1R0...
output:
691327935
result:
ok single line: '691327935'
Test #23:
score: 4
Accepted
time: 53ms
memory: 5576kb
input:
32 1000 RRRRRR0*RRRRRRR0RRRRRRRRRRRR RRR0*1RRRR0RRRR RRRRR1R 0R0RRR011RRRRRRRR 0RR0RR*RR*RR*RRRRRRRR* 1RR0RRRRRR**0RR1R0**RR0*RRRR*RRR* RRR00RR1RRR**R* R01RRRR11R0*0R1*RRRRRRRR*RR0R0RR*00R*RR0R1RRRRRR* RRR1RRRRRRRR* RRRRRRRRR*1R*RRR1R0R0*0 R1RR01*RRRRRR RR11RRR1R1R**RRRR*1R*RRR R*RRRRRR0RRRRR00R0RRR...
output:
714451377
result:
ok single line: '714451377'
Test #24:
score: 4
Accepted
time: 92ms
memory: 5492kb
input:
32 1000 RRR0R*R0 RRRRRRRR0RRR*R1R*R00R RRRRRRRRRRR0RR1RRRRRR1RRRR*RRRRRRR00RR RRRRR R0RRRRRRRR1 RRRRRRRRRRR1*R*RRRRRRRR RR*RR*RRR1RRRRRR *R*1RR0RRRRRRRRR*R1RRRRRRRRRRR1R10R*R1R 1 RRRR RR11RRRRRRRR1RRRR1RR1RR RRRRRRRRRR*RRRR*RRRRR*11RR*RRR1RRR10RR 0R1RR0R1R*RRRR*RRRR*1R0RRRRR*RR RRRRRRRR *RRRRRRRRRR0...
output:
426645236
result:
ok single line: '426645236'
Test #25:
score: 4
Accepted
time: 53ms
memory: 5572kb
input:
32 1000 1RR1RRRRRR0RRRRRRRRRR RR1*RRRR1RRRRR*R RR*RRRR11R RRR*0*0RR R0*RRRRRRRRRR0RR0R R0RRRRRR1R0RRR1R RRRRRR*R0RRRR00RRRRR0RRRR1RR1RR RRR*RR*R0*RRRR0RR0RRRRRRR*R10RRRR RRRR00* RRRRRRRRRR*R0RR1RRRR RRRRRR1RRR1*0R*R0*RRRRRRR0RRR*R 10*RRRRRRRR1RR0RRRRRRR0RR0RRR RRRR*0R1RR RRRRRR RR0R1RRRRR*RRRRRRRRRR...
output:
780564072
result:
ok single line: '780564072'
Extra Test:
score: 0
Extra Test Passed