HZOJ Silhouette

转化一下题意：给出矩阵每行每列的最大值，求满足条件的矩阵个数。

先将A，B按从大到小排序，显然没有什么影响。如果A的最大值不等于B的最大值那么无解否则一定有解。

考虑从大到小枚举A，B中出现的数s，那么可以将这个矩形分成一些不同的矩形或者L形使之互不影响，且位置的值在[0,s]中,且每行每列的最大值均为s，最后用分步乘法计数原理求解。

例：

5

1 2 2 3 5

2 2 3 4 5

由于矩形是特殊的L形于是我们只考虑L形：

设拐点的矩形为a*b，L上部高为c，左部长为d。

考虑容斥，设f[i]为至少有i行的限制不满足条件（每列都要满足条件），

那么$f[i]=C_a^i * ( s^i * ( (s+1)^{a+c-i} - s^{a+c-i} ))^b * (s^i * (s+1)^{a-i} )^d$

$s^i$保证i行不满足限制，$((s+1)^{a+c-i}-s^{a+c-i})$表示剩下的至少一个满足限制条件（为保证列满足），b次方即每列。这样就考虑完了前b列。

那么多出来的d列呢？大致相同。$(s^i*(s+1)^{a-i})^d$可以发现并没有保证列满足，因为L型左部上面一定比这里大，那么已经保证列满足限制，所以这里就随便选了。

$ans=\prod \sum _{i=0}^{a} -1^i*f[i]$

 #include<algorithm>

 #include<iostream>

 #include<cstring>

 #include<cstdio>

 #define LL long long

 using namespace std;

 const int mod=1e9+;

 struct Hash_map

 {

     int fi[],ni[],siz;

     int key[],val[];

     inline int &operator [] (int x)

     {

         int k=x%;int i=fi[k];

         for(;i&&key[i]!=x;i=ni[i]);

         if(!i)i=++siz,key[i]=x,val[i]=,ni[i]=fi[k],fi[k]=i;

         return val[i];

     }

 }ta,tb;

 LL poww(LL a,LL b);

 LL jc[],inv[];

 LL CC(LL n,LL m){return jc[n]*inv[m]%mod*inv[n-m]%mod;}

 int n,A[],B[],C[],cnt;

 bool cmp(int a,int b){return a>b;}

 LL f[];

 signed main()

 {

 //    freopen("silhouette4.in","r",stdin);

     jc[]=inv[]=;for(int i=;i<=;i++)jc[i]=jc[i-]*i%mod,inv[i]=poww(jc[i],mod-);

     cin>>n;

     for(int i=;i<=n;i++)cin>>A[i],C[++cnt]=A[i],ta[A[i]]++;

     for(int i=;i<=n;i++)cin>>B[i],C[++cnt]=B[i],tb[B[i]]++;

     sort(A+,A+n+,cmp);sort(B+,B+n+,cmp);

     if(A[]!=B[]){puts("");return ;}

     sort(C+,C+cnt+,cmp);cnt=unique(C+,C+cnt+)-C-;

     LL ans=;

     int la=,lb=,na=,nb=;

     for(int i=;i<=cnt;i++)

     {

         int s=C[i];

         la=na,lb=nb;

         while(na<n&&A[na+]==s)na++;

         while(nb<n&&B[nb+]==s)nb++;

         int a=na-la,b=nb-lb,c=la,d=lb;

         LL tem=;

         for(int j=;j<=a;j++)

         {

             f[j]=CC(a,j)*poww( ( poww(s,j) * (poww(s+,a+c-j)-poww(s,a+c-j)%mod) )%mod ,b)%mod*

                  poww( poww(s,j)*poww(s+,a-j)%mod ,d)%mod;

             if(j&)tem-=f[j];else tem+=f[j];

             tem=(tem%mod+mod)%mod;

         }

         ans=(ans*tem)%mod;

     }

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

 }

 LL poww(LL a,LL b)

 {

     a%=mod;LL ans=;

     while(b)

     {

         if(b&)ans=ans*a%mod;

         a=a*a%mod;b=b>>;

     }

     return ans;

 }

巴特西

HZOJ Silhouette

最新文章

热门文章