[Easy] CF1832E Combinatorics Problem

简要题意

给定一个长度为 $n$ 的序列 $a$ 和一个参数 $k$，你需要求出一个长度为 $n$ 的序列 $b$，满足：

$$b_i=\sum_{j=1}^{i}\binom{i-j+1}{k}$$

$1\leq n\leq 10^7,1\leq k\leq 5$。

思路

记 $b_{i,j}$ 表示当 $k=j$ 时的答案，则：

$$\begin{aligned} b_{n,k}&=\sum_{i=1}^{n}\binom{n-i+1}{k}a_i\\ &=\sum_{i=1}^{n}\left(\binom{n-i}{k-1}+\binom{n-i}{k}\right)a_i\\ &=\sum_{i=1}^{n}\binom{n-i}{k-1}a_i+\sum_{i=1}^{n}\binom{n-i}{k}a_i\\ &=\left(\binom{0}{k}+\binom{0}{k-1}\right)a_n+\sum_{i=1}^{n-1}\binom{n-i}{k-1}a_i+\sum_{i=1}^{n-1}\binom{n-i}{k}a_i\\ &=[k\in\{0,1\}]a_n+b_{n-1,k-1}+b_{n-1,k} \end{aligned}$$

直接递推，边界 $b_{n,0}=b_{n-1,0}+a_n$。

时间复杂度 $O(nk)$。

代码

#include <bits/stdc++.h>
using namespace std;

constexpr int mod = 998244353;
int Add(int x, int y){ return (x + y) >= mod ? (x + y - mod) : (x + y); }
int Sub(int x, int y){ return (x - y) < 0 ? (x - y + mod) : (x - y); }
int Mul(int x, int y){ return 1ll * x * y % mod; }

const int N = 1e7 + 5;
int a[N], b[N][6], n, k;

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int x, y, m; cin >> n >> a[1] >> x >> y >> m >> k;
    for(int i=2;i<=n;i++) a[i] = (1ll * a[i - 1] * x + y) % m;
    for(int i=1;i<=n;i++) b[i][0] = Add(b[i - 1][0], a[i]);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=k;j++){
            if(j == 1) b[i][j] = a[i];
            b[i][j] = Add(b[i][j], Add(b[i - 1][j], b[i - 1][j - 1]));
        }
    }
    long long ans = 0;
    for(int i=1;i<=n;i++) ans ^= 1ll * i * b[i][k];
    cout << ans << '\n';
    return 0;
}

// Written by xiezheyuan