记录编号 590696 评测结果 AAAAAAAAAA
题目名称 [USACO Nov06] 牧场的安排 最终得分 100
用户昵称 Gravatardream 是否通过 通过
代码语言 C++ 运行时间 0.031 s
提交时间 2024-07-10 17:16:37 内存使用 3.40 MiB
显示代码纯文本
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. const int mod=100000000,N=14;
  4. int m,n;
  5. int cnt;
  6. int a[(1<<N)];
  7. int b[N];
  8. int f[N][(1<<N)];
  9. void it(){
  10. for(int i=0;i<(1<<n);i++){
  11. if(i&(i<<1)){
  12. continue;
  13. }
  14. a[++cnt]=i;
  15. }
  16. }
  17. int main(){
  18. freopen("cowfood.in","r",stdin);
  19. freopen("cowfood.out","w",stdout);
  20. cin>>m>>n;
  21. for(int i=1;i<=m;i++){
  22. for(int j=0;j<n;j++){
  23. int c;
  24. cin>>c;
  25. b[i]+=(c<<j);
  26. }
  27. }
  28. it();
  29. for(int i=1;i<=cnt;i++){
  30. if((a[i]|b[1])==b[1]){
  31. f[1][a[i]]=1;
  32. }
  33. }
  34. int res=0;
  35. for(int i=2;i<=m;i++){
  36. for(int j=1;j<=cnt;j++){
  37. if((a[j]|b[i])!=b[i]){
  38. continue;
  39. }
  40. for(int q=1;q<=cnt;q++){
  41. if((a[q]|b[i-1])!=b[i-1]){
  42. continue;
  43. }
  44. if(a[j]&a[q]){
  45. continue;
  46. }
  47. f[i][a[j]]+=f[i-1][a[q]];
  48. f[i][a[j]]%=mod;
  49. }
  50. }
  51. }
  52. for(int i=1;i<=cnt;i++){
  53. res+=f[m][a[i]];
  54. res%=mod;
  55. }
  56. cout<<res;
  57. return 0;
  58. }