题解 P3298 【[SDOI2013]泉】

· · 题解

怎么题解都是用哈希的啊，怎么容斥都看不懂啊

我们设f[i]为至少有i个泉区的水流指数对应相同

再设g[i]为恰好有i个泉区的水流指数对应相同（也就是答案数组）

f[i]可以直接暴力选中i个位置，把那些位置上的泉水指数单独拿出来，排个序（懒得写哈希）然后就能直接求了

想想怎么求g[i]

对于i<j发现其实g[j]在f[i]里面算了C(j,i)遍

那么我们就能得到f[i],g[i]的关系

g[i]=f[i]-\sum\limits_{j=i+1}^{6}g[j]*C_j^i

直接按这个式子dp就行了

数组记得稍微开大点，不然就是91分

复杂度O(2^6n \log n)=O(n\log n)

#include<cstdio>
#include<cstring>
#include<ctime>
#include<cstdlib>
#include<algorithm>

#define rg register
#define il inline
#define MX (100000 + 500)
#define ll long long

il int read(){
    rg char k = getchar();
    while(k < '0' || k > '9')   k = getchar();
    int x = 0;
    while(k >= '0' && k <= '9'){
        x = x * 10 + k - '0';
        k = getchar();
    }
    return x;
}

ll C(int n ,int m){
    if(n < m)   return 0;
    ll s1 = 1 ,s2 = 1;
    for(rg int i = 0 ; i < m ; ++i)
        s1 *= (ll)n - i ,s2 *= (ll)i + 1;
    return s1 / s2;
}

int tot;
struct data{
    int a[6];
    il bool operator <(const data b)const{
        for(rg int i = 0 ; i < tot ; ++i)
            if(a[i] != b.a[i])  return a[i] < b.a[i];
        return false;
    }
    il bool operator ==(const data b)const{
        for(rg int i = 0 ; i < tot ; ++i)
            if(a[i] != b.a[i])  return false;
        return true;
    }
}org[MX] ,tmp[MX];

ll ans[7];
int use[MX] ,n ,k;
void solve(){
    for(rg int i = 0 ; i < n ; ++i)
        for(rg int j = 0 ; j < tot ; ++j)
            tmp[i].a[j] = org[i].a[use[j]];
    std::sort(tmp ,tmp + n);
    ll _ans = 0 ,tmpsum = 1;
    //tmpsum表示当前有几个连续相同的
    for(rg int i = 1 ; i < n ; ++i){
        if(tmp[i] == tmp[i - 1])    ++tmpsum;
        else _ans += tmpsum * (tmpsum - 1) / 2 ,tmpsum = 1;
    }
    _ans += tmpsum * (tmpsum - 1) / 2;
    ans[tot] += _ans;
}
void dfs(int now ,int num){
    if(now == 6){
        if(tot == num)
            solve();
        return ;
    }
    use[tot++] = now;
    dfs(now + 1 ,num);
    --tot;
    dfs(now + 1 ,num);
}

int main(){
    scanf("%d%d" ,&n ,&k);
    for(rg int i = 0 ; i < n ; ++i)
        for(rg int j = 0 ; j < 6 ; ++j)
            org[i].a[j] = read();

    for(rg int i = 6 ; i >= k ; --i){
        dfs(0 ,i);
        for(rg int j = i + 1 ; j <= 6 ; ++j){
            ans[i] -= ans[j] * C(j ,i);
        }
    }
    printf("%lld\n" ,ans[k]);
    return 0;
}