| 题目名称 | 1522. [POJ2441]安排公牛 |
|---|---|
| 输入输出 | examnine.in/out |
| 难度等级 | ★★☆ |
| 时间限制 | 4000 ms (4 s) |
| 内存限制 | 64 MiB |
| 测试数据 | 10 |
| 题目来源 |
 cstdio
于2014-02-05加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：34， 提交：89， 通过率：38.2% | ||||
 white |
100 | 0.040 s | 0.32 MiB | C++ |
 CSU_Turkey |
100 | 0.069 s | 8.31 MiB | C++ |
|
CSU_Turkey |
100 | 0.081 s | 8.31 MiB | C++ |
 lky |
100 | 0.099 s | 8.29 MiB | C++ |
 , |
100 | 0.101 s | 8.17 MiB | Pascal |
 农场主 |
100 | 0.101 s | 32.29 MiB | C++ |
 0 |
100 | 0.105 s | 8.31 MiB | C++ |
 Herian |
100 | 0.107 s | 4.32 MiB | C++ |
 xmqwbzr |
100 | 0.121 s | 8.31 MiB | C++ |
 pztl |
100 | 0.125 s | 8.31 MiB | C++ |
| 本题关联比赛 | |||
| 动规 | |||
| 动规 | |||
| exam | |||
| 状态压缩DP | |||
| 状态压缩DP练习 | |||
| 关于 安排公牛 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
标程怕是爆精度了吧。long long过不了的unsigned int就过了？？？？
 胡嘉兴
2017-10-18 19:21
7楼
| ||||
|
出题人是真皮 long long 过不去 uint 就过去了？
 Ostmbh
2017-04-05 09:09
6楼
| ||||
|
| ||||
|
请各位仔细查看该题文件名。。。并不是一个单词
| ||||
|
,
2014-05-16 18:44
3楼
| ||||
|
回复 @Chenyao :
我和小伙伴们都吓傻了……每个牛喜欢的棚都不一样啊这怎么容斥……少侠你可以推一下，没准真能推出来…… | ||||
|
@cstdio 数学神犇这题能不能用容斥做？没google到容斥的解法。。。
 Chenyao2333
2014-02-05 21:25
1楼
| ||||
confoo
digital-T
cstdio【题目描述】
Farmer Johnson的公牛们非常喜欢打篮球。但它们都不愿意一起打篮球，因为所有公牛都认为其他的牛弱爆了。Farmer Johnson有N头牛（我们把它们编号为1~N）和M个牛棚（我们把它们编号为1~M），这些牛棚就是公牛们的篮球场。但FJ的公牛非常挑剔，它们只会在自己喜欢的牛棚打球，并且都不愿意和其他的牛共享牛棚。
因此安排他的公牛对Farmer Johnson来说是一项艰难的任务，他希望得到你的帮助。当然，找到一种方案是容易的，但你的任务是找出一共有多少种方案。
一个方案是一种使得所有公牛都能在它喜欢的牛棚中快乐玩耍，并且没有两只牛共享一个牛棚的安排方式。
答案不会超过32位无符号整数范围。（其实用unsigned int 会溢出，懒得改数据了，直接用unsigned int就好了，别用long long！）
【输入格式】
输入文件的第一行有两个正整数N，M（1<=N,M<=20）。
接下来有N行，第i行的开头有一个正整数P(1<=P<=M)，代表第i头牛喜欢的牛棚数量。接下来有P个正整数，即P个牛棚的编号。
【输出格式】
输出一行一个正整数，即方案总数。
【样例输入】
3 4 2 1 4 2 1 3 2 2 4
【样例输出】
4
【来源】
POJ Monthly,TN
北京大学 POJ 2441