题目大意
已知 (n)、(s)、(d)，令 (a_0 = s)，(a_n = a_{n-1} + d)，求 ((sum_{k=0}^{n} a_k imes C_n^k) \% 998244353) 的值。
保证 (n)，(s)，(d le 10^{18})。
题目分析
先给出组合数公式 (C_n^m = frac{n!}{m!(n-m)!}) 。
第一眼看，发现 (a_n = s + n imes d) ，唯一比较难搞的是阶乘。递归 (n le 10^{18}) 明显不行，我们猜想，可能通过某个公式可以解决。
膜拜 (xsl666) 数论带师考场手玩数论题吊打蒟蒻
这种东西你推到了就非常简单，推不到就挠头ing。
正解
我们先给出一个组合恒等式
[k imes C_n^k = n imes C_{n-1}^{k-1}
]
根据上式得推论
[sum_{k=1}^{n} k imes C_n^k = sum_{k=1}^{n} n imes C_{n-1}^{k-1} = n imes sum_{k=1}^{n} C_{n-1}^{k-1} = n imes sum_{k=0}^{n-1} C_{n-1}^{k} = n imes w^{n-1}
]
再根据 (a_k = s + k imes d) 得
[sum_{k=0}^{n} a_k imes C_n^k = sum_{k=0}^{n} (s + kd) imes C_n^k = s imes sum_{k=0}^n C_n^k + d imes sum_{k=0}^n k imes C_n^k
]
打表后得到最终答案为
[s 2^{n} + nd2^{n-1} = (2s+nd)2^{n-1}
]
那么我们只需要用快速幂求 (2^{n-1}) 即可。
值得注意的是，在输出时最好把快速幂答案单独存在一个变量中，因为直接调用快速幂函数返回值不知道为什么会少 (40) 分。
代码
#include<bits/stdc++.h>
#include<cctype>
#pragma GCC optimize(2)
#define in(a) a = read()
#define out(a) write(a)
#define outn(a) out(a),putchar('
')
#define ll long long
#define rg register
using namespace std;
inline ll read()
{
ll X = 0,w = 0;
char ch = 0;
while(!isdigit(ch))
{
w |= ch == '-';
ch=getchar();
}
while(isdigit(ch))
{
X = (X << 3) + (X << 1) + (ch ^ 48);
ch = getchar();
}
return w ? -X : X;
}
char F[200] ;
inline void write(ll x)
{
if(x == 0)
{
putchar('0');
return;
}
ll tmp = x > 0 ? x : -x;
int cnt = 0;
if(x < 0)
putchar( '-' );
while(tmp > 0)
{
F[cnt++] = tmp % 10 + '0';
tmp /= 10;
}
while(cnt > 0)
putchar(F[--cnt]) ;
}
const int mod = 998244353;
ll n, s, d;
ll ksm(ll a, ll b)
{
ll ans = 1;
while(b)
{
if(b & 1)
ans = ans * a % mod;
a = a * a % mod;
b >>= 1;
}
return ans;
}
int main()
{
freopen("problem.in","r",stdin);
freopen("problem.out","w",stdout);
in(n), in(s), in(d);
ll p = ksm(2, n-1);
s %= mod, d %= mod, n %= mod;
outn( ((s<<1) + n*d%mod) * p%mod);
return 0;
}