ZOJ 3874 Permutation Graph (分治NTT优化DP)

题面：vjudge传送门 ZOJ传送门

题目大意：给你一个排列，如果两个数构成了逆序对，就在他们之间连一条无向边，这样很多数会构成一个联通块。现在给出联通块内点的编号，求所有可能的排列数

推来推去容易发现性质，同一联通块内的点一定是连续标号的，否则无解

然后我就不会了

好神的$NTT$优化$DP$啊

根据上面的性质，联通块之间是互不影响的，所以我们对每个联通块分别统计答案再相乘

定义$f[i]$表示$i$个点构成的合法联通块，可能的排列数

一个合法联通块的所有元素一定在同一联通块内，说明不可能存在两个联通块，因此

$f[i]=i!-\sum f[j]*(i-j)!$

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

模数是一个原根是10的费马素数

别忘了判断无解的情况

 #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],invwn[N1],mulwn[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<<=) mulwn[i]=qpow(,(p-)/i), invwn[i]=qpow(mulwn[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>)?mulwn[k]:invwn[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]; int de;

 void CDQ(int l,int r)

 {

     if(r-l<) return;

     if(r-l==){ f[l]=(g[l]+p-f[l])%p; 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,mi,ma; ll ans;

     scanf("%d",&T); n=;

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

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

     NTT::Pre(len,L);

     CDQ(,n);

     while(T--){

     n=gint(); m=gint(); ans=;

     for(i=;i<=m;i++)

     {

         x=gint(); mi=inf,ma=;

         for(j=;j<=x;j++) que[j]=gint(), mi=min(mi,que[j]), ma=max(ma,que[j]);

         if(ma-mi+!=x) ans=;

         ans=(ans*f[x])%p;

     }

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

     }

     return ;

 }

巴特西

ZOJ 3874 Permutation Graph (分治NTT优化DP)

最新文章

热门文章