原题点这
前置知识点:
组合数学
题意:
给你一个数组 a 和 k, 让你计算一个新的数组 b。
给你 \(a_1\) , 对于$ 2 \le i \le n $, $ a_i = (a_{i-1} \cdot x + y) \bmod m $
$ b_i = (\sum\limits_{j=1}^{i} \binom{i - j + 1}{k} \cdot a_j) \bmod 998244353 $.
$ c_i = b_i \cdot i $
让你求:$ c_1 \oplus c_2 \oplus \dots \oplus c_n $
思路:
乍一看好像是 FFT 的板子,但是看数据范围:\(10^7\)。好吧,估计过不了 * _ *。
那只能开始化简公式了:
到这就很明显了,直接暴力遍历求b即可,时间复杂度O(nk),完全可过。
AC代码:
#define int long long
#define rep(i,x,y) for(int i = (x); i <= (y); i ++)
#define dec(i,y,x) for(int i = (y); i >= (x); i --)
const int N = 1e7 + 10;
int a[N];
int n,a1,x,y,m,k;
void solve()
{
cin >> n >> a1 >> x >> y >> m >> k;
a[1] = a1;
rep(i,2,n)
{
a[i] = (a[i-1] * x + y) % m;
}
rep(i,0,k)
{
rep(j,2,n)
{
a[j] = (a[j] + a[j-1]) % mod;
}
if(i > 1) dec(j,n,1) a[j] = a[j-1];
}
int ans = 0;
rep(i,1,n) ans ^= (a[i] * i);
cout << ans << endl;
}