Limits 2s, 512 MB

As Mr. Bean was playing a video game in the previous problem, now he is leveled up. At this level, he has (N x 60) enemies in front of him. As he is powered up he has now (N x 60) powerful guns, each bullet kills one enemy.

He has pointed (N x 60) guns towards (N x 60) enemies, such as the 1st gun is pointed towards the 1st enemy, the 2nd towards the 2nd and so on, each gun will only shoot towards the enemy it’s pointed at.

But the guns have defects, sometimes bullets don’t come out from some guns. And the bullets have some special characteristics, if any bullet hits a dead enemy the enemy gets alive again.

Mr. Bean will shoot M rounds of bullets from each gun. One round from each of them at a time.
But before starting to shoot Mr.Bean wants to know how optimal his strategy is , so he will provide you the information of his M rounds of shooting and you have to tell him how many enemies will remain alive after all M rounds.

Due to security essues as Mr.Bean dosen't want other gamers to know about his information he will give you the data encrypted. He has given you a function in the past ( the function is given below ), now during each game he will give you the values of N, M, seed and mod. Using these values in the function you will get a M x N
matrix A, each row of A will describe one round.

The binary representation of the numbers describes the bullets, if we denote each element of the matrix by Aij (0 <= i < M, 0 <= j < N), then Aij will describe the (j x 60 + 1)th to (j x 60 + 60)th bullet of ith round, if a bit is on then the corresponding gun has fired a bullet and if the bit is off then no bullet came out of the corresponding gun. (for more info see in the sample and note section).


long long A[100005][505];

void generateVal(int n, int m, unsigned long long seed, long long mod){

	for(int i = 0; i < m; i++){	

        for(int j = 0; j < n; j++){  

            seed *= 0x7e378157;  

            seed ^= 0x5d30227f;  

            A[i][j] = seed & mod;


The input will contain 4 numbers N, M, seed, mod, the number of enemies, the number of rounds, the seed and mod needed for the function.

1 <= N <= 500

1 <= M <= 100000

0 <= seed, mod, Aij < 260


A single integer, the number of enemies alive after M rounds of shooting.


2 1 11 123
10 1000 123 123123

In sample 1 the generated matrix is,

[66, 17]

so the actual information is,

000000000000000000000000000000000000000000000000000001000010, 000000000000000000000000000

so the 54th, 69th, 116th and 120th enemy will be dead and rest will remain alive.


Login to submit.


89% Solution Ratio
EgorKulikovEarliest, Jul '20
Asif_AlimFastest, 0.0s
EgorKulikovLightest, 131 kB
YouKnowWhoShortest, 531B
Toph uses cookies. By continuing you agree to our Cookie Policy.