526互联

Educational Codeforces Round 148 (Rated for Div. 2)E. Combinatorics Problem（组合数，动态规划）

发布时间 2023-08-30 10:29:35作者: XiCen

题目链接：https://codeforces.com/contest/1832/problem/E

 

题意：

 

 

当然这是化简后的题意，原题面和这个差距还是有点大的；

 

分析：

 

因为组合数有公式：

 

 

所以：

 

 

 

嗯，然后就没有了；

 

时间复杂度：O（n*k）；

 

代码：

 

#include<bits/stdc++.h>
#define int long long

const int mod = 998244353;

signed main()
{
    std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);

    int n,x,y,m,k;
    std::cin>>n;
    std::vector<int> a(n+1,0);

    std::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 = 0;i<=k;++i)
        for(int j = 2;j<=n;++j)
            a[j] = (a[j]+a[j-1])%mod;

    int ans = 0;

    for(int i = k;i<=n;++i)
        ans ^= 1ll*i*a[i-k+1];

    std::cout<<ans<<"\n";

    return 0;
}

本题考察的是对于递推的理解和组合数的熟悉程度，码量小，很开心：）