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

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

时间:2023-03-15 18:22:25浏览次数:48  
标签:ll limits int 题解 sum binom 2016 P6667 underline

orz fjy666 orz fjy666 orz fjy666

神 · fjy666 · 拉普拉斯 · 爱因斯坦大帝于 5min 内爆切了此题,膜拜!

思路

斯特林数。

注意到 \(f(k)\) 是多项式而式子中含有组合数,于是考虑到普通多项式转下降幂多项式。

不妨设 \(f(k) = \sum\limits_{i = 0}^m f_i k^i = \sum\limits_{i = 0}^m b_i k^{\underline{i}}\).

我们知道当 \(m\) 较小时可以 \(O(m^2)\) 通过 \(f_i\) 求出 \(b_i\),但是这里给出的是多项式的点值。

暂且忽略,尝试用下降幂多项式化简。

代入多项式有:\(Q(f, n, x) = \sum\limits_{k = 0}^n f(k) \binom{n}{k} x^k (1 - x)^{n - k} \sum\limits_{i = 0}^m b_i k^{\underline{i}}\).

整理成多项式的形式是:\(\sum\limits_{i = 0}^m b_i \sum\limits_{k = 0}^n k^{\underline{i}} \binom{n}{k} x^k (1 - x)^{n - k}\).

注意到下降幂和组合数有结论:\(\binom{n}{k} k^{\underline{i}} = n^{\underline{i}} \binom{n - i}{k - i}\).

于是原式等价于 \(\sum\limits_{i = 0}^m b_i \sum\limits_{k = 0}^n n^{\underline{i}} \binom{n - i}{k - i} x^k (1 - x)^{n - k}\).

整理一下得 \(\sum\limits_{i = 0}^m b_i n^{\underline{i}} \sum\limits_{k = 0}^n \binom{n - i}{k - i} x^k (1 - x)^{n - k}\).

后面的和式可以换种写法:\(\sum\limits_{i = 0}^m b_i n^{\underline{i}} \sum\limits_{k = 0}^{n - i} \binom{n - i}{k} x^{k + i} (1 - x)^{n - k - i}\).

提出来 \(x^k\) 就可以二项式定理:\(\sum\limits_{i = 0}^m b_i n^{\underline{i}} x^k \sum\limits_{k = 0}^{n - i} \binom{n - i}{k} x^i (1 - x)^{n - k - i} = \sum\limits_{i = 0}^m b_i n^{\underline{i}} x^k (1 - x + x)^{n - k} = \sum\limits_{i = 0}^m b_i n^{\underline{i}} x^k\).

于是只需要求出 \(b\).

考虑多项式 \(f\) 点值的 EGF:\(\sum\limits_{n} \frac{f(n) x^n}{n!}\).

把 \(f(n)\) 代入得 \(\sum\limits_{n} \frac{x^n}{n!} \sum\limits_{i = 0}^m b_i n^{\underline{i}}\).

注意到 \(n^{\underline{i}} n! = \frac{n!}{(n - i)!} \frac{1}{n!} = \frac{1}{(n - i)!}\).

于是有原式等于 \(\sum\limits_{i = 0}^m b_i \sum\limits_{n} \frac{x^n}{n!} n^{\underline{i}} = \sum\limits_{i = 0}^m b_i x^i \sum\limits_{n} \frac{x^{n - i}}{(n - i)!}\).

明显是两个多项式的卷积形式,于是 \(O(n \log n)\) 可以解决。

代码

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;

typedef long long ll;

const int maxm = 2e4 + 5;
const int sz = 2e5 + 5;
const int mod = 998244353;
const int g = 3;

int n, m, x;
int a[maxm], rev[sz];
ll F[sz], G[sz];
ll fac[sz], invf[sz], wp[sz];

inline int read()
{
    int res = 0, flag = 1;
    char ch = getchar();
    while ((ch < '0') || (ch > '9'))
    {
        if (ch == '-') flag = -1;
        ch = getchar();
    }
    while ((ch >= '0') && (ch <= '9')) res = res * 10 + ch - '0', ch = getchar();
    return res * flag;
}

void calc_rev(int k) { for (int i = 0; i < k; i++) rev[i] = (rev[i >> 1] >> 1 | (i & 1 ? k >> 1 : 0)); }

ll qpow(ll base, ll power, ll mod)
{
    ll res = 1;
    while (power)
    {
        if (power & 1) res = res * base % mod;
        base = base * base % mod, power >>= 1;
    }
    return res;
}

ll qpow(int x) { return (x % 2 == 0 ? 1 : mod - 1); }

void NTT(ll* A, int n)
{
    calc_rev(n);
    for (int i = 0; i < n; i++)
        if (rev[i] > i) swap(A[i], A[rev[i]]);
    for (int len = 2, m = 1; len <= n; m = len, len <<= 1)
    {
        ll wn = qpow(g, (mod - 1) / len, mod) % mod;
        wp[0] = 1;
        for (int i = 1; i <= len; i++) wp[i] = wp[i - 1] * wn % mod;
        for (int l = 0, r = len - 1; r <= n; l += len, r += len)
        {
            int w = 0;
            for (int p = l; p < l + m; p++, w++)
            {
                ll x = A[p], y = wp[w] * A[p + m] % mod;
                A[p] = (x + y) % mod, A[p + m] = (x - y + mod) % mod;
            }
        }
    }
}

void INTT(ll *A, int n)
{
    NTT(A, n), reverse(A + 1, A + n);
    int inv = qpow(n, mod - 2, mod);
    for (int i = 0; i < n; i++) A[i] = A[i] * inv % mod;
}

void times(ll *F, ll *G, int lf, int lg, int lim)
{
    int len = lf + lg - 1, k = 1;
    while (k < len) k <<= 1;
    NTT(F, k), NTT(G, k);
    for (int i = 0; i < k; i++) F[i] = F[i] * G[i] % mod;
    INTT(F, k), INTT(G, k);
    for (int i = lim; i < k; i++) F[i] = 0;
}

void init(int lim)
{
    fac[0] = invf[0] = fac[1] = invf[1] = 1;
    for (int i = 2; i <= lim; i++) fac[i] = fac[i - 1] * i % mod, invf[i] = (mod - mod / i) * invf[mod % i] % mod;
    for (int i = 2; i <= lim; i++) invf[i] = invf[i - 1] * invf[i] % mod;
}

int main()
{
    scanf("%d%d%d", &n, &m, &x);
    init(m);
    for (int i = 0; i <= m; i++) F[i] = invf[i] * qpow(i) % mod;
    for (int i = 0; i <= m; i++) G[i] = invf[i] * read() % mod;
    times(F, G, m + 1, m + 1, m + 1);
    for (int i = 0; i <= m; i++) F[i] = F[i] * fac[i] % mod;
    int cur = 1, ans = 0;
    for (int i = 0; i <= m; i++) ans = (ans + 1ll * cur * F[i] % mod * invf[i] % mod) % mod, cur = 1ll * cur * x % mod * (n - i) % mod;
    printf("%d\n", ans);
    return 0;
}

标签:ll,limits,int,题解,sum,binom,2016,P6667,underline
From: https://www.cnblogs.com/lingspace/p/p6667.html

相关文章

  • 公众号前端访问后台500 疑难问题解决
     后台日志联调,发现前端根本无法进入后台方法中去经过仔细对比发现referrer请求过长在主设置页面增加<metaname="referrer"content="origin">配置问题解决 ......
  • 阿里一面:15道网络安全真题解析,你能答对几道?
    前言网络安全是一个广阔的领域,面试过程中可能会提出各种各样的问题。招聘人员主要关注技术方面以及工具和技术知识,以确保框架安全。 以下是在网络安全领域寻求工作时可能......
  • 2023.3.14 状压 dp 模拟赛题解
    好强啊。不说是谁了,都好强啊呜呜呜。   首先T1的一个优化luoguP1842奶牛玩杂技,需要一个贪心排序来优化序列顺序。关于贪心排序:像这样有两种及以上性质的序列,......
  • 2020年河南省CCPC 题解
    2020年河南省CCPC题解ProblemA.班委竞选设ax为第x类班干部最大票数。从小到大枚举学号i,若新x>ax则更新ax并且记录i为ansx的答案voidsolve(){intn=re......
  • P5200 [USACO19JAN]Sleepy Cow Sorting G 题解
    前言:教练要求写的,于是过来补发题解。题目传送门分析容易发现后缀如果是上升的那么就不用动,让前面的通过移动插进来就可以了,第一个答案就是\(n\)减去最长上升后缀的长......
  • CF1788D Moving Dots 题解
    可能更好的阅读体验题目传送门题目翻译题目解析考虑怎样才能产生贡献,显然对于留下的相邻的\(l,r\),需要让\(l\)向右,\(r\)向左即可产生\(1\)的贡献。接下来就是考......
  • [整理]NOIP2021 题解
    T1秒了,直接写一个线性筛一样的东西即可。constintN=10000010;intT,x;boolok[N];intnxt[N];ilvoidInit(){for(inti=1;i<N;i++){if(ok[i])continue;......
  • 【题解】P6071 『MdOI R1』Treequery
    题目描述给定一棵\(n\)个点的无根树,边有边权。令\(E(x,y)\)表示树上\(x,y\)之间的简单路径上的所有边的集合,特别地,当\(x=y\)时,\(E(x,y)=\varnothing\)。你需......
  • docker安装笔记及常见问题解决
    1.yum安装gcc相关环境yum-yinstallgccyum-yinstallgcc-c++2.卸载旧版本(非必要)yumremovedocker\docker-client\docker-client-latest\doc......
  • 由于找不到 visa32.dll问题解决办法
    由于找不到visa32.dll,无法继续执行代码。重新安装程序可能会解决此问题。 金山官网下载https://www.ijinshan.com/filerepair/visa32.dll.shtml由于找不到NiViSv32.d......