HDU 5322 Hope (分治NTT优化DP)

题面传送门

题目大意：

假设现在有一个排列，每个数和在它右面第一个比它大的数连一条无向边，会形成很多联通块。

定义一个联通块的权值为：联通块内元素数量的平方。

定义一个排列的权值为：每个联通块的权值之积

求长度为$n$所有排列的权值之和，$n\leq 1e5$，$1e4$组询问

原题面描述不清楚啊..害得我白想了30min

和ZOJ3874一样都是排列$DP$问题

$DP$方程还是不难想的

假设现在有一个$i-1$的排列，当我们把$i$某个位置上时

$i$前面的数都会和$i$连通，$i$后面的数一定不和$i$前面的数连通

利用这个性质就可以$DP$了，定义$f[i]$表示长度为$i$的所有排列的权值之和

$f[i]$

$i$后面一共j个数可以在$i-1$个数中任选，$i$前面一共$i-j-1$个数可以任意排列，可得

$=\sum C_{i-1}^{j}f[j](i-j-1)!(i-j)^{2}$

化简

$=(i-1)!\sum \frac{f[j]}{j!}(i-j)^{2}$

发现这是一个卷积的形式，用分治$NTT$解决即可

 #include <cmath>

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 #define N1 (1<<18)+10

 #define il inline

 #define dd double

 #define ld long double

 #define ll long long

 using namespace std;

 const int inf=0x3f3f3f3f;

 const ll p=;

 int gint()

 {

     int ret=,fh=;char c=getchar();

     while(c<''||c>''){if(c=='-')fh=-;c=getchar();}

     while(c>=''&&c<=''){ret=ret*+c-'';c=getchar();}

     return ret*fh;

 }

 ll qpow(ll x,ll y)

 {

     ll ans=;

     for(;y;x=x*x%p,y>>=) if(y&) ans=ans*x%p;

     return ans;

 }

 namespace NTT{

 ll a[N1],b[N1],c[N1],Wn[N1],_Wn[N1];

 int r[][N1];

 void Pre(int len,int L)

 {

     int i,j;

     for(j=;j<=L;j++) for(i=;i<(<<j);i++)

         r[j][i]=(r[j][i>>]>>)|((i&)<<(j-));

     for(i=;i<=len;i<<=) Wn[i]=qpow(,(p-)/i), _Wn[i]=qpow(Wn[i],p-);

 }

 void NTT(ll *s,int len,int type,int L)

 {

     int i,j,k; ll wn,w,t;

     for(i=;i<len;i++) if(i<r[L][i]) swap(s[i],s[r[L][i]]);

     for(k=;k<=len;k<<=)

     {

         wn=(type>)?Wn[k]:_Wn[k];

         for(i=;i<len;i+=k)

         {

             for(j=,w=;j<(k>>);j++,w=w*wn%p)

             {

                 t=w*s[i+j+(k>>)]%p;

                 s[i+j+(k>>)]=(s[i+j]+p-t)%p;

                 s[i+j]=(s[i+j]+t)%p;

             }

         }

     }

 }

 void Main(int len,int L)

 {

     int i,invl=qpow(len,p-);

     NTT(a,len,,L); NTT(b,len,,L);

     for(i=;i<len;i++) c[i]=a[i]*b[i]%p;

     NTT(c,len,-,L);

     for(i=;i<len;i++) c[i]=c[i]*invl%p;

 }

 void clr(int sz)

 {

     memset(a,,sz<<);

     memset(b,,sz<<);

 }

 };

 using NTT::a; using NTT::b; using NTT::c;

 ll f[N1],g[N1],ans[N1],mul[N1],_mul[N1]; int de;

 void CDQ(int l,int r)

 {

     if(r-l==&&l>)

     {

         ans[l]=mul[l-]*f[l]%p;

         f[l]=ans[l]*_mul[l]%p; return;

     }

     if(r-l<=) return;

     int mid=(l+r)>>,i,len,L;

     CDQ(l,mid);

     for(len=,L=;len<(mid-l)+(r-l)-;len<<=,L++);

     for(i=l;i<mid;i++) NTT::a[i-l]=f[i];

     for(i=;i<(r-l);i++) NTT::b[i]=g[i];

     NTT::Main(len,L);

     for(i=mid;i<r;i++) f[i]=(f[i]+NTT::c[i-l])%p;

     NTT::clr(len);

     CDQ(mid,r);

 }

 int T,n,m;

 int que[N1];

 int main()

 {

     int i,j,x,y,len,L;

     n=;

     for(i=;i<n;i++) g[i]=1ll*i*i%p;

     mul[]=mul[]=_mul[]=_mul[]=;

     for(i=;i<n;i++) mul[i]=mul[i-]*i%p, _mul[i]=qpow(mul[i],p-);

     for(len=,L=;len<n+n-;len<<=,L++);

     NTT::Pre(len,L);

     f[]=; CDQ(,n);

     while(scanf("%d",&n)!=EOF)

         printf("%lld\n",ans[n]);

     return ;

 }

巴特西

HDU 5322 Hope (分治NTT优化DP)

最新文章

热门文章