原文链接www.cnblogs.com/zhouzhendong/p/LOJ565.html

前言

标算真是优美可惜这题直接暴力FFT算一算就solved了。

题解

首先，假装没有进位，考虑解决这个问题。

对于每一位，考虑作用在其之上的概率为 \(p\) 的操作，构建多项式 \(((1-p) + px )\)，那么将一个位置上所有这样的多项式乘起来之后， \(x^k\) 项系数就代表这个位置被操作 \(k\) 次的概率。对答案的贡献就是 \(k\times\) \(x^k\) 项系数。

考虑进位。

从低位向高位推，进位就相当于将多项式系数两个两个合并。

从低位向高位，考虑将每一位的多项式两个两个合并之后乘到高一位的多项式上，就可以得出每一位被变换任意次的真的概率。

考虑这个过程的复杂度：

一个多项式的长度对其高位长度的贡献依次是 $len, len / 2, len / 4, len / 2 ^ 3 ,\cdots $ ，所以总贡献是 \(O(len)\) 的。由于多项式总长度为 \(O(n+m)\) ，又由于乘法在FFT时有个log，所以这部分的总时间复杂度为 \(O((n+m)\log m)\)。

而前一半需要分治FFT来算多项式，复杂度为 \(O(m\log ^ 2m)\) 。

总时间复杂度为 \(O(n\log m + m\log ^ 2 m)\) 。

代码

#include 
    
     #define clr(x) memset(x,0,sizeof x)#define For(i,a,b) for (int i=(a);i<=(b);i++)#define Fod(i,b,a) for (int i=(b);i>=(a);i--)#define fi first#define se second#define pb(x) push_back(x)#define mp(x,y) make_pair(x,y)#define outval(x) cerr<<#x" = "<
     
      <