传送门 https://www.luogu.org/problemnew/show/P5162
题解
真是非常套路的一道题......
考虑 \(DP\): 设 \(f_n\) 为 \(n\) 个积木能搭出的方案数,\(g_n\) 为所有方案的高度之和.
容易得到转移方程:
\[ \begin{align*} &f_n=[n=0]+\sum_{i=1}^n {n \choose i} f_{n-i}\&g_n=\sum_{i=1}^n {n \choose i} (f_{n-i}+g_{n-i}) \end{align*} \]
发现 \(f_n\) 似乎更容易搞出来, 我们先搞 \(f_n\).
由转移方程可以得到:
\[ \frac{f_n}{n!}=[n=0]+\sum_{i=1}^n \frac{1}{i!} \frac{f_{n-i}}{(n-i)!} \]
设
\[ F(x)=\sum_n \frac{f_n}{n!} x^n\S(x)=\sum_{n=1}^{\infty} \frac{1}{n!} x^n \]
则有
\[ \begin{align*} F(x)-1&=F(x)S(x)\F(x)&=\frac{1}{1-S(x)} \end{align*} \]
多项式求逆即可.
接下来是求 \(g_n\).
令 \(t_n=f_n+g_n\), 则有
\[ \frac{g_n}{n!}=\sum_{i=1}^n \frac{1}{i!} \frac{t_{n-i}}{(n-i)!} \]
设
\[ \begin{align*} &G(x)=\sum_n \frac{g_n}{n!} x^n\&T(x)=\sum_n \frac{t_n}{n!}=F(x)+G(x) \end{align*} \]
可以得到
\[ G(x)=S(x)T(x)=S(x)F(x)+S(x)G(x)\G(x)=\frac{S(x)F(x)}{1-S(x)}=S(x)[F(x)]^2=F(x)(F(x)-1) \]
NTT 即可.
最后 \(ans_n=\frac{g_n}{f_n}\).
代码
- #include<bits/stdc++.h>
- namespace my_std{
- using namespace std;
- #define pii pair<int,int>
- #define fir first
- #define sec second
- #define MP make_pair
- #define rep(i,x,y) for (int i=(x);i<=(y);i++)
- #define drep(i,x,y) for (int i=(x);i>=(y);i--)
- #define go(x) for (int i=head[x];i;i=edge[i].nxt)
- #define sz 400404
- typedef long long ll;
- const ll mod=998244353;
- template<typename T>
- inline void read(T& t)
- {
- t=0;char f=0,ch=getchar();
- double d=0.1;
- while(ch>'9'||ch<'0') f|=(ch=='-'),ch=getchar();
- while(ch<='9'&&ch>='0') t=t*10+ch-48,ch=getchar();
- if(ch=='.')
- {
- ch=getchar();
- while(ch<='9'&&ch>='0') t+=d*(ch^48),d*=0.1,ch=getchar();
- }
- t=(f?-t:t);
- }
- template<typename T,typename... Args>
- inline void read(T& t,Args&... args){read(t); read(args...);}
- void file()
- {
- #ifndef ONLINE_JUDGE
- freopen("a.txt","r",stdin);
- #endif
- }
- // inline ll mul(ll a,ll b){ll d=(ll)(a*(double)b/mod+0.5);ll ret=a*b-d*mod;if (ret<0) ret+=mod;return ret;}
- }
- using namespace my_std;
- inline ll ksm(ll x,int y)
- {
- ll ret=1;
- for (;y;y>>=1,x=x*x%mod) if (y&1) ret=ret*x%mod;
- return ret;
- }
- ll inv(ll x){return ksm(x,mod-2);}
- int r[sz],limit;
- void NTT_init(int n)
- {
- limit=1;int l=-1;
- while (limit<=n+n) limit<<=1,++l;
- rep(i,0,limit-1) r[i]=(r[i>>1]>>1)|((i&1)<<l);
- }
- void NTT(ll *a,int type)
- {
- rep(i,0,limit-1) if (i<r[i]) swap(a[i],a[r[i]]);
- for (int mid=1;mid<limit;mid<<=1)
- {
- ll Wn=ksm(3,(mod-1)/mid>>1);if (type==-1) Wn=inv(Wn);
- for (int len=mid<<1,j=0;j<limit;j+=len)
- {
- ll w=1;
- for (int k=0;k<mid;k++,w=w*Wn%mod)
- {
- ll x=a[j+k],y=w*a[j+k+mid]%mod;
- a[j+k]=(x+y)%mod;a[j+k+mid]=(mod+x-y)%mod;
- }
- }
- }
- if (type==1) return;
- ll I=inv(limit);
- rep(i,0,limit-1) a[i]=a[i]*I%mod;
- }
- ll tmp1[sz],tmp2[sz];
- void PolyInv(ll *a,ll *f,int n)
- {
- if (n==1) return (void)(f[0]=inv(a[0]));
- int mid=(n+1)>>1;
- PolyInv(a,f,mid);
- NTT_init(n);
- rep(i,0,mid-1) tmp1[i]=f[i];
- rep(i,0,n-1) tmp2[i]=a[i];
- NTT(tmp1,1);NTT(tmp2,1);
- rep(i,0,limit-1) tmp1[i]=tmp1[i]*(mod+2-tmp1[i]*tmp2[i]%mod)%mod;
- NTT(tmp1,-1);
- rep(i,0,n-1) f[i]=tmp1[i];
- rep(i,0,limit-1) tmp1[i]=tmp2[i]=0;
- }
- ll fac[sz],_fac[sz];
- void init(){fac[0]=_fac[0]=1;rep(i,1,sz-1) _fac[i]=inv(fac[i]=fac[i-1]*i%mod);}
- ll f[sz],g[sz],s[sz];
- ll t1[sz],t2[sz],t3[sz],t4[sz];
- int main()
- {
- file();
- init();
- int n=1e5+5,T;
- rep(i,1,n) s[i]=mod-_fac[i];
- ++s[0];
- PolyInv(s,t1,n);
- rep(i,1,n) f[i]=t1[i];f[0]=1;
- rep(i,0,n) t2[i]=t3[i]=f[i];--t3[0];
- NTT_init(n);
- NTT(t2,1);NTT(t3,1);
- rep(i,0,limit-1) t4[i]=t2[i]*t3[i]%mod;
- NTT(t4,-1);
- rep(i,1,n) g[i]=t4[i];
- read(T);
- while (T--) read(n),printf("%lld\n",g[n]*inv(f[n])%mod);
- }
来源: http://www.bubuko.com/infodetail-2945244.html