首页 > 其他 > 详细

bzoj2012: [Ceoi2010]Pin

时间:2016-07-29 19:03:13      阅读:310      评论:0      收藏:0      [点我收藏+]

Description

给出N(2<=N<=50000)个长度为4的字符串,问有且仅有D(1<=D<=4)处不相同的字符串有几对。

Input

第1行: N,D 以下N行每行一个字符串

Output

一个数:有多少对有且仅有处不相同的字符串。
记录每个字符串出现次数以及带1..4个通配符的字符串出现次数,容斥得到答案
#include<cstdio>
int n,m;
char s[8];
int _t2[128][128][6];
int _t3[128][4];
int t4,ans=0;
#define t3(a,b) _t3[a][b]
#define t2(a,b,c) _t2[a][b][c]
const int P=1844677;
struct Map{
    int xs[P],ys[P];
    int&operator()(int a,int b,int c,int d){
        int x=(((a<<7|b)<<7|c)<<7)|d;
        int w=x%P;
        while(xs[w]){
            if(xs[w]==x)return ys[w];
            w+=123457;
            if(w>=P)w-=P;
        }
        xs[w]=x;
        return ys[w];
    }
}t0,t1;
int main(){
    scanf("%d%d",&n,&m);
    for(t4=0;t4<n;t4++){
        scanf("%s",s);
        int a=s[0],b=s[1],c=s[2],d=s[3];
        if(!a||!b||!c||!d)printf("%d",a/=0);
        if(m==1){
            ans+=
            -t0(a,b,c,d)++*4
            +t1(a,b,c,0)++
            +t1(a,b,d,1)++
            +t1(a,c,d,2)++
            +t1(b,c,d,3)++;
        }else if(m==2){
            int aa1,aa2,aa3;
            ans+=
            +(aa1=t0(a,b,c,d)++)*6
            -(aa2=t1(a,b,c,0)++
            +t1(a,b,d,1)++
            +t1(a,c,d,2)++
            +t1(b,c,d,3)++)*3
            +(aa3=t2(a,b,0)++
            +t2(a,c,1)++
            +t2(a,d,2)++
            +t2(b,c,3)++
            +t2(b,d,4)++
            +t2(c,d,5)++);
        }else if(m==3){
            ans+=
            -t0(a,b,c,d)++*4
            +(t1(a,b,c,0)++
            +t1(a,b,d,1)++
            +t1(a,c,d,2)++
            +t1(b,c,d,3)++)*3
            -(t2(a,b,0)++
            +t2(a,c,1)++
            +t2(a,d,2)++
            +t2(b,c,3)++
            +t2(b,d,4)++
            +t2(c,d,5)++)*2
            +t3(a,0)++
            +t3(b,1)++
            +t3(c,2)++
            +t3(d,3)++;
        }else{
            ans+=
            t0(a,b,c,d)++
            -(t1(a,b,c,0)++
            +t1(a,b,d,1)++
            +t1(a,c,d,2)++
            +t1(b,c,d,3)++)
            +(t2(a,b,0)++
            +t2(a,c,1)++
            +t2(a,d,2)++
            +t2(b,c,3)++
            +t2(b,d,4)++
            +t2(c,d,5)++)
            -(t3(a,0)++
            +t3(b,1)++
            +t3(c,2)++
            +t3(d,3)++)
            +t4;
        }
    }
    printf("%d\n",ans);
    return 0;
}

 

bzoj2012: [Ceoi2010]Pin

原文:http://www.cnblogs.com/ccz181078/p/5719371.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!