注释:
$e^x$ 与 $ln(1-x)$ 的麦克劳林级数:
- $e^x=\sum_{
- i=0
- }\frac{
- x^i
- }{
- i!
- }$
- $ln(1-x)=-\sum_{
- i=1
- }\frac{
- x^i
- }{
- i
- }$
多项式 ln,exp 就是用这个定义的
以及, 在求 ln(y) 时的注意点:
令 1-x=y,x=1-y, 如果 y 的常数项不为 1, 那么 x 的常数项一定不为 0.ln(y)=ln(1-x)=$-\sum_{i=1}\frac{x^i}{i}$
x 的常数项 a 对于式子的右侧产生的贡献是 $-\sum_{i=1}\frac{a^i}{i}=ln(1-a)$(或者说 ln(y) 的常数项是这个), 当 a 不为 0 时这个东西模意义下一般都没办法算
做法: 看题解 https://www.luogu.org/problemnew/solution/P4725
设 G(x)=ln(F(x))
两边同时求导, 得 $G'(x)=ln'(F(x))F'(x)=\frac{F'(x)}{F(x)}$
这样可以求出 G'(x), 积分后得到 G(x) 除常数项之外的项
常数项怎么办?
根据 "注释" 的最后一句, G(x) 常数项等于模意义下 ln(F(x) 的常数项), 反正 F 的常数项不为 1 时, 我不会算; 刚好题目保证 F 的常数项为 1, 那么 G(x) 常数项就是 0
- #prag 2 ma GCC optimize(2)
- #include<cstdio>
- #include<algorithm>
- #include<cstring>
- #include<vector>
- #include<cmath>
- using namespace std;
- #define fi first
- #define se second
- #define mp make_pair
- #define pb push_back
- typedef long long ll;
- typedef unsigned long long ull;
- const int md=998244353;
- const int N=131072;
- int rev[N<<1];
- void init(int len)
- {
- int bit=0,i;
- while((1<<(bit+1))<=len) ++bit;
- for(i=0;i<len;++i)
- rev[i]=(rev[i>>1]>>1)|((i&1)<<(bit-1));
- }
- ll poww(ll a,ll b)
- {
- ll base=a,ans=1;
- for(;b;b>>=1,base=base*base%md)
- if(b&1)
- ans=ans*base%md;
- return ans;
- }
- void dft(int *a,int len,int idx)// 要求 len 为 2 的幂
- {
- int i,j,k,t1,t2;ll wn,wnk;
- for(i=0;i<len;++i)
- if(i<rev[i])
- swap(a[i],a[rev[i]]);
- for(i=1;i<len;i<<=1)
- {
- wn=poww(idx==1?3:332748118,(md-1)/(i<<1));
- for(j=0;j<len;j+=(i<<1))
- {
- wnk=1;
- for(k=j;k<j+i;++k,wnk=wnk*wn%md)
- {
- t1=a[k];t2=a[k+i]*wnk%md;
- a[k]+=t2;
- (a[k]>=md) && (a[k]-=md);
- a[k+i]=t1-t2;
- (a[k+i]<0) && (a[k+i]+=md);
- }
- }
- }
- if(idx==-1)
- {
- ll ilen=poww(len,md-2);
- for(i=0;i<len;++i)
- a[i]=a[i]*ilen%md;
- }
- }
- void p_inv(int *f,int *g,int len)//g=f^(-1);f,g 数组的长度不小于 2^(ceil(log2(len))+1)(需要足够长用于临时存放元素)
- {
- static int t1[N<<1];
- int n1=2;
- for(;n1<(len<<1);n1<<=1);
- memset(f+len,0,sizeof(int)*(n1-len));
- g[0]=poww(f[0],md-2);
- for(int i=2,j;i<(len<<1);i<<=1)
- {
- init(i<<1);
- memcpy(t1,f,sizeof(int)*i);
- memset(t1+i,0,sizeof(int)*i);
- memset(g+(i>>1),0,sizeof(int)*(i+(i>>1)));
- dft(t1,i<<1,1);dft(g,i<<1,1);
- for(j=0;j<(i<<1);++j)
- g[j]=ll(g[j])*(2+ll(md-g[j])*t1[j]%md)%md;
- dft(g,i<<1,-1);
- }
- memset(g+len,0,sizeof(int)*(n1-len));
- }
- int inv[300011];
- inline void p_de(int *f,int len)//derivative 求导; f=f'
- {
- for(int i=0;i<len-1;++i)
- f[i]=ll(i+1)*f[i+1]%md;
- f[len-1]=0;
- }
- inline void p_in(int *f,int len)//integral 积分; f=?f
- {
- for(int i=len-1;i>=1;--i)
- f[i]=ll(f[i-1])*inv[i]%md;
- f[0]=0;
- }
- void p_ln(int *f,int len)//f=ln(f);f 长度满足 inv 的限制
- {
- static int t1[N<<1];
- int n1=1,i;
- while(n1<len) n1<<=1;
- memset(f+len,0,sizeof(int)*(n1-len));
- p_inv(f,t1,n1);p_de(f,n1);
- init(n1<<1);
- dft(f,n1<<1,1);dft(t1,n1<<1,1);
- for(i=0;i<(n1<<1);++i)
- f[i]=ll(f[i])*t1[i]%md;
- dft(f,n1<<1,-1);
- p_in(f,n1);
- }
- int a[N<<1];
- int n;
- int main()
- {
- int i;
- inv[1]=1;
- for(i=2;i<=300000;++i)
- inv[i]=ll(md-md/i)*inv[md%i]%md;
- scanf("%d",&n);
- for(i=0;i<n;++i)
- scanf("%d",a+i);
- //for(int iii=1,p=n;iii<=50;++iii)
- // a[p++]=rand()%md;
- p_ln(a,n);
- for(i=0;i<n;++i)
- printf("%d",a[i]);
- return 0;
- }
- View Code
来源: http://www.bubuko.com/infodetail-2992236.html