AtCoder Regular Contest 106 解题报告

arc106_d Powers

AtCoder Regular Contest 106 的第四题,数学。

题目链接:D – Powers

题意翻译

  • 给定长度为 \( N \) 的数列 \( A = \left( A _ 1 , A _ 2 , \cdots , A _ N \right) \) 和一个正整数 \( K \)。
  • 要你求对于每一个 \( X ( 1 \leq X \leq K ) \),下列式子的值
    \[ \left(\displaystyle \sum_{L=1}^{N-1} \sum_{R=L+1}^{N}(A_L+A_R)^X\right) \bmod 998244353\]
  • 数据范围:\( 2 \leq N \leq 2 \times 10 ^ 5 \),\( 1 \leq K \leq 300 \),\( 1 \leq A _ i \leq 10 ^ 8 \)。

题解

考虑直接化式子。

\[
\begin{aligned}
&\left( \sum _ { L = 1 } ^ { N – 1 } \sum _ { R = L + 1 } ^ N ( A _ L + A _ R ) ^ X \right) \\
&\equiv \left( \sum _ { L = 1 } ^ { N – 1 } \sum _ { R = L + 1 } ^ N \sum _ {i=0} ^ X \binom { X } { i } A _ L ^ i A _ R ^ { X – i } \right) \\
&\equiv \sum _ {i=0} ^ X \binom { X } { i } \frac { \sum _ { L = 1 } ^ N \sum _ { R = 1 } ^ N A _ L ^ i A _ R ^ { X – i } – \sum _ { L = 1 } ^ N A _ L ^ X} { 2 } \\
&\equiv \sum _ {i=0} ^ X \binom { X } { i } \frac { \sum _ { L = 1 } ^ N A _ L ^ i \sum _ { R = 1 } ^ N A _ R ^ { X – i } – \sum _ { L = 1 } ^ N A _ L ^ X } { 2 } \pmod {998244353}
\end{aligned}
\]

不妨设 \( i \) 次方的总和为 \( \text {sum} ^ i \),则发现答案为
\[ \sum _ {i=0} ^ X \binom { X } { i } \frac { \text {sum} ^ i \text {sum} ^ { X – i } – \text {sum} ^ X } { 2 } \bmod {998244353} \]

预处理二项式系数和次方和即可。

#include <bits/stdc++.h>
using namespace std;
#define reg register
typedef long long ll;
#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++)
static char buf[100000], *p1 = buf, *p2 = buf;
inline int read(void)
{
    reg bool f = false;
    reg char ch = getchar();
    reg int res = 0;
    while (!isdigit(ch))
        f |= (ch == '-'), ch = getchar();
    while (isdigit(ch))
        res = 10 * res + ch - '0', ch = getchar();
    return f ? -res : res;
}

const int MAXN = 2e5 + 5;
const int MAXK = 300 + 5;
const int p = 998244353;
const int inv2 = 499122177;

inline int add(reg int a, reg int b)
{
    reg int sum = a + b;
    return sum >= p ? sum - p : sum;
}

inline int mul(reg int a, reg int b)
{
    return 1ll * a * b % p;
}

int n, k;
int h[MAXK], C[MAXK][MAXK];

int main(void)
{
    n = read(), k = read();
    for (reg int i = 1; i <= n; ++i)
    {
        static int a;
        a = read();
        for (reg int j = 0, x = 1; j <= k; ++j, x = mul(x, a))
            h[j] = add(h[j], x);
    }
    C[0][0] = 1;
    for (reg int i = 1; i <= k; ++i)
    {
        C[i][0] = 1;
        for (reg int j = 1; j <= i; ++j)
            C[i][j] = add(C[i - 1][j - 1], C[i - 1][j]);
    }
    for (reg int i = 1; i <= k; ++i)
    {
        reg int ans = 0;
        for (reg int j = 0; j <= i; ++j)
            ans = add(ans, 1ll * C[i][j] * inv2 % p * add(p - h[i], mul(h[j], h[i - j])) % p);
        printf("%d\n", ans);
    }
    return 0;
}
Pages: 1 2 3 4 5 6 7 8