competitive programming

Codeforces 894B Ralph And His Magic Field

Well, I didn’t solve it myself though it’s only B problem in Div2… Fine, this sometimes happens, never mind. Just practice more.

The problem is, how many different ways can we put integers in a n \ m* block so that the products of each row and each column is 1 or -1.

Let’s see how to solve it. We can easily figure out that only 1 or -1 can be put into the block. Further, another important conclusion is that when k is -1, the answer is 0 if n and m have different parity. Why is that? This is not obvious for me. If we have n be odd and m be even, then we have an even number of -1 in total since we have an even number of columns. However, we have an odd number of rows, and in each row there exists an odd number of -1. So the total number of -1 cannot be even. That’s impossible. For the rest cases, we consider the (n-1)*(m-1) subblock. We can fill either 1 or -1 into any cell. And then the rest cells are determined.
The answer is:
$$
2^{(n-1)+(m-1)}
$$

With quick power, we can solve it easily.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <iostream>
#include <algorithm>
#include <string.h>
#include <math.h>
#include <vector>

using namespace std;

#define pb push_back
#define mp make_pair
#define ll long long
#define ull unsigned ll
#define db double
#define INF 0x3f3f3f3f
#define MOD 1000000007
#define PII pair<int, int>

ll n,m,k;

ll qp(ll temp,ll x) {
    ll ret=1;
    while (x>0) {
        if (x&1) ret=(ret*temp)%MOD;
        temp=(temp*temp)%MOD;
        x>>=1;
    }
    return ret;
}

int main()
{
    scanf("%lld%lld%lld",&n,&m,&k);
    if (k==-1) {
        if ((n%2)+(m%2)==1) {
            printf("0\n");
            return 0;
        }
    }
    ll ans=qp(qp(2,n-1),m-1);
    printf("%lld\n",ans);
}

I’m recently studying using ocaml, which is a functional language.
So let’s rewrite the solution with ocaml.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
open Scanf
open Printf
open Int64

let md = 1000000007L

let f n m k =
  if k = -1L && Int64.rem (Int64.add m n) 2L = 1L then 0L
    else let rec g x y =
      if y = 0L then 1L
        else if y = 1L then x
        else let tmp = g x (Int64.div y 2L) in
          if Int64.rem y 2L = 0L then Int64.rem (Int64.mul tmp tmp) md 
          else Int64.rem (Int64.mul (Int64.rem (Int64.mul tmp tmp) md) x) md in
    g (g 2L (Int64.sub n 1L)) (Int64.sub m 1L)

let () =
  let ans = bscanf Scanning.stdin "%Ld %Ld %Ld" f in
    printf "%Ld\n" ans

Though it may be very difficult to use it in a contest temporarily, I have a great interest in this language.
The problem: Codeforces 894B Ralph And His Magic Field