题解洛谷 P3298 【[SDOI2013]泉】

考虑到年份数很小，只有 \(6\)，所以可以 \(2^6\) 来枚举子集，确定流量指数对应相同的位置，然后通过哈希和排序来计算相同的方案数。

但是这样计算出的是大于等于子集元素个数的方案数，所以还需要通过容斥来得到恰好为 \(k\) 的方案数。设子集元素个数为 \(num\)，其容斥系数为 \((-1)^{num-k}\binom{num}{k}\)，还需乘上组合数的原因是相同个数恰好为 \(num\) 的方案数对相同个数大于等于 \(k\) 的方案数的贡献为 \(\binom{num}{k}\)。

为了防止被卡，我这里用了双哈希来实现。

\(code:\)

#include<bits/stdc++.h>

#define maxn 100010

#define p1 998244353

#define p2 1000000007

#define b1 131

#define b2 137

using namespace std;

typedef long long ll;

template<typename T> inline void read(T &x)

{

    x=0;char c=getchar();bool flag=false;

    while(!isdigit(c)){if(c=='-')flag=true;c=getchar();}

    while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}

    if(flag)x=-x;

}

ll n,k,ans;

ll a[maxn][10],C[10][10];

bool tag[6];

struct node

{

    ll h1,h2;

}t[maxn];

bool cmp(const node &a,const node &b)

{

    if(a.h1==b.h1) return a.h2<b.h2;

    return a.h1<b.h1;

}

void init()

{

    for(int i=0;i<=6;++i) C[i][0]=1;

    for(int i=1;i<=6;++i)

        for(int j=1;j<=i;++j)

            C[i][j]=C[i-1][j]+C[i-1][j-1];

}

ll calc(int s)

{

    for(int i=1;i<=n;++i) t[i].h1=t[i].h2=0;

    for(int i=1;i<=n;++i)

    {

        for(int j=1;j<=6;++j)

        {

            t[i].h1=(t[i].h1*b1%p1+a[i][j]*tag[j])%p1;

            t[i].h2=(t[i].h2*b2%p2+a[i][j]*tag[j])%p2;

        }

    }

    sort(t+1,t+n+1,cmp);

    ll cnt=0,sum=0;

    for(int i=2;i<=n;++i)

    {

        if(t[i].h1==t[i-1].h1&&t[i].h2==t[i-1].h2) cnt++,sum+=cnt;

        else cnt=0;

    }

    return sum;

}

int main()

{

    read(n),read(k),init();

    for(int i=1;i<=n;++i)

        for(int j=1;j<=6;++j)

            read(a[i][j]);

    for(int s=0;s<=63;++s)

    {

        int num=0;

        for(int i=1;i<=6;++i)

        {

            if(s&(1<<(i-1))) num++,tag[i]=true;

            else tag[i]=false;

        }

        if(num<k) continue;

        ll val=calc(s)*C[num][k];

        if((num-k)&1) ans-=val;

        else ans+=val;

    }

    printf("%lld",ans);

    return 0;

}

巴特西

题解洛谷 P3298 【[SDOI2013]泉】

最新文章

热门文章

巴特西

题解 洛谷 P3298 【[SDOI2013]泉】

最新文章

热门文章

题解洛谷 P3298 【[SDOI2013]泉】