热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

洛谷P4705玩游戏(生成函数+多项式运算)

题面传送门题解妈呀这辣鸡题目调了我整整三天……最后发现竟然是因为分治\(NTT\)之后的多项式长度不是\(2\)的幂导致把多项式的值存下来的时候发生了一些玄学错误……玄学到了我\(WA\)

题面

传送门

题解

妈呀这辣鸡题目调了我整整三天……最后发现竟然是因为分治\(NTT\)之后的多项式长度不是\(2\)的幂导致把多项式的值存下来的时候发生了一些玄学错误……玄学到了我\(WA\)的点全都是\(WA\)\(2\)的幂次行里……

看到这种题目二话不说先推倒

\[ \begin{aligned} [x^k]Ans &={1\over nm}\sum_{i=1}^n\sum_{j=1}^m\left(a_i+b_j\right)^k\\ &={1\over nm}\sum_{i=1}^n\sum_{j=1}^m\sum_{p=0}^k{k\choose p}{a_i}^p{b_j}^{k-p}\\ &={k!\over nm}\sum_{p=0}^k{\sum_{i=1}^n{a_i}^p\over p!}{\sum_{j=1}^m{b_j}^{k-p}\over (k-p)!}\\ \end{aligned} \]

然后这就被画成了一个卷积的形式

定义两个多项式\(A(x)=\sum_{i=0}^\infty x^i\sum_{j=1}^n{a_j}^i\),和\(B(x)=\sum_{i=0}^\infty x^i\sum_{j=1}^m{b_j}^i\),只要我们能求出这两个多项式的系数,然后一通乱搞之后就能求出\(Ans\)

然后继续推倒

\[ \begin{aligned} A(x) &=\sum_{i=0}^\infty x^i\sum_{j=1}^n{a_j}^i\\ &=\sum_{j=1}^n\sum_{i=0}^\infty {a_j}^ix^i\\ &=\sum_{i=1}^n{1\over 1-a_ix}\\ &=\sum_{i=1}^n {a_i}^0+{a_i}^1x^1+{a_i}^2x^2+... \end{aligned} \]

所以……这玩意儿该咋算啊……

我们设

\[ \begin{aligned} G(x) &=\sum_{i=1}^n{-a_i\over 1-a_ix}\\ &=\sum_{i=1}^n-{a_i}^1-{a_i}^2x-{a_i}^3x^2-...\\ \end{aligned} \]

那么就有\(A(x)=-xG(x)+n\)

然而我还是不会算\(G\)啊……

那就继续推倒

\[ \begin{aligned} G(x) &=\sum_{i=1}^n{-a_i\over 1-a_ix}\\ &=\sum_{i=1}^n\ln'\left(1-a_ix\right)\\ &=\ln'\left(\prod_{i=1}^n (1-a_ix)\right) \end{aligned} \]

分治\(NTT\)就行啦

然后没有然后了

我错了多项式比计算几何难调多了

//minamoto
#include
#define R register
#define fp(i,a,b) for(R int i=(a),I=(b)+1;iI;--i)
#define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)
using namespace std;
char buf[1<<21],*p1=buf,*p2=buf;
inline char getc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}
int read(){
    R int res,f=1;R char ch;
    while((ch=getc())>'9'||ch<'0')(ch=='-')&&(f=-1);
    for(res=ch-'0';(ch=getc())>='0'&&ch<='9';res=res*10+ch-'0');
    return res*f;
}
char sr[1<<21],z[20];int C=-1,Z=0;
inline void Ot(){fwrite(sr,1,C+1,stdout),C=-1;}
void print(R int x){
    if(C>1<<20)Ot();if(x<0)sr[++C]='-',x=-x;
    while(z[++Z]=x%10+48,x/=10);
    while(sr[++C]=z[Z],--Z);sr[++C]='\n';
}
const int N=(1<<18)+5,P=998244353,Gi=332748118;
inline int add(R int x,R int y){return x+y>=P?x+y-P:x+y;}
inline int dec(R int x,R int y){return x-y<0?x-y+P:x-y;}
inline int mul(R int x,R int y){return 1ll*x*y-1ll*x*y/P*P;}
int ksm(R int x,R int y){
    R int res=1;
    for(;y;y>>=1,x=mul(x,x))if(y&1)res=mul(res,x);
    return res;
}
vectorr[21];int rt[2][N<<1],inv[N],fac[N],ifac[N],lim,d;
inline void init(R int len){lim=1,d=0;while(lim>1]>>1)|((i&1)<<(d-1));
    }
    inv[0]=inv[1]=fac[0]=fac[1]=ifac[0]=ifac[1]=1;
    fp(i,2,262144){
        fac[i]=mul(fac[i-1],i),
        inv[i]=mul(P-P/i,inv[P%i]),
        ifac[i]=mul(ifac[i-1],inv[i]);
    }
    for(R int t=(P-1)>>1,i=1,x,y;i<=262144;i<<=1,t>>=1){
        x=ksm(3,t),y=ksm(Gi,t);
        rt[1][i]=rt[0][i]=1;
        fp(k,1,i-1){
            rt[1][k+i]=mul(rt[1][k+i-1],x),
            rt[0][k+i]=mul(rt[0][k+i-1],y);
        }
    }
}
int rev[N];
void NTT(int *A,int ty){
    fp(i,0,lim-1)if(i>1),init(len<<1);
    static int A[N],B[N];
    fp(i,0,len-1)A[i]=a[i],B[i]=b[i];
    fp(i,len,lim-1)A[i]=B[i]=0;
    NTT(A,1),NTT(B,1);
    fp(i,0,lim-1)A[i]=mul(A[i],mul(B[i],B[i]));
    NTT(A,0);
    fp(i,0,len-1)b[i]=dec(add(b[i],b[i]),A[i]);
    fp(i,len,lim-1)b[i]=0;
}
void Ln(int *a,int *b,int len){
    static int A[N],B[N];
    fp(i,1,len-1)A[i-1]=mul(a[i],i);A[len-1]=0;
    Inv(a,B,len),init(len<<1);fp(i,len,lim-1)A[i]=B[i]=0;
    NTT(A,1),NTT(B,1);
    fp(i,0,lim-1)A[i]=mul(A[i],B[i]);
    NTT(A,0);
    fp(i,1,len-1)b[i]=mul(A[i-1],inv[i]);b[0]=0;
    fp(i,len,lim-1)b[i]=0;
}
int D[25][N];
void solve(int *a,int d,int l,int r){
    if(l==r)return D[d][0]=1,D[d][1]=P-a[l],void();
    int mid=(l+r)>>1;
    solve(a,d,l,mid),solve(a,d+1,mid+1,r),init(r-l+1+1);
    static int A[N],B[N];
    fp(i,0,mid-l+1)A[i]=D[d][i];fp(i,mid-l+2,lim-1)A[i]=0;
    fp(i,0,r-mid)B[i]=D[d+1][i];fp(i,r-mid+1,lim-1)B[i]=0;
    NTT(A,1),NTT(B,1);
    fp(i,0,lim-1)A[i]=mul(A[i],B[i]);
    NTT(A,0);
    fp(i,0,r-l+1)D[d][i]=A[i];
    fp(i,r-l+2,lim-1)D[d][i]=0;
}
int a[N],b[N],ak[N],bk[N];
int n,m,t;
void calc(int *a,int *b,int n,int t){
    static int A[N],B[N];
    solve(a,1,1,n);
    init(t+1);int len=lim;
    fp(i,0,n)A[i]=D[1][i];
    fp(i,n+1,len-1)A[i]=0;
    Ln(A,B,len);
    fp(i,1,len-1)B[i-1]=mul(B[i],i);B[len-1]=0;
    b[0]=n;
    fp(i,1,t)b[i]=mul(P-B[i-1],ifac[i]);
}
void Mul(int *a,int *b){
    init(t<<1);
    NTT(a,1),NTT(b,1);
    fp(i,0,lim-1)a[i]=mul(a[i],b[i]);
    NTT(a,0);
    int invm=ksm(mul(n,m),P-2);
    fp(i,1,t)print(1ll*a[i]*fac[i]%P*invm%P);
}
int main(){
//  freopen("testdata.in","r",stdin);
    Pre();
    n=read(),m=read();
    fp(i,1,n)a[i]=read();
    fp(i,1,m)b[i]=read();
    t=read();
    calc(a,ak,n,t),calc(b,bk,m,t);
    Mul(ak,bk);
    return Ot(),0;
}

推荐阅读
  • Splay Tree 区间操作优化
    本文详细介绍了使用Splay Tree进行区间操作的实现方法,包括插入、删除、修改、翻转和求和等操作。通过这些操作,可以高效地处理动态序列问题,并且代码实现具有一定的挑战性,有助于编程能力的提升。 ... [详细]
  • 本文探讨了如何在给定整数N的情况下,找到两个不同的整数a和b,使得它们的和最大,并且满足特定的数学条件。 ... [详细]
  • golang常用库:配置文件解析库/管理工具viper使用
    golang常用库:配置文件解析库管理工具-viper使用-一、viper简介viper配置管理解析库,是由大神SteveFrancia开发,他在google领导着golang的 ... [详细]
  • 优化ListView性能
    本文深入探讨了如何通过多种技术手段优化ListView的性能,包括视图复用、ViewHolder模式、分批加载数据、图片优化及内存管理等。这些方法能够显著提升应用的响应速度和用户体验。 ... [详细]
  • 本文将介绍如何编写一些有趣的VBScript脚本,这些脚本可以在朋友之间进行无害的恶作剧。通过简单的代码示例,帮助您了解VBScript的基本语法和功能。 ... [详细]
  • Explore how Matterverse is redefining the metaverse experience, creating immersive and meaningful virtual environments that foster genuine connections and economic opportunities. ... [详细]
  • 本文介绍如何使用Objective-C结合dispatch库进行并发编程,以提高素数计数任务的效率。通过对比纯C代码与引入并发机制后的代码,展示dispatch库的强大功能。 ... [详细]
  • 本文介绍如何利用动态规划算法解决经典的0-1背包问题。通过具体实例和代码实现,详细解释了在给定容量的背包中选择若干物品以最大化总价值的过程。 ... [详细]
  • 题目描述:给定n个半开区间[a, b),要求使用两个互不重叠的记录器,求最多可以记录多少个区间。解决方案采用贪心算法,通过排序和遍历实现最优解。 ... [详细]
  • 360SRC安全应急响应:从漏洞提交到修复的全过程
    本文详细介绍了360SRC平台处理一起关键安全事件的过程,涵盖从漏洞提交、验证、排查到最终修复的各个环节。通过这一案例,展示了360在安全应急响应方面的专业能力和严谨态度。 ... [详细]
  • 本实验主要探讨了二叉排序树(BST)的基本操作,包括创建、查找和删除节点。通过具体实例和代码实现,详细介绍了如何使用递归和非递归方法进行关键字查找,并展示了删除特定节点后的树结构变化。 ... [详细]
  • 本教程涵盖OpenGL基础操作及直线光栅化技术,包括点的绘制、简单图形绘制、直线绘制以及DDA和中点画线算法。通过逐步实践,帮助读者掌握OpenGL的基本使用方法。 ... [详细]
  • Java编程实践:深入理解方法重载
    本文介绍了Java中方法重载的概念及其应用。通过多个示例,详细讲解了如何在同一类中定义具有相同名称但不同参数列表的方法,以实现更灵活的功能调用。 ... [详细]
  • 本文探讨了《魔兽世界》中红蓝两方阵营在备战阶段的策略与实现方法,通过代码展示了双方如何根据资源和兵种特性进行战士生产。 ... [详细]
  • Codeforces Round #566 (Div. 2) A~F个人题解
    Dashboard-CodeforcesRound#566(Div.2)-CodeforcesA.FillingShapes题意:给你一个的表格,你 ... [详细]
author-avatar
手机用户2702932415_836
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有