BZOJ 3198: [Sdoi2013]spring [容斥原理 哈希表]
3198: [Sdoi2013]spring
题意:n个物品6个属性,求有多少不同的年份i,j满足有k个属性对应相等
一开始读错题了,注意是对应相等 第i个属性只能和第i个属性对应
容斥一下
\]
\(2^6\)枚举哪些属性对应相等,哈希一下计算这些属性相等的个数,这时候其他是任意的因为是\(\ge\)
这样还不行,容斥系数还要乘上\(\binom{i}{k}\),因为两个k+1个属性对应相等的物品贡献了\(\binom{k+1}{k}\)个k个属性相等
其实就是说,比如\(\ge k\)的时候我们求到的\(\ge k\)个相等的方案数,并不是这样的物品对个数,对于一个\(k+i\)个属性对应相等的物品对我们其实考虑了\(\binom{k+i}{k}\)次,这里本身就出现了重复(不是容斥的原因是我们统计个数的原因),所以要额外消去这个的影响,方法就是乘上那个组合数
我在这里进行了证明
属性值太大很容易冲突所以要用哈希表
然后去学了哈希表...貌似P越小越快啊
```cpp
#include
#include
#include
#include
using namespace std;
typedef long long ll;
const int N=1e5+5, M=23333, P=1001001;//1234567;
inline int read(){
char c=getchar();int x=0,f=1;
while(c'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&cint n, k, a[N][7], c[7][7];
struct HashList{
struct meow{int id, c, ne;} e[N*64];
int cnt, h[P], tim[P], Cl;
inline void ini(){Cl++;}
inline bool same(int x, int y, int s) {
for(int i=1; i<=6; i++)
if(s&(1<<(i-1)) && a[x][i] != a[y][i]) return false;
return true;
}
int hash(int a, int s) {
ll val=0;
for(int j=1; j<=6; j++)
if(s&(1<<(j-1))) val = (valM%P + a[j]%P)%P;
return val;
}
int insert(int id, int s) {
int val=hash(a[id], s); //printf("ins %d %d %d\n",id,s,val);
if(tim[val] != Cl) h[val]=0, tim[val]=Cl;
for(int i=h[val];i;i=e[i].ne)
if(same(e[i].id, id, s)) {e[i].c++; return e[i].c-1;}
e[++cnt]=(meow){id, 1, h[val]}; h[val]=cnt;
return 0;
}
}H;
ll cal(int s) {
H.ini();
ll ans=0;
for(int i=1; i<=n; i++)
ans += H.insert(i, s);
return ans;
}
inline int one(int x) {
int ans=0;
while(x) ans++, x&=x-1;
return ans;
}
ll cnt[7];
int main() {
//freopen("in","r",stdin);
n=read(); k=read();
for(int i=1; i<=n; i++)
for(int j=1; j<=6; j++) a[i][j]=read();
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];
}
int All=1<<6;
for(int s=0; s<All; s++) cnt[one(s)] += cal(s);
ll ans=0;
for(int i=k; i<=6; i++) ans += (( (i-k)&1 ) ? -1 : 1) * c[i][k] * cnt[i];
printf("%lld\n",ans);
}
最新文章
- tagfield
- StartUML反向(逆向)Java工程通过代码生成类图
- 云计算 云服务 hadoop
- Hdu OJ 5965 扫雷(递推)
- [转载]赖勇浩:推荐《Linux 多线程服务器端编程》
- android图片缩小和放大Matrix
- wordpress中如何禁止或者屏蔽更新提示
- Django Web在Apache上的部署
- [Java] 类的初始化步骤
- Myeclipse SVN 修改用户名和密码
- SALM入门笔记(1):特征点的匹配
- [译]Python作为一种编程语言有多强大?
- [51nod1197]字符串的数量 V2
- JavaScript IIEF 模仿块级作用域
- fastAdmin进阶
- 揭开yield关键字的神秘面纱
- P2016 战略游戏
- [UE4]子弹穿透多个机器人
- java调用第三方包的例子
- li设置float后ul无法包裹li问题解决