Description
.jpg)
Input
.jpg)
Output
Sample Input
3 3
1 2 3 4 5 6
1 2 3 0 0 0
0 0 0 4 5 6
1 2 3 4 5 6
1 2 3 0 0 0
0 0 0 4 5 6
Sample Output
2
HINT
Dragonite修正数据
Source
Hash
Solution
若求的是相同个数的正好为k的
但是有一对相同个数是k+p
那么在f[i]单次统计时会被统计$C_{k+p}^{i}$次$(k<=i<=k+p)$
那么对于最终答案f[i]多统计了$C_{i}^{k}$次
所以一对相同个数为k+p的就多统计了$\sum_{i=k}^{k+p}C_i^k*C_{k+p}^{i}$次
但这些都是不合法的
运用容斥原理可以得到最终这对相同个数为k+p的统计了$\sum_{i=k}^{k+p}C_i^k*C_{k+p}^{i}*(-1)^{i-k}$
发现当k+p=k时即p=0时 这个式子值为1，否则为0。
这便符合我们的要求。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 |
#include<iostream> #include<cstdio> #include<algorithm> #include<cmath> #include<cstring> #define M 2333 #define mo 1000003 #define ll long long using namespace std; const int N=100010; int n,k,a[N][7],C[7][7],tot,cnt,Next[N],head[mo],tree[N],num[N],p[mo]; ll f[7]; int Count(int x) { int ans=0; for (;x;x=x&(x-1)) ans++; return ans; } bool calc_same(int x,int y,int sta) { for (int i=1;i<=6;i++) if ((sta&(1<<(i-1)))&&a[x][i]!=a[y][i]) return 0; return 1; } void add(int x,int y) { tot++; Next[tot]=head[x]; head[x]=tot; tree[tot]=y; num[tot]=1; } int Insert(int x,int now,int sta) { if (p[x]!=cnt) { p[x]=cnt;head[x]=0;} for (int i=head[x];i;i=Next[i]) if (calc_same(tree[i],now,sta)) { num[i]++;return num[i]-1;} add(x,now); return 0; } ll calc(int sta) { cnt++;tot=0; ll ans=0; for (int i=1;i<=n;i++) { ll sum=0; for (int j=1;j<=6;j++) if (sta&(1<<(j-1))) (sum=sum*M%mo+a[i][j])%=mo; ans+=Insert(sum,i,sta); } return ans; } int main() { scanf("%d%d",&n,&k); for (int i=1;i<=n;i++) for (int j=1;j<=6;j++) scanf("%d",&a[i][j]); C[0][0]=1; for (int i=1;i<=6;i++) { C[i][0]=1; for (int j=1;j<=i;j++) C[i][j]=C[i-1][j]+C[i-1][j-1]; } calc(7); for (int i=0;i<=(1<<6)-1;i++) f[Count(i)]+=calc(i); ll ans=0; for (int i=k;i<=6;i++) ans+=(ll)(((i-k)&1)?-1:1)*C[i][k]*f[i]; printf("%lld\n",ans); return 0; } |
