QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#351786 | #1185. To argue, or not to argue | Rong7 | AC ✓ | 372ms | 389284kb | C++14 | 4.0kb | 2024-03-12 14:58:44 | 2024-03-12 14:58:44 |
Judging History
answer
// Not afraid to dark.
#include <bits/stdc++.h>
using namespace std;
#define int long long
namespace io {
int read_pos, read_dt; char read_char;
inline int read (int &p = read_pos){
p = 0, read_dt = 1; read_char = getchar ();
while (! isdigit (read_char)){
if (read_char == '-')
read_dt = - 1;
read_char = getchar ();
}
while (isdigit (read_char)){
p = (p << 1) + (p << 3) + read_char - 48;
read_char = getchar ();
}
return p = p * read_dt;
}
int write_sta[65], write_top;
inline void write (int x){
if (x < 0)
putchar ('-'), x = - x;
write_top = 0;
do
write_sta[write_top ++] = x % 10, x /= 10;
while (x);
while (write_top)
putchar (write_sta[-- write_top] + 48);
}
int llen;
inline int get_string (char c[], int &len = llen){
len = 0;
read_char = getchar ();
while (read_char == ' ' || read_char == '\n' || read_char == '\r')
read_char = getchar ();
while (read_char != ' ' && read_char != '\n' && read_char != '\r'){
c[++ len] = read_char;
read_char = getchar ();
}
return len;
}
}
const int N = 12, NM = 144, mod = 1e9 + 7;
int n, m, c;
char s[NM][NM], tmps[NM][NM];
int dp[NM + 5][NM + 5][2 << N];
int res[NM + 5];
int inv[NM + 5], inj[NM + 5], jc[NM + 5];
inline int Qpow (int a, int p){
int res = 1;
while (p > 0){
if (p & 1)
res = res * a % mod;
a = a * a % mod;
p >>= 1;
}
return res;
}
inline int C (int a, int b){
return jc[a] * inj[b] % mod * inj[a - b] % mod;
}
inline void AFrAYuRmbrM (){
int avl = 0;
io::read (n), io::read (m), io::read (c);
for (int i = 0;i < n;++ i){
scanf ("\n%s", s[i]);
for (int j = 0;j < m;++ j)
if (s[i][j] != 'X')
++ avl;
}
if (n < m){
for (int i = 0;i < n;++ i)
for (int j = 0;j < m;++ j)
tmps[j][i] = s[i][j];
swap (n, m);
for (int i = 0;i < n;++ i)
for (int j = 0;j < m;++ j)
s[i][j] = tmps[i][j];
}
for (int i = 0;i <= n * m;++ i)
for (int j = 0;j <= c;++ j)
for (int k = 0;k < (1 << m);++ k)
dp[i][j][k] = 0;
dp[0][0][0] = 1;
for (int i = 0;i < n * m;++ i)
for (int j = 0;j <= c;++ j)
for (int k = 0;k < (1 << m);++ k)
if (dp[i][j][k]){
int x = i / m, y = i % m;
if (k >> y & 1){
if (s[x][y] != 'X')
(dp[i + 1][j][k ^ (1 << y)] += dp[i][j][k]) %= mod;
} else {
if (s[x][y] != 'X'){
if (j < c)
(dp[i + 1][j + 1][k ^ (1 << y)] += dp[i][j][k]) %= mod;
if (y && (k >> (y - 1) & 1))
(dp[i + 1][j][k ^ (1 << (y - 1))] += dp[i][j][k]) %= mod;
}
(dp[i + 1][j][k] += dp[i][j][k]) %= mod;
}
}
for (int i = 0;i <= c;++ i)
res[i] = dp[n * m][i][0];
int Ans = 0;
for (int i = 0, v = 1;i <= c;++ i, v = - v){
int rs = C (c, i) * jc[i] % mod * res[i] % mod;
for (int j = 0;j < c - i;++ j)
rs = rs * C (avl - 2 * (i + j), 2) % mod;
Ans = (Ans + mod + v * rs % mod) % mod;
}
io::write (Ans * Qpow (2, c) % mod), puts ("");
return ;
}
signed main (){
inv[1] = inj[0] = inj[1] = jc[0] = jc[1] = 1;
for (int i = 2;i <= NM;++ i){
inv[i] = inv[i - mod % i] * (mod / i + 1) % mod;
inj[i] = inj[i - 1] * inv[i] % mod;
jc[i] = jc[i - 1] * i % mod;
}
int T = io::read ();
while (T --)
AFrAYuRmbrM ();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 10020kb
input:
2 2 2 2 .. .. 4 4 3 X.X. .... .X.. ...X
output:
8 347040
result:
ok 2 number(s): "8 347040"
Test #2:
score: 0
Accepted
time: 372ms
memory: 389284kb
input:
96 1 144 8 ................................................................................................................................................ 144 1 31 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ....
output:
517668733 268886110 64664470 926220403 0 0 372341012 839870997 115795952 169129272 928175112 399452284 981581814 563968454 82030165 770277954 161484719 374884294 988612558 269599606 838995341 614914000 779550646 19224822 195892020 368899964 857064056 437999888 225342223 836336621 981420655 30328633 ...
result:
ok 96 numbers