[Sdoi2013]spring

题目

INPUT

OUTPUT

SAMPLE

INPUT

3 3

1 2 3 4 5 6

1 2 3 0 0 0

0 0 0 4 5 6

OUTPUT

2

解题报告

$hash$加容斥

我们一看到恰有$K$个相等，很容易就能想到容斥原理，所以，我们需要枚举每种对应相等的情况，也就是枚举$2^{6}$种对应相等的情况，然后$C_{num}^{2}$求出总对数

问题在于如何处理对应相等的情况，$O(n^{2})$的暴力是很容易想出来的，然而在并没有的数据范围中，$n$是$10^{5}$级别的，意味着$O(n^{2})$的暴力可以说再见了，那么我们就很容易想到$hash$，用对应相等的$hash$值来判断对应位置的相等，就可以做到$O(n)$判等了

接着就是最重要的一部分了：容斥原理

我们考虑，我们只取出了$a$位对应位来判断是否相等，但是显然$a+1$位对应相等的一对城市也会被包含进去，所以我们要应用容斥原理，从$k$个对应相等开始枚举$k+1$位对应相等，直到$n$个对应相等，奇偶性与$k$相同的加上，不同的减去

（不懂原理的自行百度容斥原理）

重要的是，我们不能简单的加减总对数，我们考虑，从$k+a$位对应相等的一对城市中取出$k$位对应相等，共有$C_{k+a}^{k}$种取法，（因为我们是按位取，按位比较的），所以我们还要对应的乘上他们的组合数

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 #include 
          
            6 using namespace std; 7 #define mod 1000007 8 #define P 2333333333333LL 9 int read() {10     int s=0,f=1;11     char ch=getchar();12     for( ; ch<'0'||ch>'9'; f=(ch=='-')?(-1):(f),ch=getchar()) ;13     for( ; ch>='0'&&ch<='9'; s=(s<<1)+(s<<3)+(ch^48),ch=getchar()) ;14     return s*f;15 }16 int n,k,sta[7],top,f[100005][7],fac[7],C[7][7];17 unsigned long long num[1000010],inv[1000010],tmp,biao[100005];18 void clear() {19     top=tmp=0;20     memset(biao,0,sizeof(biao));21     memset(num,0,sizeof(num));22     memset(inv,0,sizeof(inv));23 }24 void init() {25  26     fac[0]=fac[1]=1;27     for(int i=2; i<=6; ++i) {28         fac[i]=fac[i-1]*i;29     }30     for(int i=0; i<=6; ++i) {31         for(int j=0; j<=i; ++j) {32             C[i][j]=fac[i]/(fac[j]*fac[i-j]);33         }34     }35 }36 void get(int x) {37     clear();38     for(int i=1; i<=6; ++i) {39         if((1<<(i-1))&x) {40             sta[++top]=i;41         }42     }43     for(int i=1; i<=n; ++i) {44         for(int j=1; j<=top; ++j) {45             biao[i]=biao[i]*P+f[i][sta[j]];46         }47     }48     for(int i=1; i<=n; ++i) {49         int ss=biao[i]%mod;50         while(inv[ss]!=biao[i]) {51             if(!num[ss]) {52                 break;53             }54             ++ss;55         }56         inv[ss]=biao[i];57         tmp+=num[ss];58         ++num[ss];59     }60 }61 int main() {62     n=read(),k=read();63     for(int i=1; i<=n; ++i) {64         for(int j=1; j<=6; ++j) {65             f[i][j]=read();66         }67     }68     init();69     long long ans=0;70     for(int i=0; i<(1<<6); ++i) {71         get(i);72         if(top>=k) {73             if((top-k)&1) {74                 ans-=tmp*C[top][k];75             }76             if(!((top-k)&1)) {77                 ans+=tmp*C[top][k];78             }79         }80     }81     cout<
          
         
        
       
      

好久不写题解，都快不会写了= =