結果
問題 | No.462 6日知らずのコンピュータ |
ユーザー |
|
提出日時 | 2016-12-13 00:13:37 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 2,140 bytes |
コンパイル時間 | 1,651 ms |
コンパイル使用メモリ | 173,404 KB |
実行使用メモリ | 6,824 KB |
最終ジャッジ日時 | 2024-11-29 18:35:16 |
合計ジャッジ時間 | 3,894 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 84 |
ソースコード
#include "bits/stdc++.h" using namespace std; #define FOR(i,j,k) for(int (i)=(j);(i)<(int)(k);++(i)) #define rep(i,j) FOR(i,0,j) #define each(x,y) for(auto &(x):(y)) #define mp make_pair #define mt make_tuple #define all(x) (x).begin(),(x).end() #define debug(x) cout<<#x<<": "<<(x)<<endl #define smax(x,y) (x)=max((x),(y)) #define smin(x,y) (x)=min((x),(y)) #define MEM(x,y) memset((x),(y),sizeof (x)) #define sz(x) (int)(x).size() typedef long long ll; typedef pair<int, int> pii; typedef vector<int> vi; typedef vector<ll> vll; const int MOD = (int)1e9 + 7; int add(int a, int b){ int c = a + b; if(c >= MOD)c -= MOD; else if(c < 0)c += MOD; return c; } void sadd(int &a, int b){ a += b; if(a >= MOD)a -= MOD; else if(a < 0)a += MOD; } int mul(int a, int b){ return (int)((long long)a*b%MOD); } int bitcntll(unsigned long long x) { x = (x & 0x5555555555555555) + ((x >> 1) & 0x5555555555555555); x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333); x = (x & 0x0f0f0f0f0f0f0f0f) + ((x >> 4) & 0x0f0f0f0f0f0f0f0f); x = (x & 0x00ff00ff00ff00ff) + ((x >> 8) & 0x00ff00ff00ff00ff); x = (x & 0x0000ffff0000ffff) + ((x >> 16) & 0x0000ffff0000ffff); x = (x & 0x00000000ffffffff) + ((x >> 32) & 0x00000000ffffffff); return (int)x; } int main(){ ios::sync_with_stdio(false); cin.tie(0); int N, K; while(cin >> N >> K) { vll A(K); int a = 0, b = 0; rep(i, K) { cin >> A[i]; if(A[i] == 0)a = 1; if(A[i] == (1ll << N) - 1)b = 1; } if(!a)A.push_back(0); if(!b)A.push_back((1ll << N) - 1); K = sz(A); sort(all(A)); int ans = 1; bool ok = true; rep(i, K - 1) { if((A[i] & A[i + 1]) != A[i]) { ok = false; break; } else { ll x = A[i + 1] - A[i]; int y = bitcntll(x); for(int j = 2; j <= y; ++j) { ans=mul(ans, j); } } } if(!ok)ans = 0; cout << ans << endl; } }