E. Combinatorics Problem

题意

给出 $n,a_1,x,y,m$，$\forall i\in [2,n],a_i=(a_{i-1}\cdot x+y)modm$

对于每一个 $b_i$，则由题中所给公式求出

输出 $b_1\cdot 1⨁b_2\cdot 2⨁b_3\cdot \mathrm{3.....}⨁b_n\cdot n$

思路

先线性求出数组 $a$，然后我们观察 $b_i$ 公式：

• $b_i=C_i^k\cdot a_1+C_{i-1}^k\cdot a_2+C_{i-2}^k\cdot a_3+...+C_1^k\cdot a_i$

由组合数公式：$C_n^m=C_{n-1}^{m-1}+C_{n-1}^m$，我们可以得到：

$b_i=(C_{i-1}^{k-1}+C_{i-1}^k)\cdot a_1+(C_{i-2}^{k-1}+C_{i-2}^k)\cdot a_2+(C_{i-3}^{k-1}+C_{i-3}^k)\cdot a_3+...+C_1^k\cdot a_i$

用 $dp[i][j]$ 表示当 $k=j$ 时，$b_i$ 的值，那么我们可以得出除了最后一项 $C_1^k\cdot a_1$ 外，其他每一项的第一项合并在一起就是：$dp[i-1][k-1]$，第二项合并在一起就是：$dp[i-1][k]$

那么我们有递推公式：$dp[i][j]=dp[i-1][j-1]+dp[i-1][j]+C_1^k\cdot a_i$

特别地，当 $k=0$ 时，所有 $C_i^0=1$，因此 $dp[i][0]$ 是 ${\sum }_{i=1}^i{a}_i$ 这个前缀和

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

#include<bits/stdc++.h>
#define fore(i,l,r)	for(int i=(int)(l);i<(int)(r);++i)
#define fi first
#define se second
#define endl '\n'
#define ull unsigned long long
#define ALL(v) v.begin(), v.end()
#define Debug(x, ed) std::cerr << #x << " = " << x << ed;

const int INF=0x3f3f3f3f;
const long long INFLL=1e18;

typedef long long ll;

template<class T>
constexpr T power(T a, ll b){
    T res = 1;
    while(b){
        if(b&1) res = res * a;
        a = a * a;
        b >>= 1;
    }
    return res;
}

constexpr ll mul(ll a,ll b,ll mod){ //快速乘，避免两个long long相乘取模溢出
    ll res = a * b - ll(1.L * a * b / mod) * mod;
    res %= mod;
    if(res < 0) res += mod; //误差
    return res;
}

template<ll P>
struct MLL{
    ll x;
    constexpr MLL() = default;
    constexpr MLL(ll x) : x(norm(x % getMod())) {}

    static ll Mod;
    constexpr static ll getMod(){
       if(P > 0) return P;
       return Mod;
    }

    constexpr static void setMod(int _Mod){
       Mod = _Mod;
    }
    constexpr ll norm(ll x) const{
       if(x < 0){
           x += getMod();
       }
       if(x >= getMod()){
           x -= getMod();
       }
       return x;
    }
    constexpr ll val() const{
       return x;
    }
    explicit constexpr operator ll() const{ 
       return x; //将结构体显示转换为ll类型： ll res = static_cast<ll>(OBJ)
    }
    constexpr MLL operator -() const{ //负号，等价于加上Mod
       MLL res;
       res.x = norm(getMod() - x);
       return res;
    }
    constexpr MLL inv() const{
       assert(x != 0);
       return power(*this, getMod() - 2); //用费马小定理求逆
    }
    constexpr MLL& operator *= (MLL rhs) & { //& 表示“this”指针不能指向一个临时对象或const对象
       x = mul(x, rhs.x, getMod()); //该函数只能被一个左值调用
       return *this;
    }
    constexpr MLL& operator += (MLL rhs) & {
       x = norm(x + rhs.x);
       return *this;
    }
    constexpr MLL& operator -= (MLL rhs) & {
       x = norm(x - rhs.x);
       return *this;
    }
    constexpr MLL& operator /= (MLL rhs) & {
       return *this *= rhs.inv();
    }
    friend constexpr MLL operator * (MLL lhs, MLL rhs){
       MLL res = lhs;
       res *= rhs;
       return res;
    }
    friend constexpr MLL operator + (MLL lhs, MLL rhs){
       MLL res = lhs;
       res += rhs;
       return res;
    }
    friend constexpr MLL operator - (MLL lhs, MLL rhs){
       MLL res = lhs;
       res -= rhs;
       return res;
    }
    friend constexpr MLL operator / (MLL lhs, MLL rhs){
       MLL res = lhs;
       res /= rhs;
       return res;
    }
    friend constexpr std::istream& operator >> (std::istream& is, MLL& a){
       ll v;
       is >> v;
       a = MLL(v);
       return is;
    }
    friend constexpr std::ostream& operator << (std::ostream& os, MLL& a){
       return os << a.val();
    }
    friend constexpr bool operator == (MLL lhs, MLL rhs){
       return lhs.val() == rhs.val();
    }
    friend constexpr bool operator != (MLL lhs, MLL rhs){
       return lhs.val() != rhs.val();
    }
};

const ll mod = 998244353;
using Z = MLL<mod>;


int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    int n;
    ll a1, x, y, m, k;
    std::cin >> n >> a1 >> x >> y >> m >> k;
    std::vector<ll> a(n + 1);
    a[1] = a1;
    fore(i, 2, n + 1) a[i] = (a[i - 1] * x % m + y) % m;
    std::vector<std::vector<Z>> dp(n + 1, std::vector<Z>(k + 1, 0));
    fore(i, 1, n + 1) dp[i][0] = dp[i - 1][0] + a[i];
    fore(j, 1, k + 1)
        fore(i, 1, n + 1)
            dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1] + (j <= 1) * a[i];
    ll ans = 0;
    fore(i, 1, n + 1)  ans ^= (1ll * i * dp[i][k].x);
    std::cout << ans;
    return 0;
}