Article directory
- Subject address
- topic abstract
- topic type
- problem solving ideas
- the code
Subject URL
https://codeforces.com/problemset/problem/1832/E
Abstract topic
give n,
a
1
a_1
a1?, x, y, m, k are six integers, and the following 4 steps are required
- according to
a
i
=
(
a
i
?
1
?
x
+
the y
)
%
m
,
i
∈
[
2
,
no
]
a_i=(a_{i-1}\cdot x + y) \% m, i\in[2,n]
ai?=(ai?1x + y)%m,i∈[2,n] generate array a
- according to
b
i
=
(
∑
j
=
1
i
(
C
i
?
j
+
1
k
?
a
j
)
)
%
998244353
b_i = (\sum_{j=1}^i(C_{i-j + 1}^k\cdot a_j)) \% 998244353
bi?=(∑j=1i?(Ci?j + 1kaj?))?8244353 generate array b
- according to
c
i
=
b
i
?
i
c_i = b_i\cdot i
ci?=bii generates array c
- calculate
c
1
⊕
c
2
⊕
?
⊕
c
no
c_1 \oplus c_2 \oplus \cdots \oplus c_n
The result of c1?⊕c2?⊕?⊕cn? (
⊕
\oplus
⊕ stands for XOR operation of bit operation)
The amount of data:
1
≤
no
≤
1
0
7
1\le n\le 10^7
1≤n≤107
0
≤
a
1
,
x
,
the y
,
≤
m
0\le a_1,x,y,\le m
0≤a1?,x,y,≤m
2
≤
m
≤
998244353
2\le m \le 998244353
2≤m≤998244353
1
≤
k
≤
5
1\le k \le 5
1≤k≤5
Type of topic
Mathematical derivation
Problem solving ideas
Steps 1, 3, and 4 are very intuitive, and they have been simulated and directly calculated
The main difficulty is the second step, calculating b according to a
The following disassembly analysis:
Roughly calculate each
b
i
b_i
The complexity of bi? is very high, since the maximum possible n is
1
0
7
10^7
107, need to find a way to let
b
i
b_i
bi? can be calculated in
o
(
1
)
O(1)
Complete in O(1) time
tips:
Usually this is the caseb
i
b_i
bi? and
b
i
?
1
b_{i-1}
The relation of bi?1? makes
b
i
b_i
bi? can be passed
b
i
?
1
b_{i-1}
bi?1? quickly yields
The way to find their relationship is to expand them and then subtract them, which is applicable in most cases
We expand it and subtract to get the relationship
b
i
=
C
i
k
?
a
1
+
C
i
?
1
k
?
a
2
…
C
2
k
?
a
i
?
1
+
C
1
k
?
a
i
b
i
?
1
=
C
i
?
1
k
?
a
1
+
C
i
?
2
k
?
a
2
…
C
1
k
?
a
i
?
1
b
i
?
b
i
?
1
=
(
C
i
k
?
C
i
?
1
k
)
?
a
1
+
(
C
i
?
1
k
?
C
i
?
2
k
)
?
a
2
…
(
C
2
k
?
C
1
k
)
?
a
i
?
1
+
C
1
k
?
a
i
\begin{array}{clcr} b_i & amp;= & amp;C_i^k\cdot a_1 & amp; + & amp;C_{i-1}^k\cdot a_2 & amp;\dots & amp;C_2^k\cdot a_{i-1} & amp; + & amp;C_1^k\cdot a_i \ b_{i-1} & amp;= & amp;C_{i-1 }^k\cdot a_1 & amp; + & amp;C_{i-2}^k\cdot a_2 & amp;\dots & amp;C_1^k\cdot a_{i-1} \\ \ b_i-b_{i-1} & amp;= & amp;(C_i^k-C_{i-1}^k)\cdot a_1 & amp; + & amp;(C_{i-1}^k -C_{i-2}^k)\cdot a_2 & amp;\dots & amp;(C_2^k-C_1^k)\cdot a_{i-1} & amp; + & amp;C_1^ k\cdot a_i \ \end{array}
bi?bi?1?bibi?1===?Cika1?Ci?1ka1?(CikCi?1k?)?a1 + + + ?Ci?1k a2?Ci?2ka2?(Ci?1kCi?2k?)?a2………?C2kai?1?C1kai?1?(C2kC1k? )?ai?1 + + ?C1kai?C1kai
∵
\because
∵ Combination numbers have this property
C
i
k
=
C
i
k
?
1
+
C
i
?
1
k
?
1
C_i^k=C_i^{k-1} + C_{i-1}^{k-1}
Cik?=Cik?1? + Ci?1k?1?
∴
b
i
?
b
i
?
1
=
(
C
i
?
1
k
?
1
?
a
i
+
…
C
1
k
?
1
?
a
i
?
1
)
+
C
1
k
?
a
i
\therefore b_i-b_{i-1} = (C_{i-1}^{k-1}\cdot a_i + \dots C_1^{k-1}\cdot a_{i-1}) + C_1^k\cdot a_i
∴ bibi?1?=(Ci?1k?1ai? + …C1k?1ai?1?) + C1kai?
Is the content in the brackets familiar, and
b
i
?
1
b_{i-1}
bi?1? is very similar, that is, when k is k-1
b
i
?
1
b_{i-1}
bi?1?
We extend b by one dimension, the original
b
i
b_i
bi? use
b
k
,
i
b_{k,i}
bk,i? instead, then get
b
k
,
i
?
b
k
,
i
?
1
=
b
k
?
1
,
i
?
1
+
C
1
k
?
a
i
b_{k,i}-b_{k,i-1} = b_{k-1,i-1} + C_1^k\cdot a_i
bk,ibk,i?1?=bk?1,i?1? + C1kai?
∴
b
k
,
i
=
b
k
,
i
?
1
+
b
k
?
1
,
i
?
1
+
C
1
k
?
a
i
\therefore b_{k,i} =b_{k,i-1} + b_{k-1,i-1} + C_1^k\cdot a_i
∴bk,i?=bk,i?1? + bk?1,i?1? + C1kai?
Therefore, we need to calculate the value
b
0
,
i
b_{0,i}
b0, i? and
b
k
,
0
b_{k,0}
bk,0?, remaining
b
k
,
i
b_{k,i}
bk,i? can be obtained from the results that have been calculated in the preorder
Available by definition
b
0
,
i
=
a
i
+
a
i
?
1
+
…
a
1
=
b
k
,
i
?
1
+
a
i
b_{0,i}=a_i + a_{i-1} + \dots a_1=b_{k,i-1} + a_i
b0,i?=ai? + ai?1? + …a1?=bk,i?1? + ai?
b
k
,
0
=
0
b_{k,0}=0
bk,0?=0
Then according to
b
k
,
i
=
b
k
,
i
?
1
+
b
k
?
1
,
i
?
1
+
C
1
k
?
a
i
b_{k,i} =b_{k,i-1} + b_{k-1,i-1} + C_1^k\cdot a_i
bk,i?=bk,i?1? + bk?1,i?1? + C1kai? (when k=1,
C
1
k
=
1
C_1^k=1
C1k?=1, and equal to 0 in other cases) can be obtained according to the pre-calculation
o
(
1
)
O(1)
O(1) complexity computes
overall complexity
o
(
no
?
k
)
O(n\cdot k)
O(n?k)
Code
#include <bits/stdc++.h>
using namespace std;
const int mod = 998244353;
long long a[10000001];
long long b[6][10000001];
int main() {<!-- -->
int n, x, y, m, K;
cin >> n;
cin >> a[1] >> x >> y >> m >> K;
for (int i = 2; i <= n; i ++ ) {<!-- -->
a[i] = (a[i - 1] * x + y) % m;
}
for (int i = 1; i <= n; i ++ ) {<!-- -->
b[0][i] = b[0][i-1] + a[i];
}
for (int k = 1; k <= K; k ++ ) {<!-- -->
for (int i = 1; i <= n; i ++ ) {<!-- -->
b[k][i] = (b[k][i - 1] + b[k - 1][i - 1] + (k == 1 ? a[i] : 0)) % mod;
}
}
long long ans = 0;
for (int i = 1; i <= n; i ++ ) {<!-- -->
ans ^= b[K][i] * i;
}
cout << ans << endl;
}