Original question link: E. Combinatorics Problem
The main idea of the title:
Given a length of
n
n
array of n
a
a
a (obtained according to the formula of the original question) and a positive integer
k
k
k, you need to calculate a length of
n
n
new array of n
b
b
b , where:
-
b
1
=
(
C
k
1
?
a
1
)
m
o
d
998244353
;
b_1=(C_{k}^{1}\cdot a_1)\mod 998244353;
b1?=(Ck1a1?)mod998244353;
-
b
2
=
(
C
k
2
?
a
1
+
C
k
1
?
a
2
)
m
o
d
998244353
;
b_2=(C_{k}^{2}\cdot a_1 + C_{k}^{1}\cdot a_2)\mod 998244353;
b2?=(Ck2a1? + Ck1a2?)mod998244353;
-
b
3
=
(
C
k
3
?
a
1
+
C
k
2
?
a
2
+
C
k
1
?
a
3
)
m
o
d
998244353
b_3=(C_{k}^{3}\cdot a_1 + C_{k}^{2}\cdot a_2 + C_{k}^{1}\cdot a_3)\mod 998244353
b3?=(Ck3a1? + Ck2a2? + Ck1a3?)mod998244353, and so on.
in particular,
b
i
=
(
∑
j
=
1
i
C
k
i
?
j
+
1
?
a
j
)
m
o
d
998244353
b_i=(\sum_{j=1}^{i}C_{k}^{i-j + 1} \cdot a_j) \mod 998244353
bi?=(∑j=1i?Cki?j + 1aj?)mod998244353.
Now you want to output this
b
b
b XOR sum of arrays.
Problem-solving ideas:
It seems very difficult. Let’s see if we can convert it into a recursive form.
hypothesis
k
=
2
k=2
k=2, then our
b
b
The b array would look like this:
b
1
=
a
1
b
2
=
3
?
a
1
+
a
2
b
3
=
6
?
a
2
+
3
?
a
2
+
a
3
b
4
=
10
?
a
2
+
6
?
a
2
+
3
?
a
3
+
a
4
\begin{array}{l} b_1=a_1\ b_2=3\cdot a_1 + a_2\ b_3=6\cdot a_2 + 3\cdot a_2 + a_3\ b_4=10\cdot a_2 + 6\cdot a_2 + 3\cdot a_3 + a_4\ \end{array}
b1?=a1?b2?=3?a1? + a2?b3?=6?a2? + 3?a2? + a3?b4?=10?a2? + 6?a2? + 3?a3? + a4? ?
hypothesis
b
0
=
0
b_0=0
b0?=0 Let’s take the difference between two adjacent items and see what we get.
Δ
1
=
a
1
Δ
2
=
2
?
a
1
+
a
2
Δ
3
=
3
?
a
1
+
2
?
a
2
+
a
3
Δ
4
=
4
?
a
1
+
3
?
a
2
+
2
?
a
3
+
a
4
\begin{array}{l} \Delta_1 = a_1\ \Delta_2 = 2 \cdot a_1 + a_2\ \Delta_3 = 3 \cdot a_1 + 2 \cdot a_2 + a_3\ \Delta_4 = 4 \cdot a_1 + 3 \cdot a_2 + 2 \cdot a_3 + a_4\ \end{array}
Δ1?=a1?Δ2?=2?a1? + a2?Δ3?=3?a1? + 2?a2? + a3?Δ4?=4?a1? + 3?a2? + 2?a3? + a4? ?
It seems to be very regular. We find that we can make another difference, then we will get:
Δ
1
‘
=
a
1
Δ
2
‘
=
a
1
+
a
2
Δ
3
‘
=
a
1
+
a
2
+
a
3
Δ
4
‘
=
a
1
+
a
2
+
a
3
+
a
4
\begin{array}{l} \Delta_1′ = a_1\ \Delta_2′ = a_1 + a_2\ \Delta_3′ = a_1 + a_2 + a_3\ \Delta_4’ = a_1 + a_2 + a_3 + a_4\ \end {array}
Δ1′?=a1?Δ2′?=a1? + a2?Δ3′?=a1? + a2? + a3?Δ4′?=a1? + a2? + a3? + a4
You’ll find out, huh? Isn’t this a prefix sum?
Then the conclusion is:
b
b
b array is
a
a
a of an array
k
+
1
k+1
k + 1 order prefix sum.
Of course, this question can also be derived based on the number of combinations.
Depend on
C
n
k
=
C
n
?
1
k
+
C
n
?
1
k
?
1
C_n^k= C_{n-1}^{k} + C_{n-1}^{k-1}
Cnk?=Cn?1k? + Cn?1k?1? can be obtained
b
n
,
k
=
∑
i
=
1
n
C
n
?
i
+
1
k
?
a
i
b
n
,
k
=
∑
i
=
1
n
(
C
n
?
i
k
+
C
n
?
i
k
?
1
)
?
a
i
b
n
,
k
=
b
n
?
1
,
k
?
1
+
b
n
?
1
,
k
\begin{array}{l} b_{n,k}=\sum_{i=1}^{n}C_{n-i + 1}^{k}\cdot a_i \ b_{n,k}= \sum_ {i=1}^{n}(C_{n-i}^{k} + C_{n-i}^{k-1})\cdot a_i\ b_{n,k}= b_{n-1,k- 1} + b_{n-1,k} \end{array}
bn,k?=∑i=1n?Cn?i + 1kai?bn,k?=∑i=1n?(Cn?ik? + Cn?ik?1?)?ai?bn,k?= bn?1,k?1? + bn?1,k
In this way, we open a two-dimensional array
b
n
,
k
b_{n,k}
bn,k?,
b
n
,
k
b_{n,k}
bn,k? can be deduced from the previous state.
Of course, here we do it directly with violence
a
a
a of an array
k
+
1
k+1
A k + 1 prefix sum would be more convenient.
time complexity:
O
(
n
k
)
O(nk)
O(nk)
AC code:
#include <bits/stdc + + .h>
#define YES return void(cout << "Yes\
")
#define NO return void(cout << "No\
")
using namespace std;
using ui64 = unsigned long long;
using PII = pair<int, int>;
using i64 = long long;
const int mod = 998244353;
void solve() {<!-- -->
i64 n, x, y, m, k;
cin >> n;
vector<i64> a(n + 1);
cin >> a[1] >> x >> y >> m >> k;
for (int i = 2; i <= n; + + i) {<!-- -->
a[i] = (a[i - 1] * x + y) % m;
}
// k + 1 times prefix sum
for (int j = 1; j <= k + 1; + + j) {<!-- -->
for (int i = 1; i <= n; + + i) {<!-- -->
a[i] = (a[i] + a[i - 1]) % mod;
}
}
i64 c = 0;
for (int i = k; i <= n; + + i) {<!-- -->
c ^= a[i - k + 1] * i;
}
cout << c << '\
';
}
signed main() {<!-- -->
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int t = 1; //cin >> t;
while (t--) solve();
return 0;
}