Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## 理论最高复杂度是假的，实际算出来每次转移最多只有377*377

Posted by Techiah at 2018-05-16 20:53:41 on Problem 3254
```=.=我感觉加了一堆set和map试图剪枝反而增加了复杂度，纯暴力能跑得快很多

#define _CRT_SECURE_NO_WARNINGS
#pragma _attribute_((optimize("-O2")))

#include <iostream>
#include <queue>
#include <stack>
#include <cstdio>
#include <vector>
#include <map>
#include <list>
#include <set>
#include <cstdio>
#include <bitset>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <string>
#include <sstream>
#include <ctime>
#include <complex>
#include <iomanip>
//#define Endl endl
//#define int long long

//#define Local

using namespace std;
set<int> precal;

int now;

const int md = 1e8;

void pre(int p, int l)
{
if (p == 12)
{
precal.insert(now);
return;
}
if (l)
{
now <<= 1;
pre(p + 1, 0);
now >>= 1;
}
else
{
now <<= 1;
pre(p + 1, 0);
now >>= 1;
now <<= 1;
now++;
pre(p + 1, 1);
now >>= 1;
}
}

signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);

//freopen("input1.txt", "r", stdin);
//freopen("output1.txt", "w", stdout);

int n, m;
cin >> n >> m;

map<int, int> cal[4100];

pre(0, 0);
pre(0, 1);

now = 0;
for (int i = 0; i < m; i++)
{
now <<= 1;
int tmp;
cin >> tmp;
now += tmp;
}
for (set<int>::iterator it = precal.begin(); it != precal.end(); ++it)
{
if ((*it | now) == now)
cal[0].insert({ *it,1 });
}

for (int i = 1; i < n; i++)
{
now = 0;
for (int j = 0; j < m; j++)
{
now <<= 1;
int tmp;
cin >> tmp;
now += tmp;
}
for (set<int>::iterator it = precal.begin(); it != precal.end(); ++it)
{
if (*it > now)
break;
if ((*it | now) == now)
for (map<int, int>::iterator j = cal[i - 1].begin(); j != cal[i - 1].end(); ++j)
if ((j->first&*it) == 0)
cal[i][*it] += j->second, cal[i][*it] %= md;
}
}
int cont = 0;
for (map<int, int>::iterator j = cal[n - 1].begin(); j != cal[n - 1].end(); ++j)
cont += j->second, cont %= md;
cout << cont << endl;

#ifdef Local
cout << "time: " << (long long)clock() * 1000 / CLOCKS_PER_SEC << " ms" << endl;
#endif
return 0;
}```

Followed by: