CSES - Datatähti 2019 alku - Results
Submission details
Task:Ruudukko
Sender:jarvenp
Submission time:2019-01-07 17:24:17 +0200
Language:C++
Status:READY
Result:100
Feedback
groupverdictscore
#1ACCEPTED31
#2ACCEPTED14
#3ACCEPTED55
Test results
testverdicttimegroup
#1ACCEPTED0.01 s1details
#2ACCEPTED0.01 s1details
#3ACCEPTED0.01 s1details
#4ACCEPTED0.03 s1details
#5ACCEPTED0.02 s1details
#6ACCEPTED0.02 s1details
#7ACCEPTED0.02 s1details
#8ACCEPTED0.01 s1details
#9ACCEPTED0.03 s1details
#10ACCEPTED0.02 s1details
#11ACCEPTED0.03 s2details
#12ACCEPTED0.01 s2details
#13ACCEPTED0.03 s2details
#14ACCEPTED0.07 s2details
#15ACCEPTED0.21 s2details
#16ACCEPTED0.41 s2details
#17ACCEPTED0.55 s2details
#18ACCEPTED0.57 s2details
#19ACCEPTED0.56 s2details
#20ACCEPTED0.57 s2details
#21ACCEPTED0.74 s3details
#22ACCEPTED0.03 s3details
#23ACCEPTED0.02 s3details
#24ACCEPTED0.02 s3details
#25ACCEPTED0.04 s3details
#26ACCEPTED0.48 s3details
#27ACCEPTED0.03 s3details
#28ACCEPTED0.03 s3details
#29ACCEPTED0.03 s3details
#30ACCEPTED0.03 s3details

Code

#include <bits/stdc++.h>
#include <stdint.h>
using namespace std;
int64_t n;
int64_t taikaluvut[501];
const int64_t M = (1e9+7);
int64_t fact(int64_t val){
int64_t ans=1;
for(int64_t i=1; i<=val; i++){
ans *= i;
ans %=M;
}
return ans;
}
int64_t potenssi(int64_t a, int64_t b){
if(b == 1){
return a;
}
int64_t v = potenssi(a,b/2);
v*=v;
v %= M;
if(b%2 == 1){
v *= a;
v %= M;
}
return v;
}
int64_t modulo(int64_t a, int64_t b){
return ((a%M)*potenssi(b,M-2))%M;
}
int64_t factDiv(int64_t val1, int64_t val2, int64_t val3){
/*if(val2 < val3){
int64_t temp = val3;
val3 = val2;
val2 = temp;
}
int64_t factors[501];
for(int64_t i=0; i<501; i++){
factors[i] = 0;
}
factors[1] = 1;
for(int64_t i=val2+1; i<=val1; i++){
for(int64_t i2=0; primes[i][i2] != -1; i2++){
factors[primes[i][i2]]++;
}
}
for(int64_t i=2; i<=val3; i++){
for(int64_t i2=0; primes[i][i2] != -1; i2++){
factors[primes[i][i2]]--;
}
}
int64_t ans = 1;
for(int64_t i=1; i<=val1; i++){
for(int64_t i2=0; i2<factors[i]; i2++){
ans*= i;
ans %= M;
}
}
return ans;*/
return modulo(fact(val1),(fact(val2)*fact(val3))%M);
}
int64_t perm(int64_t howMany, int64_t size){
if(howMany > size){
return 0;
}
//return((fact(size)/(fact(howMany)*fact(size-howMany)))%M);
return (factDiv(size, howMany, (size-howMany)));
}
int64_t solutions(int64_t size, int64_t blocks){
if(size < blocks){
return 0;
}
int64_t ans = (int64_t)taikaluvut[size];
for(int64_t i=1; i <= (size-blocks); i++){
ans += (int64_t)(perm(i,(size-blocks))*(int64_t)taikaluvut[size-i])%M;
ans %= M;
}
return ans;
}
int main(){
/* for(int64_t i=1; i<501; i++){
int64_t num = i;
int64_t index = 0;
for(int64_t i2=2; num > 1; i2++){
while(num%i2 == 0){
num/= i2;
primes[i][index] = i2;
index++;
}
}
primes[i][index] = -1;
}
primes[1][0] = 1;
primes[1][1] = -1;*/
taikaluvut[0] = 1;
taikaluvut[1] = 0;
taikaluvut[2] = 1;
for(int64_t i=3; i<501; i++){
taikaluvut[i] = (((taikaluvut[i-1]+taikaluvut[i-2])%M)*(i-1))%M;
}
cin >> n;
char goal[505][505];
for(int64_t i=0; i<n; i++){
cin >> goal[i];
}
int64_t aAmount = 0;
for(int64_t i=0; i<n; i++){
for(int64_t i2=0; i2<n; i2++){
if(goal[i][i2] == 'A'){
aAmount++;
}
}
}/*
int64_t bAmount = 0;
for(int64_t i=0; i<n; i++){
for(int64_t i2=0; i2<n; i2++){
if(goal[i][i2] == 'B'){
bAmount++;
}
}
}*/
int64_t xSize = n-aAmount;
int64_t ySize = n-aAmount;
int64_t aSize = n-aAmount;
int64_t extraB = 0;
int64_t taulSize = n;
for(int64_t i=0; i<n; i++){
for(int64_t i2=0; i2<n; i2++){
if(goal[i][i2] == 'B'){
int64_t aX = 0;
int64_t aY = 0;
for(int64_t i3=0; i3<n; i3++){
if(goal[i][i3] == 'A'){
aX = 1;
goal[i][i3] = 'C';
break;
}
else if(goal[i][i3] == 'C'){
aX = 2;
break;
}
}
for(int64_t i3=0; i3<n; i3++){
if(goal[i3][i2] == 'A'){
aY = 1;
goal[i3][i2] = 'C';
break;
}
else if(goal[i3][i2] == 'C'){
aY = 2;
break;
}
}
taulSize--;
if((aY==0) && (aX==0)){
xSize--;
ySize--;
extraB++;
}
else if((aY!=0)&&(aX!=0)){
if(aY == 1){
aAmount--;
}
if(aX == 1){
aAmount--;
}
}
else if(aY == 1){
aAmount--;
xSize--;
}
else if(aY == 2){
xSize--;
}
else if(aX==1){
aAmount--;
ySize--;
}
else if(aX == 2){
ySize--;
}
}
}
}
// cout << aAmount<<" "<< xSize<<" " << ySize<<" "<<aSize<<" "<<extraB<<" "<<taulSize<<"\n";
if(xSize < ySize){
int64_t temp = xSize;
xSize = ySize;
ySize = temp;
}
int64_t ans=0;
for(int64_t i=0; i <= ySize; i++){
// uint64_t b = ((fact(ySize)/fact(ySize-i))*perm(i,xSize))%M;
int64_t b = (factDiv(ySize,(ySize-i),1)*perm(i,xSize))%M;
// cout <<b <<"\n";
int64_t tempY = ySize-i;
int64_t tempX = xSize-i;
int64_t temp = 0;
for(int64_t i2=0; (i2 <= tempX)&&(i2 <= aAmount); i2++){
if((taulSize-ySize-(aAmount-i2)) >= tempX){
int64_t temp1 = (((perm(i2, aAmount)*(perm(tempX-i2,taulSize-ySize-aAmount)))%M)*fact(tempX))%M;
for(int64_t i3=0; (i3 <= tempY)&& (i3 <= (aAmount-i2)); i3++){
if((taulSize-xSize-(aAmount-i2-i3)) >= tempY){
int64_t temp2 = (((perm(i3,aAmount-i2)*(perm(tempY-i3,taulSize-xSize-(aAmount-i2))))%M)*fact(tempY))%M;
temp += ((((temp1*temp2)%M)*solutions(taulSize-i-tempX-tempY, aAmount-i2-i3))%M);
temp %= M;
}
}
}
}
// cout <<i<<" "<<b<<" "<< temp<<"\n";
ans += ((((b*temp)%M)*solutions(aSize, i+extraB))%M);
ans %= M;
}
cout <<ans<<"\n";
}

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