付公主的背包

た入场券 2022-01-12 10:45 181阅读 0赞

[付公主的背包][Link 1]

数据范围过大的计数？

生成函数！

无穷项？转化成封闭形式

分母乘积再求逆

次数过大不能分治NTT？

分母乘积？

求Ln变成求和！

Ln？

有结论：

Ln![1399631-20190410221128704-526350654.png][]=![1399631-20190410221119847-787160876.png][]

--------------------

upda：2019.4.19：

证明：

1.Taylor展开

在x0=1的地方展开

2.

求导把ln里面的f(x)拿出来

![1399631-20190419075802193-78790459.png][]

（图片来源：[在Ta的博客查看][Ta]）

--------------------

就可以开桶，然后mlogm处理系数之和

求exp再求逆

int main(){
        int n,m;
        Poly f;
        
        rd(n);rd(m);
        f.resize(m+1);
        ni[1]=1;
        for(reg i=2;i<=m;++i) {
            ni[i]=(ll)(mod-mod/i)*ni[mod%i]%mod;
        }
        int v;
        for(reg i=1;i<=n;++i){
            rd(v);++buc[v];
        }
        for(reg i=1;i<=m;++i){
            if(buc[i]){
                for(reg j=i;j<=m;j+=i){
                    f[j]=ad(f[j],mul(mod-mul(i,ni[j]),buc[i]));
                }
            }
        }
    //    f.out();
        f=Exp(f);
        f=~f;
        for(reg i=1;i<=m;++i){
            printf("%d\n",f[i]);
        }
        return 0;
    }

求Ln把乘法变成加法的tirck

转载于:https://www.cnblogs.com/Miracevin/p/10686560.html

[Link 1]: https://www.luogu.org/problemnew/show/P4389
[1399631-20190410221128704-526350654.png]: https://img2018.cnblogs.com/blog/1399631/201904/1399631-20190410221128704-526350654.png
[1399631-20190410221119847-787160876.png]: /images/20220109/82652730bf3d47bd88bdbeee8cfff229.png
[1399631-20190419075802193-78790459.png]: /images/20220109/d2ed3086befe466cb34541ae654cb85e.png
[Ta]: https://2016gdgzoi509.blog.luogu.org/fu-gong-zhu-di-bei-bao

发表评论取消回复

表情：

评论列表（有 0 条评论，181人围观）

还没有评论，来说两句吧...

相关阅读

相关王子与公主

王子与公主 1、题目要求 > 题目描述(From JD) ![2020-09-17\_203823][2020-09-17_203823] > 示例 ![20

绝地灬酷狼/ 2022年12月08日 12:53/ 0 赞/ 144 阅读

相关背包问题详解：01背包、完全背包、多重背包

参考链接： 1. [http://www.cnblogs.com/fengty90/p/3768845.html][http_www.cnblogs.com_fengty9

蔚落/ 2022年09月30日 00:54/ 0 赞/ 312 阅读

相关 01背包完全背包多重背包的概念

01背包（ZeroOnePack）: 有N件物品和一个容量为V的背包，每种物品均只有一件。第i件物品的费用是c\[i\]，价值是w\

港控/mmm°/ 2022年08月07日 11:46/ 0 赞/ 279 阅读

相关 alipay demo当面付

demo下载地址:[https://doc.open.alipay.com/docs/doc.htm?spm=a219a.7629140.0.0.ZyIWRL&treeId=1

梦里梦外;/ 2022年07月13日 13:47/ 0 赞/ 181 阅读

相关背包问题(0-1背包、完全背包、多重背包)详解

背包问题一个背包总容量为V, 现在有N个物品, 第i个物品容量为weight\[i\], 价值为value\[i\], 现在往背包里面装东西, 怎样装才能使背包内物品总

柔情只为你懂/ 2022年06月08日 00:59/ 0 赞/ 388 阅读

相关算法——背包问题 01背包+完全背包+多重背包

01背包：https://biancheng.love/problem/51/index 有n 种不同的物品，每个物品有两个属性，weight重量，value 价值，现在给一

ゞ浴缸里的玫瑰/ 2022年06月06日 10:41/ 0 赞/ 360 阅读

相关背包问题—01背包、完全背包

01背包问题题目有m件物品和一个容量为V 的背包。放入第i 件物品占用的体积是Vi，得到的价值是Wi。求解将哪些物品装入背包可使价值总和最大。思路这

末蓝、/ 2022年05月30日 10:10/ 0 赞/ 413 阅读

相关 01背包、完全背包、多重背包问题的C++实现

01背包问题容量为10的背包，有5种物品，每种物品只有一个，其重量分别为5，4，3，2，1，其价值分别为1，2，3，4，5。设计算法，实现背包内物品价值最大。

淡淡的烟草味﹌/ 2022年05月30日 01:19/ 0 赞/ 297 阅读

相关背包问题-01背包，完全背包，多重背包

背包问题-01背包，完全背包，多重背包 -------------------- 01背包：概念：有Goods\_Num件物品，MAX\_V

太过爱你忘了你带给我的痛/ 2022年05月14日 09:23/ 0 赞/ 348 阅读

相关付公主的背包

[付公主的背包][Link 1] 数据范围过大的计数？生成函数！无穷项？转化成封闭形式分母乘积再求逆次数过大不能分治NTT？分母乘积？求Ln变成求和！

た入场券/ 2022年01月12日 10:45/ 0 赞/ 182 阅读