P8977 - li<x>nk with Checksum

内存限制：256 MB 时间限制：1 S

题面：传统评测方式：Special Judge 上传者：

提交：0 通过：0

link has invented an algorithm called CRC-link. In order to calculate CRC-link checksum of a datagram, let's assume the input byte array as

D

and the CRC-link polynomial as

P

(

P=0x04C11DB7P=\text{0x04C11DB7}

), and follow the three steps below.

Treat each byte of the input byte array $D$ as an 8-bit binary number. Append 32 zero bits to the end of $D$ , creating an initial remainder $R$ .
Repeat the following step for $N$ times, where $N$ is the number of bits in $D$ .
- If the most significant bit of $R$ is 1, shift $R$ one bit to the left, then perform an XOR operation: XOR the most significant 32 bits of $R$ with the CRC-link polynomial $P$ .
- Otherwise, just shift $R$ one bit to the left.
The most significant 32 bits of $R$ is the CRC-link checksum of $D$ .

For example, if

D

= {0x01, 0x02}, the CRC-link checksum can be calculated by:

00000001 00000010 00000000 00000000 00000000 00000000
(shift left for 7 bits)
10000001 00000000 00000000 00000000 00000000 00000000
(shift left for 1 bit, then xor P)
00000110 11000001 00011101 10110111 00000000 00000000
(shift left for 5 bits)
11011000 00100011 10110110 11100000 00000000 00000000
(shift left for 1 bit, then xor P)
10110100 10000110 01110000 01110111 00000000 00000000
(shift left for 1 bit, then xor P)
01101101 11001101 11111101 01011001 00000000 00000000
(shift left for 1 bit)
11011011 10011011 11111010 10110010 00000000 00000000
(since we have shifted 16 bits in total, the left 32 bits above is what we need)

Please note that CRC-link may be slightly different from CRC32.

For a datagram consisting of three parts: a header (

n_1

bytes), a checksum (

4

bytes), and a footer (

n_2

bytes), the header and footer are given, while the checksum needs to be determined by you. You should choose a checksum that matches the CRC-link calculation result of the entire datagram. Formally, you should make sure CRC-link(concat(header,YourAnswer,footer)) equals to YourAnswer.

You may refer the example explanation for better understanding of how to check your answer.

The first line contains two integers,

n_1

and

n_2

(

\le n_1, n_2 \le 10^5

), representing the lengths of the header and footer, respectively.
The second line contains

n_1

integers, where the

i

-th integer

a_i

(

\le a_i < 2^8

) represents the value of the

i

-th byte in the header.
The third line contains

n_2

integers, where the

i

-th integer

b_i

(

\le b_i < 2^8

) represents the value of the

i

-th byte in the footer.

If a feasible checksum exists, output the checksum value (in decimal). Otherwise, output `-1'.
If multiple feasible solutions exist, you can output any one of them.

1 2
114
51 4

456567105

In the first example, when outputting `456567105', the answer is correct because CRC-link(72 1B 36 A9 41 33 04) equals to `456567105'.

2023牛客多校2

8977: link with Checksum

题目描述

输入格式

输出格式

输入样例复制

输出样例复制

数据范围与提示

分类标签