首页 > 其他分享 >P6667 [清华集训2016] 如何优雅地求和 题解

P6667 [清华集训2016] 如何优雅地求和 题解

时间:2024-11-06 09:42:48浏览次数:3  
标签:nonumber mf int 题解 sum binom 2016 P6667 mod

一道非常有启发性的题目。

思路

考虑对于一个给出点值的多项式函数如何处理。

我们发现,对于一个 \(m\) 次多项式 \(f(x)\),由于 \(\binom{x}{i}\) 为 \(i\) 次多项式,所以说我们必定可以把一个多项式函数写成如下模样:

\[F(k)=\sum_{i=0}^m\binom{k}{i}f_i \]

可以看出,\(f_i\) 实际上是非常好得到的。

我们可以进行二项式反演。

\[\begin{align} f_k&=\sum_{i=0}^m \binom{k}{i}(-1)^{k-i}F(i)\nonumber \\ &=k!\sum_{i=0}^m \frac{F(i)}{i!}\frac{(-1)^{k-i}}{(k-i)!}\nonumber \end{align} \]

卷积处理即可。

这样的话我们就可以使用简单的组合数快速求出多项式的点值。

感觉这个操作还是很巧妙的,可能还比较通用。

对于这道题,剩下的部分就很简单了,我们可以:

\[\begin{align} &=\sum_{k=0}^n\sum_{i=0}^m\binom{k}{i}f_i\binom{n}{k}x^k(1-x)^{n-k}\nonumber\\ &=\sum_{i=0}^mf_i\sum_{k=0}^n\binom{k}{i}\binom{n}{k}x^k(1-x)^{n-k}\nonumber\\ &=\sum_{i=0}^mf_i\sum_{k=0}^n\frac{n!k!}{k!(n-k)!i!(k-i)!}x^k(1-x)^{n-k}\nonumber\\ &=\sum_{i=0}^mf_i\frac{n!}{i!}\sum_{k=0}^n\frac{1}{(n-k)!(k-i)!}x^k(1-x)^{n-k}\nonumber\\ &=\sum_{i=0}^mf_i\frac{n!}{i!(n-i)!}\sum_{k=0}^n\frac{(n-i)!}{(n-k)!(k-i)!}x^k(1-x)^{n-k}\nonumber\\ &=\sum_{i=0}^mf_i\binom{n}{i}\sum_{k=0}^n\binom{n-i}{k-i}x^k(1-x)^{n-k}\nonumber\\ &=\sum_{i=0}^mf_i\binom{n}{i}\sum_{k=0}^{n-i}\binom{n-i}{k}x^{k+i}(1-x)^{n-k-i}\nonumber\\ &=\sum_{i=0}^mf_ix^i\binom{n}{i}\sum_{k=0}^{n-i}\binom{n-i}{k}x^{k}(1-x)^{n-i-k}\nonumber\\ &=\sum_{i=0}^mf_ix^i\binom{n}{i} (x+1-x)^{n-i}\nonumber\\ &=\sum_{i=0}^mf_ix^i\binom{n}{i}\nonumber\\ \end{align} \]

复杂度瓶颈在前面的处理 \(f_i\)。

时间复杂度:\(O(m\log m)\)。

Code

#include <bits/stdc++.h>
using namespace std;

const int mod = 998244353;
const int G = 3;
const int I = 332748118;

int n, m, x, k;
int a[20010];
int fc[20010];
int iv[20010];
int f[1 << 16];
int g[1 << 16];
int b[1 << 16];
int w[1 << 16];

inline int power(int x, int y) {
  int res = 1;
  while (y) {
    if (y & 1) res = 1ll * res * x % mod;
    x = 1ll * x * x % mod, y >>= 1;
  }
  return res;
}
inline void init(int n) {
  int x = __lg(n) + 1;
  if (k == (1 << x)) return;
  k = (1 << x);
  for (int i = 0; i < k; i++)
    b[i] = (b[i >> 1] >> 1) | ((i & 1) ? (k >> 1) : 0);
}
inline void ntt(int *f, int n, int flag) {
  init(n), w[0] = 1;
  for (int i = 0; i < k; i++) if (i < b[i]) swap(f[i], f[b[i]]);
  for (int i = 1; i < k; i <<= 1) {
    int b = i << 1;
    int w0 = power((flag ? G : I), (mod - 1) / b);
    for (int j = 1; j < i; j++) w[j] = 1ll * w[j - 1] * w0 % mod;
    for (int j = 0; j < k; j += b) {
      for (int l = 0; l < i; l++) {
        int x = f[j + l], y = 1ll * f[j + l + i] * w[l] % mod;
        f[j + l] = (x + y >= mod ? x + y - mod : x + y);
        f[j + l + i] = (x - y < 0 ? x - y + mod : x - y);
      }
    }
  }
  if (flag == 0) {
    int iv = power(k, mod - 2);
    for (int i = 0; i < k; i++) f[i] = 1ll * f[i] * iv % mod;
  }
}

int main() {
  cin >> n >> m >> x;
  for (int i = 0; i <= m; i++) cin >> a[i];
  fc[0] = 1;
  for (int i = 1; i <= m; i++) fc[i] = 1ll * fc[i - 1] * i % mod;
  iv[m] = power(fc[m], mod - 2);
  for (int i = m; i >= 1; i--) iv[i - 1] = 1ll * iv[i] * i % mod;
  for (int i = 0; i <= m; i++) {
    f[i] = 1ll * a[i] * iv[i] % mod;
    g[i] = (i & 1 ? mod - iv[i] : iv[i]);
  }
  ntt(f, m + m, 1);
  ntt(g, m + m, 1);
  for (int i = 0; i < k; i++)
    f[i] = 1ll * f[i] * g[i] % mod;
  ntt(f, m + m, 0);
  int sm = 1;
  int ns = 0;
  for (int i = 0; i <= m; i++) {
    ns = (ns + 1ll * sm * f[i]) % mod;
    sm = (1ll * sm * x) % mod;
    sm = (1ll * sm * (n - i)) % mod;
  }
  cout << ns << "\n";
}

标签:nonumber,mf,int,题解,sum,binom,2016,P6667,mod
From: https://www.cnblogs.com/JiaY19/p/18529316

相关文章

  • CSP-J2024题解
    T1扑克牌本题要求:在给定的扑克牌的基础上,还需要多少张牌可以让扑克牌凑成一整套,试题中读入的字符串每个都代表一张合法的扑克牌。可以使用C++STL中的set(集合)完成本题。这是因为,set可以自动去重,去除重复的牌(字符串)后,剩下的字符串就是实际拥有的不同的牌。而一副扑克牌有......
  • ABC378 E 题解
    ABC378E题解题意给定序列\(A\),求\(\sum_{1\lel\ler\len}(\sum_{l\lei\ler}A_i\modM)\)计算所有区间和取模之后的结果再求和。注意外层是没有取模的。如果是外层也要取模的情况,那还是十分好办的,直接贡献法计算每个数字被统计了多少次就可以了。问题就在于外层没......
  • 2024强网杯web题解
    PyBlocklyfromflaskimportFlask,request,jsonifyimportreimportunidecodeimportstringimportastimportsysimportosimportsubprocessimportimportlib.utilimportjsonapp=Flask(__name__)app.config['JSON_AS_ASCII']=Falseblacklis......
  • 2024newstarweb题解
    w1headach3会赢吗源码flag碎片X1:ZmxhZ3tXQTB3再次查看源码flag碎片X2:IV95NF9yM2Fs第三个页面也是直接查看源码直接改源码flag碎片X3:MXlfR3I0c1B下一个页面直接禁用jsflag碎片X4:fSkpKcyF9ZmxhZ3tXQTB3IV95NF9yM2FsMXlfR3I0c1BfSkpKcyF9base64解码即......
  • WPF程序弹出页中按钮在触摸屏(电容屏)上点击事件需要点十次才能触发的问题解决方法
    一、事件背景介绍1.功能简述:主页面是一个DataGrid列表,点击DataGrid行,弹出子页面;子页面根据数据加载多个Button按钮,如下图,就是这个页面中的按钮,在触摸屏上触摸点击,需要点击十次才能成功,使用鼠标点击一下就能成功。 主要代码如下://WPF前端<DataGridx:Name="scanDtl......
  • P11236 「KTSC 2024 R1」水果游戏 题解
    很有意思的一道题。思路首先将相邻一样的数合并,每个元素变成一个二元组,表示数与出现次数。考虑什么时候不能合并。我们发现假如充分合并后,现在有连续的三个数\(x_1,x_2,x_3\),以及他们各自的出现次数\(y_1,y_2,y_3\)。如果\(x_1>x_2,x_3>x_2\)。我们想要合并这三个,必须要......
  • 国标GB28181-2016平台LiteGBS国标GB28181设备端接入SDK国标级联共享功能的优势体现在
    在现代安防监控领域,视频监控管理平台的国标级联共享功能是实现跨区域、跨系统资源整合与共享的关键技术。LiteGBS平台以其卓越的性能和广泛的兼容性,为用户提供了一个高效、可靠的解决方案。本文将详细介绍国标GB28181-2016平台LiteGBS在国标级联共享方面的五大优势,展示其如何帮助......
  • 在‌Windows Server 2016中显示‌桌面图标的方法
    通过运行对话框‌:按下Win+R键,打开运行对话框。输入命令  rundll32.exeshell32.dll,Control_RunDLLdesk.cpl,,0 然后按回车键或点击确定按钮。这将打开桌面图标设置功能,你可以在其中勾选想要显示的图标。‌ 详细步骤说明‌打开运行对话框‌:按下Win+R键,打开运行对......
  • xss-labs题解
    xss—labsxss—labslevel1(GET型)level2(闭合)level3(htmlspecialchars绕过)level4(左右尖括号过滤)level5(a标签法)level6(大小写绕过)level7(双写绕过)level8(利用href自动Unicode解码特性)level9(注释绕过后端判断)xss—labs题目链接BUUCTF在线评测题目源码xss-lab/lev......