## 題目描述

### utils.h

1234567891011#ifndef _UTILS_H#define _UTILS_H#include <stdint.h>static inline uint32_t rotate_left(uint32_t x, uint32_t n) {    return  (x << n) | (x >> (32-n));}static inline uint32_t encrypt(uint32_t m, uint32_t key) {    return (rotate_left(m, key&31) + key)^key;}void output(uint32_t presum[], int n);#endif


### prefixsum-seq.c

12345678910111213141516171819202122#include <stdio.h>#include <stdlib.h>#include <stdint.h>#include <inttypes.h>#include "utils.h" #define MAXN 10000005#define MAX_THREAD 4uint32_t prefix_sum[MAXN];int main() {    int n;    uint32_t key;    while (scanf("%d %" PRIu32, &n, &key) == 2) {        uint32_t sum = 0;        for (int i = 1; i <= n; i++) {            sum += encrypt(i, key);            prefix_sum[i] = sum;        }        output(prefix_sum, n);    }    return 0;}


### secret.c (測試用)

123456789101112#include <stdio.h>#include <stdlib.h>#include <stdint.h>#include <inttypes.h>#include "utils.h" void output(uint32_t presum[], int n) {    uint32_t hash = 0;    for (int i = 1; i <= n; i++)        hash += presum[i] * i;    printf("%" PRIu32 "\n", hash);}


## 輸入格式

• $1 \le n \le 10^7$
• $0 \le key \lt 2^{32}$

## 範例輸入

3 210 5


## 範例輸出

10054560


## 範例解釋

• $(n, \textit{key})=(3, 2)$，得 $A \left\lbrack 1 \cdots 3\right] = \left\lbrack 4, 8, 12 \right]$，$S \left\lbrack 1 \cdots 3\right] = \left\lbrack 4, 12, 24 \right]$，$\text{hash} = 4 + 12 \times 2 + 24 \times 3 = 100$

## 編譯方式

1gcc -std=c99 -O2 -pthread prefixsum-seq.c secret.c -o prefixsum-seq


## 測試主機資訊

#define _GNU_SOURCE...int main() {        {                cpu_set_t cpuset;                CPU_ZERO(&cpuset);                for (int i = 0; i < 6; i++)                        CPU_SET(i, &cpuset);                assert(sched_setaffinity(0, sizeof(cpuset), &cpuset) == 0);        }...

processor   : 0vendor_id   : GenuineIntelcpu family  : 6model       : 62model name  : Intel(R) Xeon(R) CPU E5-2620 v2 @ 2.10GHzstepping    : 4microcode   : 0x415cpu MHz     : 1200.000cache size  : 15360 KBphysical id : 0siblings    : 12core id     : 0cpu cores   : 6apicid      : 0initial apicid  : 0fpu     : yesfpu_exception   : yescpuid level : 13wp      : yes processor   : 1vendor_id   : GenuineIntelcpu family  : 6model       : 62model name  : Intel(R) Xeon(R) CPU E5-2620 v2 @ 2.10GHzstepping    : 4microcode   : 0x415cpu MHz     : 1200.000cache size  : 15360 KBphysical id : 0siblings    : 12core id     : 1cpu cores   : 6apicid      : 2initial apicid  : 2fpu     : yesfpu_exception   : yescpuid level : 13wp      : yes