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

Code

#include <bits/stdc++.h>
#include <stdint.h>
using namespace std;


uint32_t n;
uint64_t counter;
uint32_t taikaluvut[501];

const uint64_t M = (1e9+7);
/*
void taulukot(uint32_t layer, char taul[][505], char goal[][505], uint16_t aUsed, uint16_t bUsed){
  if(layer == n){
    bool match = true;
    for(uint32_t i=0; i<n; i++){
      //  cout << taul[i]<<"\n";
      for(uint32_t i2=0; i2<n; i2++){
	if((taul[i][i2] != goal[i][i2]) && (goal[i][i2] != '.')){
	  match = false;
	  break;
	}
      }
      if(!match){
	break;
      }
    }
    if(match){
      counter++;
    }
    //   cout << "\n";
  }
  else{
    char temp[505][505];
    for(uint32_t i=0; i<n; i++){
      for(uint32_t i2=0; i2<n; i2++){
	temp[i][i2] = taul[i][i2];
      }
      temp[i][n] = 0;
    }
    for(uint32_t i=0; i<n; i++){
      //cout <<"b\n";
      if(((aUsed>>i)&1) == 0){
	//cout << "a\n";
	aUsed = aUsed | (1<<i);
	temp[layer][i] = 'A';
	for(uint32_t i2=0; i2<n; i2++){
	  if((((bUsed>>i2)&1) == 0) && (i2 != i)){
	    // cout << i<<" "<<temp[layer][i]<<"\n";
	    bUsed = bUsed | (1<<i2);
	    temp[layer][i2] = 'B';
	    taulukot(layer+1, temp, goal, aUsed, bUsed);
	    bUsed = bUsed & ~(1<<i2);
	    temp[layer][i2] = '.';
	  }
	}
	aUsed = aUsed & ~(1<<i);
	temp[layer][i] = '.';
      }
    }
  }
}
*/


uint64_t fact(uint16_t val){
  uint64_t ans=1;
  for(uint16_t i=1; i<=val; i++){
    ans *= i;
    ans %=M;
  }
  return ans;
}

unsigned gcd(unsigned u, unsigned v) {
    while ( v != 0) {
        unsigned r = u % v;
        u = v;
        v = r;
    }
    return u;
}

uint64_t factDiv(uint16_t val1, uint16_t val2, uint16_t val3){
  if(val2 < val3){
    uint16_t temp = val3;
    val3 = val2;
    val2 = temp;
  }
  uint16_t factors[501];
  for(uint16_t i=0; i<501; i++){
    factors[i] = 1;
  }
  for(uint16_t i=val2+1; i<=val1; i++){
    factors[i] = i;
  }
  for(uint16_t i=2; i <= val3; i++){
    uint16_t factor=i;
    for(uint16_t i2=val1; factor > 1; i2--){
      uint16_t num = gcd(factor, factors[i2]);
      factor /= num;
      factors[i2] /= num;
    }
  }
  uint64_t ans = 1;
  for(uint16_t i=1; i<=val1; i++){
    ans *= factors[i];
    ans %= M;
  }
  return ans;
}

uint64_t perm(uint16_t howMany, uint16_t size){
  if(howMany > size){
    return 0;
  }
  //return((fact(size)/(fact(howMany)*fact(size-howMany)))%M);
  return (factDiv(size, howMany, (size-howMany)));
}

uint64_t solutions(uint16_t size, uint16_t blocks){
  uint64_t ans = (uint64_t)taikaluvut[size];
  for(uint16_t i=1; i <= (size-blocks); i++){
    ans += (perm(i,(size-blocks))*taikaluvut[size-i])%M;
    ans %= M;
  }
  return ans;
}

int main(){
  /*  while(1){
    uint16_t a,b,c;
    cin >> a>>b>>c;
    cout << factDiv(a,b,c)<<"\n";
  }*/
  taikaluvut[0] = 1;
  taikaluvut[1] = 0;
  taikaluvut[2] = 1;
  for(uint32_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(uint32_t i=0; i<n; i++){
    cin >> goal[i];
  }
  
  
  /*  while(1){
    bool aUsed[n];
    bool bUsed[n];
    for(uint16_t i=0; i<n; i++){
      aUsed[i] = 0;
      bUsed[i] = 0;
    }
    for(uint16_t i=0; i<n; i++){
      for(uint16_t i2=0; i2<n; i2++){
	goal[i][i2] = '.';
      }
    }
    for(uint16_t i=0; i<n; i++){
      bool tempAUsed = false;
      bool tempBUsed = false;
      for(uint16_t i2=0; i2<n; i2++){
        uint16_t r = rand()%(n*2);
	if((r == 0) && (!tempAUsed) && (!aUsed[i2])){
	  goal[i][i2] = 'A';
	  tempAUsed = true;
	  aUsed[i2] = true;
	}
	if((r == 2) && (!tempBUsed) && (!bUsed[i2])){
	  goal[i][i2] = 'B';
	  tempBUsed = true;
	  bUsed[i2] = true;
	}
      }
      }*/
    /*    for(uint16_t i=0; i<n; i++){
      for(uint16_t i2=0; i2<n; i2++){
        cout << goal[i][i2];
      }
      cout<<"\n";
      }*/
  //if(!empty){
   /*    char taul[505][505];
    for(uint32_t i=0; i<n; i++){
      for(uint32_t i2=0; i2<n; i2++){
	taul[i][i2] = '.';
      }
      taul[i][n] = 0;
    }
    counter = 0;
    taulukot(0,taul,goal,0,0);*/
    //  cout << counter<<"\n";
    /*  }
  else{  
    cout << (fact(n)*(uint64_t)taikaluvut[n])%M<<"\n";
    }*/
  

  uint16_t aAmount = 0;
  for(uint16_t i=0; i<n; i++){
    for(uint16_t i2=0; i2<n; i2++){
      if(goal[i][i2] == 'A'){
	aAmount++;
      }
    }
  }
  uint16_t xSize = n-aAmount;
  uint16_t ySize = n-aAmount;
  uint16_t aSize = n-aAmount;
  uint16_t extraB = 0;
  uint16_t taulSize = n;
  for(uint16_t i=0; i<n; i++){
    for(uint16_t i2=0; i2<n; i2++){
      if(goal[i][i2] == 'B'){
        uint16_t aX = 0;
        uint16_t aY = 0;
	for(uint16_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(uint16_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){
    uint16_t temp = xSize;
    xSize = ySize;
    ySize = temp;
  }
  uint64_t ans=0;
  for(int16_t i=ySize; i>= 0; i--){
    // uint64_t b = ((fact(ySize)/fact(ySize-i))*perm(i,xSize))%M;
    uint64_t b = (factDiv(ySize,(ySize-i),1)*perm(i,xSize))%M;
    // cout <<b <<"\n";
    uint16_t tempY = ySize-i;
    uint16_t tempX = xSize-i;
    uint64_t temp = 0;
    for(uint16_t i2=0; (i2 <= tempX)&&(i2 <= aAmount); i2++){
      if((taulSize-ySize-(aAmount-i2)) >= tempX){
	uint64_t temp1 = (((perm(i2, aAmount)*(perm(tempX-i2,taulSize-ySize-aAmount)))%M)*fact(tempX))%M;
	for(uint16_t i3=0; (i3 <= tempY)&& (i3 <= (aAmount-i2)); i3++){
	  if((taulSize-xSize-(aAmount-i2-i3)) >= tempY){
	    uint64_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;
	  }
	}
      }
    }
    //  cout << temp<<"\n";
    ans += (((b*temp)%M)*solutions(aSize, i+extraB))%M;
    ans %= M;
  }
  cout <<ans<<"\n";
  /* if(ans != counter){
    cout << "\n";
    for(uint16_t i=0; i<n; i++){
      for(uint16_t i2=0; i2<n; i2++){
        cout << goal[i][i2];
      }
      cout<<"\n";
    }
    cout << "!!!!!!\n";
    while(1);
  }
  }*/
}

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:

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

correct output
259107857

user output
(empty)

Test 16

Group: 2

Verdict:

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

correct output
19906314

user output
(empty)

Test 17

Group: 2

Verdict:

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

correct output
224313667

user output
(empty)

Test 18

Group: 2

Verdict:

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

correct output
929574601

user output
(empty)

Test 19

Group: 2

Verdict:

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

correct output
600226043

user output
(empty)

Test 20

Group: 2

Verdict:

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

correct output
198353194

user output
(empty)

Test 21

Group: 3

Verdict:

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

correct output
840243733

user output
(empty)

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:

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

correct output
121064146

user output
(empty)

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