結果
問題 | No.462 6日知らずのコンピュータ |
ユーザー |
![]() |
提出日時 | 2019-08-24 01:09:31 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 2,175 bytes |
コンパイル時間 | 1,928 ms |
コンパイル使用メモリ | 176,764 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-10-13 14:54:35 |
合計ジャッジ時間 | 4,150 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 84 |
ソースコード
#include "bits/stdc++.h"#define ALL(obj) (obj).begin(),(obj).end()#define RALL(obj) (obj).rbegin(),(obj).rend()#define REP(i, n) for(int i = 0; i < (int)(n); i++)#define REPR(i, n) for(int i = (int)(n); i >= 0; i--)#define FOR(i,n,m) for(int i = (int)(n); i < int(m); i++)using namespace std;typedef long long ll;const int MOD = 1e9 + 7;const int INF = MOD - 1;const ll LLINF = 4e18;struct mint {private:ll x;public:mint(ll x = 0) :x(x%MOD) {}mint& operator+=(const mint a) {if ((x += a.x) >= MOD) x -= MOD;return *this;}mint& operator-=(const mint a) {if ((x += MOD - a.x) >= MOD) x -= MOD;return *this;}mint& operator*=(const mint a) {(x *= a.x) %= MOD;return *this;}mint operator+(const mint a) const {mint res(*this);return res += a;}mint operator-(const mint a) const {mint res(*this);return res -= a;}mint operator*(const mint a) const {mint res(*this);return res *= a;}friend ostream& operator<<(ostream& os, const mint& n) {return os << n.x;}};int bitcount(ll n) {int cnt = 0;while (n != 0) {if (n & 1) cnt++;n >>= 1;}return cnt;}mint fact(ll n) {mint res = 1;for (ll i = 2; i <= n; i++) {res *= i;}return res;}int main() {int n, k; cin >> n >> k;vector<bool> exist(n+1, false);vector<pair<int,ll>> a(k);REP(i, k) {cin >> a[i].second;int bc = a[i].first = bitcount(a[i].second);if (!exist[bc]) {exist[bc] = true;}else {puts("0");return 0;}}if (!exist[0]) a.push_back({0,0LL});if (!exist[n]) a.push_back({n,(1LL << n) - 1});sort(ALL(a));mint ans = 1;k = a.size();REP(i, k - 1) {if ((a[i].second & a[i + 1].second) != a[i].second) {puts("0");return 0;}else {ans *= fact(a[i + 1].first - a[i].first);}}cout << ans << endl;getchar(); getchar();}