P8613 - Jobs (Easy Version)

内存限制：512 MB 时间限制：3 S

题面：传统评测方式：文本比较上传者：

提交：0 通过：0

Note: The only difference between the easy and the hard version is the constraints on

n

and

m_i

Since Little Horse gets a golden prize in a programming contest, many companies send offers to him. There are

n

companies, and the

i

-th company has

m_i

available jobs. To get an offer from a company, you need to be qualified for the job.

How to be qualified? The company will test your "three quotients": IQ (Intelligence Quotient), EQ (Emotional Quotient), and AQ (Adversity Quotient). Each job has three lower limits of the three quotients respectively. If all of your IQ, EQ, and AQ are no less than the corresponding lower limits, you are qualified for the job. As long as you are qualified for at least one job in a company, the company will send an offer to you.

Little Horse's three quotients are all high enough, so all the companies send offers to him. But Little Horse has

q

friends that worry about their jobs. Given the value of IQ, EQ and AQ of each friend, Little Horse wants to know how many companies will send offers to each friend.

In this problem, the IQ, EQ, and AQ of these

q

friends are generated as below.

First, register an

mt19937\texttt{mt19937}

random engine

rng\texttt{rng}

with the

seed\texttt{seed}

and a uniform integer distribution object.

#include <random>
std::mt19937 rng(seed);
std::uniform_int_distribution<> u(1,400);

Then, the value of IQ, EQ, and AQ are generated as follows.

int lastans=0;
for (int i=1;i<=q;i++)
{
    int IQ=(u(rng)^lastans)%400+1;  // The IQ of the i-th friend
    int EQ=(u(rng)^lastans)%400+1;  // The EQ of the i-th friend
    int AQ=(u(rng)^lastans)%400+1;  // The AQ of the i-th friend
    lastans=solve(IQ,EQ,AQ);  // The answer to the i-th friend
}

The first line of input contains two integers

n, q

(

\le n \le 10

\le q \le 2\times 10^6

), indicating the number of companies and Little Horse's friends.
Then in the next

n

lines, the first integer of the

i

-th line is

m_i

(

\le m_i \le 10^5

) --- the number of jobs in the

i

-th company. Then there follow

3m_i

integers. The

j

-th triple integers

a_j,b_j,c_j

(

\le a_j,b_j,c_j \le 400

) indicate the lower limits of IQ, EQ, and AQ for the

j

-th job in the

i

-th company.
The next line contains one integer

seed\text{seed}

(

108≤seed<23110^8\le \text{seed}<2^{31}

). Then the IQ ,EQ, and AQ of these

q

friends are generated as above.

Let's denote the answer to the

i

-th friend as

ansi\text{ans}_i

. You should output:

(∑i=1qansi⋅seedq−i)mod998244353\left( \sum_{i=1}^q\text{ans}_i\cdot\text{seed}^{q-i} \right) \bmod 998244353

in a single line.

3 5
2 1 1 2 2 1 2
3 1 3 2 2 3 1 2 3 3
2 2 3 1 3 2 1
191415411

34417749

The value of IQ, EQ, and AQ of the 55 friends in example are shown as follows.

92 108 303
116 36 265
255 132 185
360 219 272
8 115 254

The answers to each friend are all 33.

2022牛客4

8613: Jobs (Easy Version)

题目描述

输入格式

输出格式

输入样例复制

输出样例复制

数据范围与提示

分类标签