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

Recently I am studying Muduo, a net library written by ChenShuo.
And I think the timer system of it is worth learning, so I did some notes on it in this article.

What is a timer?

A timer allows us to do something at a specific time later. This is not quoted from someone’s words. This is just my own understanding. Say, now we want to run a function, instead of running it immediately, we want to run it after 2 seconds. And a timer enables us to do something like that.

How do we use timer in Muduo?

At the very beginning, we have to know a very important idea about Muduo: One loop per thread, which is also emphasized by the author. The core class of Muduo is EventLoop. Each EventLoop is bind to a thread and will loop forever to run the thread until we call the quit() method of it. Every thing runs in one of the EventLoops in Muduo. So, if we want to run a function in 2 seconds, we run the function in one of the EventLoops. Apparently, we run our functions in some thread.
Muduo provides us with three methods to add a timer and one to cancel a timer:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

///
/// Runs callback at 'time'.
/// Safe to call from other threads.
///
TimerId runAt(const Timestamp& time, const TimerCallback& cb);
///
/// Runs callback after @c delay seconds.
/// Safe to call from other threads.
///
TimerId runAfter(double delay, const TimerCallback& cb);
///
/// Runs callback every @c interval seconds.
/// Safe to call from other threads.
///
TimerId runEvery(double interval, const TimerCallback& cb);
///
/// Cancels the timer.
/// Safe to call from other threads.
///
void cancel(TimerId timerId);

• A Timer is actually an expiration time with a callback function. The callback function would be called when it expired.
• A TimerId is an identification of a timer so that we can cancel a timer.
• Timestamp is actually micro seconds since epoch.
• TimerCallback is a function object, which we want to run in the future.

How does these timer function work?

Now we come to the critical and interesting part, let’s try to figure out how our functions are called when their time expired. In this section, we will take a look at the whole process, from the moment a timer was added to the moment its callback was called. Firstly, I need to introduce the core class of the timer system: TimerQueue. It is invisible to the clients.
The private members of it is as follow:

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

// FIXME: use unique_ptr<Timer> instead of raw pointers.
// This requires heterogeneous comparison lookup (N3465) from C++14
// so that we can find an T* in a set<unique_ptr<T>>.
typedef std::pair<Timestamp, Timer*> Entry;
typedef std::set<Entry> TimerList;
typedef std::pair<Timer*, int64_t> ActiveTimer;
typedef std::set<ActiveTimer> ActiveTimerSet;

void addTimerInLoop(Timer* timer);
void cancelInLoop(TimerId timerId);
// called when timerfd alarms
void handleRead();
// move out all expired timers
std::vector<Entry> getExpired(Timestamp now);
void reset(const std::vector<Entry>& expired, Timestamp now);

bool insert(Timer* timer);

EventLoop* loop_;
const int timerfd_;
Channel timerfdChannel_;
// Timer list sorted by expiration
TimerList timers_;

// for cancel()
ActiveTimerSet activeTimers_;
bool callingExpiredTimers_; /* atomic */
ActiveTimerSet cancelingTimers_;

How to do that?

The way Muduo use to do such thing is quite different from what I once did. I once used two stupid methods, sleep and busy loop and judge. They are bad as far as accuracy is concerned. Besides, they are quite ‘low’ and ‘unprofessional’, right? Students may do that. But we need to be professional. Muduo uses timerfd with poll. When I refer to poll, I mean select, poll, epoll. They are provided by linux system. If you are not clear about them, man them on a linux system or search the internet. I assumed you know the basic things about poll here.
However, timerfd is something new to me. A timerfd is a special file descriptor which will become readable when the time we set expires. It is done by the linux system. Wow, wonderful! This enables us to take an expiration as the same thing with an I/O event. And we can detect these events with poll.

How to add a Timer?

1. At the very beginning, we create a timerfd by calling timerfd_create of linux. This is done only once. But we may set the timerfd many times later. We may have a lot of timers, and we want to be notified when the earliest one of them expired.
2. Insert the timer into the data structure we use to store them, which is timers_ here. As you can see, there is another member activeTimers_. Unfortunately I don’t understand what is it for. But it doesn’t matter. Notice the definition of TimerList and Entry. TimerList is a set of Entry. An std::set is an ordered container implemented by RBTree. We store entries in it so that they can be sorted by their expiration time, which is represented by a Timestamp. Considering different timers may have the same timestamp, we make pair a timestamp with a pointer of the timer. This ensures us no collisions between timers.
3. Reset the timerfd if necessary. This should be done when the latest inserted timer would expire earliest. We do this by calling linux function timerfd_settime.

How to call the callbacks when they expired?

As I mentioned above, a timerfd is treated as a normal fd. And we use poll function to detect that. By the way, let’s take a look at Muduo’s thread model. Muduo is of the Reactor Pattern.
Every single loop of EventLoop looks like this:

1. At first, a poller will poll all the fds and update the channels. A channel can be seen as a bridge between low-level I/O and high-level callbacks; Notice that there is a timerfdChannel_ in TimerQueue’s members. Once the time we set expired, the timerfdChannel_ will be updated.
2. After that, timerfdChannel_ found that the fd it took charge became readable, it call its handleRead function.
3. In its handleRead function, it will remove all the expired timers and run their callbacks. Of course, we should also read the timerfd and reset it.

Now I think we have a general idea about how muduo timer works. The core of the implementation is timerfd, poll and Reactor pattern. Thanks for reading!

At first I got stuck with this problem.So I considered a simple case when there are only islands of two colors(c = 0).And it is easy to calculate the number of different ways under the constraints.

Suppose we only have islands with red and blue. Since we can only build bridges between a red island and a blue island, and further, we can only connect one blue island with one specific red island (otherwise distance between two blue islands is 2). And vice versa. Let f(i) be the number of different ways to build bridges when there are i bridges between red islands and blue islands.

Then we have:
$$
f(i) = C_a^i \cdot C_b^i \cdot i!
$$
Since we can pick i islands from red ones and i islands from blue ones, and we permutate i islands to match them.And the total number of it is:
$$
\sum_i^{min(a,b)} f(i)
$$

And next, we need to do with three colors. Try to add bridges between red islands and purple ones, and between blue and purple. And these bridges are exactly the same thing we calculated above. More importantly, bridges between red and purple, bridges between blue and purple are independent! And so is bridges between red and blue. The three groups of bridges are independent from each other. Change bridges in one group will not break the constraints. So our final answer is multiply the three number together.

Here is my code:

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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62

#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>

#define mod 998244353

const int N=5010;
ll p[N],inv[N];
ll C(int n,int m) {
    return (((p[n]*inv[m])%mod)*inv[n-m])%mod;
}

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

void init() {
    p[0]=1;inv[0]=1;
    for (int i=1;i<=5000;i++) {
        p[i]=(p[i-1]*i)%mod;
        inv[i]=qp(p[i],mod-2);
    }
}

int a[3];

int main()
{
    init();
    scanf("%d%d%d",a,a+1,a+2);
    ll ans[3]={0};
    for (int i=0;i<3;i++) {
        int x=i,y=(i+1)%3;
        int lim=min(a[x],a[y]);
        for (int j=0;j<=lim;j++) {
            ll tmp=(((C(a[x],j)*C(a[y],j))%mod)*p[j])%mod;
            ans[i]=(ans[i]+tmp)%mod;
        }
    }
    ll res=(((ans[0]*ans[1])%mod)*ans[2])%mod;
    printf("%lld\n",res);
}

Problem: Codeforces 864E Fire

Well, we may easily think of the \’Knapsack\’ problem at the first glimpse of this problem. Luckily, with small modification on the solution to the \’Knapsack\’ problem we can solve this problem.

Let\’s use dynamic programming. Let dp[i][j] be the max total value of the first i items we can rescue in first j seconds. And we easily get dp[i][j] = dp[i-1][j-t[i]] + p[i]. Notice that j has to be smaller than d[i], or we cannot save this item and of course, larger than or equal to t[i]. And when we calculate the dp for answer, we have to iterate items in increasing order of their d[i]. You can simply figure out that, since the final answer must be with the latest time, and value for later time depends on value for earlier time.

And with the well-known trick for \’Knapsack\’ problem we can only use one-dimensional array as our dp.

My code:

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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

#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>

const int N=2010;
int n;
int t,d,p;
struct node {
    int t,d,p,id;
    bool operator<(const node& rhs) const {
        return d<rhs.d;
    }
};
vector<node> a;
int dp[N];
vector<int> vec[N];
int idx=0;

int main()
{
    scanf("%d",&n);
    for (int i=1;i<=n;i++) {
        scanf("%d%d%d",&t,&d,&p);
        a.pb({t,d,p,i});
    }
    sort(a.begin(),a.end());
    int mx=0;
    for (int i=0;i<n;i++) {
        for (int j=a[i].d-1;j>=a[i].t;j--) {
            if (dp[j]<dp[j-a[i].t]+a[i].p) {
                dp[j]=dp[j-a[i].t]+a[i].p;
                vec[j]=vec[j-a[i].t];
                vec[j].pb(a[i].id);
            }
            if (mx<dp[j]) {
                idx=j;
                mx=dp[j];
            }
        }
    }
    printf("%d\n",mx);
    printf("%d\n",(int)vec[idx].size());
    for (int ele:vec[idx]) printf("%d ",ele);
    printf("\n");
}

When we use cmake to compile our program and use TARGET_LINK_LIBRARIES to link libraries we need, we have to pay attention to the order these libraries are specified.

In the following case, our program depends on the muduo_base library and muduo_base library depends on pthread, then we have to ensure pthread is after muduo_base:

1

TARGET_LINK_LIBRARIES(${PROJECT_NAME} ${MUDUO_NET_LIBRARY} ${MUDUO_BASE_LIBRARY} pthread)

1

TARGET_LINK_LIBRARIES(${PROJECT_NAME} pthread ${MUDUO_NET_LIBRARY} ${MUDUO_BASE_LIBRARY})