CSES - Datatähti 2019 alku - Results
Submission details
Task:Ruudukko
Sender:ollpu
Submission time:2018-10-03 18:14:11 +0300
Language:Ruby
Status:READY
Result:100
Feedback
groupverdictscore
#1ACCEPTED31
#2ACCEPTED14
#3ACCEPTED55
Test results
testverdicttimegroup
#1ACCEPTED0.40 s1details
#2ACCEPTED0.39 s1details
#3ACCEPTED0.39 s1details
#4ACCEPTED0.40 s1details
#5ACCEPTED0.40 s1details
#6ACCEPTED0.38 s1details
#7ACCEPTED0.39 s1details
#8ACCEPTED0.38 s1details
#9ACCEPTED0.40 s1details
#10ACCEPTED0.40 s1details
#11ACCEPTED0.40 s2details
#12ACCEPTED0.40 s2details
#13ACCEPTED0.40 s2details
#14ACCEPTED0.41 s2details
#15ACCEPTED0.43 s2details
#16ACCEPTED0.42 s2details
#17ACCEPTED0.46 s2details
#18ACCEPTED0.44 s2details
#19ACCEPTED0.46 s2details
#20ACCEPTED0.46 s2details
#21ACCEPTED0.44 s3details
#22ACCEPTED0.45 s3details
#23ACCEPTED0.45 s3details
#24ACCEPTED0.44 s3details
#25ACCEPTED0.44 s3details
#26ACCEPTED0.45 s3details
#27ACCEPTED0.45 s3details
#28ACCEPTED0.44 s3details
#29ACCEPTED0.44 s3details
#30ACCEPTED0.44 s3details

Code

M = Integer(1e9+7)
N = 500
fac = [1]
N.times do |i|
  fac << fac[-1]*fac.size
end

h = Array.new(N+1) { Array.new(N+1, 0) }
nCr = Array.new(N+1) { Array.new(N+1, 0) }
for i in 0..N
  h[i][0] = fac[i]
  nCr[i][0] = 1
end
for i in 1..N
  for j in 1..i
    h[i][j] = (i-1)*h[i-1][j-1]
    h[i][j] += (j-1)*h[i-2][j-2] if j >= 2
    nCr[i][j] = (nCr[i-1][j]+nCr[i-1][j-1])%M
  end
end

n = gets.strip.to_i
ac, bc, r, br, o, u = [0]*6
pos = Array.new(n) { [nil]*4 }
n.times do |i|
  s = gets
  n.times do |j|
    case s[j]
    when 'A'
      ac += 1
      pos[i][0b00] = j
      pos[j][0b01] = i
    when 'B'
      bc += 1
      pos[i][0b10] = j
      pos[j][0b11] = i
    end
  end
end

n.times do |i|
  if !pos[i][0b00] && !pos[i][0b10]
    r += 1
  elsif pos[i][0b00] && pos[i][0b10]
    o += 1 unless pos[pos[i][0b10]][0b01]
  elsif pos[i][0b00]
    br += 1 unless pos[pos[i][0b00]][0b11]
  else
    u += 1 unless pos[pos[i][0b10]][0b01]
  end
end
res = 0
for x in 0..r
  for y in 0..r-x
    next if r-x-y > o
    ml = fac[r]*nCr[o][r-x-y]%M*nCr[u][x]%M*nCr[n-ac-o-u][y]%M
    res += ml*h[n-ac-r][u-x]%M*h[n-bc][br+y]
    res %= M
  end
end

puts res


Test details

Test 1

Group: 1

Verdict: ACCEPTED

input
2
..
..

correct output
2

user output
2

Test 2

Group: 1

Verdict: ACCEPTED

input
2
..
A.

correct output
1

user output
1

Test 3

Group: 1

Verdict: ACCEPTED

input
2
B.
.A

correct output
0

user output
0

Test 4

Group: 1

Verdict: ACCEPTED

input
3
...
...
...

correct output
12

user output
12

Test 5

Group: 1

Verdict: ACCEPTED

input
4
....
....
....
....

correct output
216

user output
216

Test 6

Group: 1

Verdict: ACCEPTED

input
5
.....
.....
.....
.....
...

correct output
5280

user output
5280

Test 7

Group: 1

Verdict: ACCEPTED

input
5
....A
.....
.....
.....
...

correct output
264

user output
264

Test 8

Group: 1

Verdict: ACCEPTED

input
5
B....
.....
.....
.A.B.
...

correct output
22

user output
22

Test 9

Group: 1

Verdict: ACCEPTED

input
5
B.A..
....A
.....
A.B..
...

correct output
2

user output
2

Test 10

Group: 1

Verdict: ACCEPTED

input
5
A.B..
BA...
.B.A.
...BA
...

correct output
1

user output
1

Test 11

Group: 2

Verdict: ACCEPTED

input
10
..........
..........
..........
..........
...

correct output
306442892

user output
306442892

Test 12

Group: 2

Verdict: ACCEPTED

input
50
.................................

correct output
694861480

user output
694861480

Test 13

Group: 2

Verdict: ACCEPTED

input
111
.................................

correct output
555319110

user output
555319110

Test 14

Group: 2

Verdict: ACCEPTED

input
222
.................................

correct output
108372237

user output
108372237

Test 15

Group: 2

Verdict: ACCEPTED

input
333
.................................

correct output
259107857

user output
259107857

Test 16

Group: 2

Verdict: ACCEPTED

input
444
.................................

correct output
19906314

user output
19906314

Test 17

Group: 2

Verdict: ACCEPTED

input
497
.................................

correct output
224313667

user output
224313667

Test 18

Group: 2

Verdict: ACCEPTED

input
498
.................................

correct output
929574601

user output
929574601

Test 19

Group: 2

Verdict: ACCEPTED

input
499
.................................

correct output
600226043

user output
600226043

Test 20

Group: 2

Verdict: ACCEPTED

input
500
.................................

correct output
198353194

user output
198353194

Test 21

Group: 3

Verdict: ACCEPTED

input
499
.................................

correct output
840243733

user output
840243733

Test 22

Group: 3

Verdict: ACCEPTED

input
499
........................A........

correct output
4146290

user output
4146290

Test 23

Group: 3

Verdict: ACCEPTED

input
499
B.........A......................

correct output
173518884

user output
173518884

Test 24

Group: 3

Verdict: ACCEPTED

input
499
...A....B........................

correct output
20044800

user output
20044800

Test 25

Group: 3

Verdict: ACCEPTED

input
499
AB...............................

correct output
2

user output
2

Test 26

Group: 3

Verdict: ACCEPTED

input
500
.................................

correct output
121064146

user output
121064146

Test 27

Group: 3

Verdict: ACCEPTED

input
500
.................................

correct output
848435259

user output
848435259

Test 28

Group: 3

Verdict: ACCEPTED

input
500
.....B........A..................

correct output
296240911

user output
296240911

Test 29

Group: 3

Verdict: ACCEPTED

input
500
.A......B........................

correct output
2196

user output
2196

Test 30

Group: 3

Verdict: ACCEPTED

input
500
...AB............................

correct output
1

user output
1