BZOJ-2804 [Ctsc2012]showhand
以前被学长说非常丧的题...
然而其实事实不是这样...只需要对一副牌,算出它的牌型、点数和花色就好了。
接下来重载一个小于号,sort一下
再接下来容斥。由于对于A的每一副牌,它对答案的贡献是B手中<A这幅牌的牌数,并且两者没有公共牌。
后一个用容斥原理,假设有三张牌为 $a,b,c$,那么贡献为
$tot-cnt_a-cnt_b-cnt_c+cnt_{a,b}+cnt_{a,c}+cnt_{b,c}-cnt_{a,b,c}$
可以发现状态数是$2^5$,如果强行对于每副牌hash,最大的hash值为4e ($52^5$)
然而事实上A与B不可能取到两幅相同的牌,于是可以把31去掉变成30。这样的话最大的hash值为 $52^4$,就不用开hash表了。
/************************************************************** Problem: 2804 User: wjy1998 Language: C++ Result: Accepted Time:19552 ms Memory:121128 kb ****************************************************************/ #include<cstdio> #include<cstring> #include<algorithm> #include<functional> typedef long long ll; int Y[5][2],Z[5][2],tot,n,now,vis[15][4],f[7400000];ll ansx,ansy,g; struct P{int a[5],kind,x,y,c;}p[2600000]; bool operator<(const P&a,const P&b){ if(a.kind!=b.kind)return a.kind<b.kind; return a.x!=b.x?a.x<b.x:a.y<b.y; } template<class T>void init_P(T&t){ tot++; for(int i=0;i<5;i++)p[tot].a[i]=t[i][0]*4+t[i][1]; std::sort(p[tot].a,p[tot].a+5,std::greater<int>()); static int a[5],b[5],cnt_a[15],cnt_b[4]; int max_a=0,min_a=13,max_b=0,max_t=0,tot_a=0,tot_b=0,kind=0,x=0,y=0; for(int i=0;i<5;i++){ a[i]=p[tot].a[i]/4,b[i]=p[tot].a[i]&3; if(!cnt_a[a[i]]++)tot_a++; if(!cnt_b[b[i]]++)tot_b++; if(a[i]>max_a)max_a=a[i]; if(a[i]<min_a)min_a=a[i]; if(cnt_b[b[i]]>max_b)max_b=cnt_b[b[i]]; if(cnt_a[a[i]]>max_t)max_t=cnt_a[a[i]]; } if(tot_a==5&&tot_b==1){ if(a[0]==12&&a[1]==3&&a[2]==2&&a[3]==1&&a[4]==0)kind=8,x=-1,y=b[1]; else if(max_a-min_a==4)kind=8,y=b[0]; if(kind==8&&x!=-1)for(int i=0;i<5;i++)x|=1<<a[i]; } if(!kind&&tot_a==2&&max_t==4){ kind=7; for(int i=0;i<5;i++)if(cnt_a[a[i]]==4)x|=1<<a[i],y|=1<<b[i]; } if(!kind&&tot_a==2&&max_t==3){ kind=6; for(int i=0;i<5;i++)if(cnt_a[a[i]]==3)x|=1<<a[i],y|=1<<b[i]; } if(!kind&&tot_b==1){ kind=5;y=b[0]; for(int i=0;i<5;i++)x|=1<<a[i]; } if(!kind&&tot_a==5){ if(a[0]==12&&a[1]==3&&a[2]==2&&a[3]==1&&a[4]==0)kind=4,x=-1,y=b[1]; else if(max_a-min_a==4)kind=4,y=b[0]; if(kind==4&&x!=-1)for(int i=0;i<5;i++)x|=1<<a[i]; } if(!kind&&tot_a==3&&max_t==3){ kind=3; for(int i=0;i<5;i++)if(cnt_a[a[i]]==3)x|=1<<a[i],y|=1<<b[i]; } if(!kind&&tot_a==3&&max_t==2){ kind=2;int max=0; for(int i=0;i<5;i++)if(cnt_a[a[i]]==2){ x|=1<<a[i]; if(a[i]>max)max=a[i]; } x<<=13; for(int i=0;i<5;i++){ if(cnt_a[a[i]]==1)x|=1<<a[i]; if(a[i]==max)y|=1<<b[i]; } } if(!kind&&tot_a==4&&max_t==2){ kind=1; for(int i=0;i<5;i++)if(cnt_a[a[i]]==2)x|=1<<a[i],y|=1<<b[i]; x<<=13; for(int i=0;i<5;i++)if(cnt_a[a[i]]==1)x|=1<<a[i]; } if(!kind){ for(int i=0;i<5;i++)x|=1<<a[i];y=1<<b[0]; } p[tot].x=x,p[tot].y=y,p[tot].kind=kind;p[tot].c=now; for(int i=0;i<5;i++)cnt_a[a[i]]--,cnt_b[b[i]]--; } template<class T>void dfs(T&t,int x,int a,int b){ if(x==5)init_P(t); else for(int i=a;i<13;i++) for(int j=i==a?b:0;j<4;j++)if(!vis[i][j]){ t[x][0]=i,t[x][1]=j; vis[i][j]=1,dfs(t,x+1,i,j+1),vis[i][j]=0; } } void calc(int id){ for(int s=1,x,y,j;s<=30;y&1?ansx-=f[x]:ansx+=f[x],s++) for(x=y=j=0;j<5;j++)if(s&(1<<j))y++,x=x*52+p[id].a[j]; } void hash(int id){ for(int s=1,x,j;s<=30;f[x]++,s++) for(x=j=0;j<5;j++)if(s&(1<<j))x=x*52+p[id].a[j]; } ll gcd(ll x,ll y){return!y?x:gcd(y,x%y);} ll comb(int n,int k){ ll s=1; for(int i=n,j=1;j<=k;i--,j++)s=s*i/j; return s; } int main(){ scanf("%d",&n); for(int i=0,x,y;i<n;i++){ scanf("%d%d",&x,&y); if(x==1)x=14;y=4-y;x-=2; Y[i][0]=x,Y[i][1]=y,vis[x][y]=1; } for(int i=0,x,y;i<n-1;i++){ scanf("%d%d",&x,&y); if(x==1)x=14;y=4-y;x-=2; Z[i][0]=x,Z[i][1]=y,vis[x][y]=1; } dfs(Y,n,0,0);now=1;dfs(Z,n-1,0,0);std::sort(p+1,p+1+tot); for(int i=1,j=0;i<=tot;i++)if(!p[i].c)ansx+=j,calc(i);else j++,hash(i); ansy=comb(53-2*n,5-n)*comb(48-n,6-n),g=gcd(ansx,ansy),ansx/=g,ansy/=g; if(ansx==0)puts("0/1");else printf("%lld/%lld\n",ansx,ansy); }
2024年1月19日 23:41
Pavzi.com is a startup by passionate webmasters and bloggers who have a passion for providing engaging content that is accurate, interesting, and worthy to read. pavzi.com We are more like a web community where you can find different information, resources, and topics on day-to-day incidents or news. We provide you with the finest web content on every topic possible with the help of the editorial and content team.