BZOJ 3198 Spring

发表于 | 更新于

Link

Solution

两行对应相等的情况总共有262^6种，那就枚举这6464种情况，用Hash统计。 每次边查询边插入。 要求恰好为KK，用容斥。注意到公共序列长度为LL一对序列对答案的贡献是CLKC_L^K，所以容斥的时候要乘上CLKC_L^K。 对数组的Hash可以仿照字符串Hash，而因为这道题是枚举出6464种情况的，所以不需要考虑没有被选中的位，可以直接跳过去。即序列10,10,10,10,10,1010,10,10,10,10,10的两个状态000011000011和001100001100算出来的Hash值可以是相等的，不会有影响的。这样可以让Hash值存储更多有用信息。

Tips

暴力枚举，一次答案只会增加1，所以复杂度肯定不会比答案更优。--lct1999

而暴力的优化策略常常把信息分类地存在数据结构里，让答案每次增加一类的总数。(我太弱了这么显然的东西还要记下来。。)

Code

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
72
73
74
75
76
77
78
79
80
81
82
83
84
85
//Code by Lucida
#include<bits/stdc++.h>
#define get(x) scanf("%d",&x)
//#define debug(x) std::cout<<#x<<'='<<x<<std::endl
template <class T> inline bool chkmx(T &a,const T &b){return a<b?a=b,1:0;}
template <class T> inline bool chkmn(T &a,const T &b){return a>b?a=b,1:0;}
const int MAXN=1e5+10;
using std::sort;
using std::unique;
using std::lower_bound;
typedef long long LL;
typedef unsigned long long UL;
namespace iHash
{
	const int SIZE=MAXN*64;
	const int P=1e5+7;
	struct Node
	{
		UL key;int val;Node *pre;
		Node(UL key,int val,Node* pre):key(key),val(val),pre(pre){}
	}*POOL=(Node*)malloc(SIZE*sizeof(Node)),*ME=POOL;
	//struct Hash{
	Node *id[P];
	void Insert(UL key)
	{
		int h=key%P;
		for(Node *ptr=id[h];ptr;ptr=ptr->pre)
			if(ptr->key==key) {ptr->val++;return;}
		id[h]=new(ME++) Node(key,1,id[h]);
	}
	int Count(UL key)
	{
		int h=key%P;
		for(Node *ptr=id[h];ptr;ptr=ptr->pre)
			if(ptr->key==key) {return ptr->val;}
		return 0;
	}
	void Clear(){memset(id,0,sizeof(id));ME=POOL;}
	//}H;
}using namespace iHash;
const int BASE=1e9+7;
UL ArrayHash(int *a,int S)
{
	UL res=0;
	for(int i=0;i<=5;i++)
		if(S&(1<<i)) //(res*=(UL)a[i]*primes[i];
			(res*=BASE)+=a[i];
	return res;
}
int main()
{
	static int lis[MAXN*6],lc,a[MAXN][6],C[10][10];
	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-1]+C[i-1][j];
	}
	int n,K;get(n),get(K);
	for(int i=1;i<=n;i++)
		for(int j=0;j<=5;j++)
			get(a[i][j]),lis[++lc]=a[i][j];
	sort(lis+1,lis+1+lc);lc=unique(lis+1,lis+1+lc)-lis-1;
	for(int i=1;i<=n;i++)
		for(int j=0;j<=5;j++)
			a[i][j]=lower_bound(lis+1,lis+1+lc,a[i][j])-lis;
	LL ANS=0;
	for(int S=0;S<=63;++S)
	{
		int cnt=__builtin_popcount(S);if(cnt<K) continue;
		Clear();
		for(int i=1;i<=n;i++)
		{
			UL code=ArrayHash(a[i],S);
			ANS+=C[cnt][K]*Count(code)*((cnt-K)&1?-1:1);
			Insert(code);
		}
	}
	printf("%lld\n",ANS);
	return 0;
}
/* AC Record(Bugs) *
 * 
 * * * * * * * * * */