結果
問題 | No.462 6日知らずのコンピュータ |
ユーザー |
|
提出日時 | 2017-07-31 17:09:45 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 1,584 bytes |
コンパイル時間 | 1,135 ms |
コンパイル使用メモリ | 82,336 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-10-11 00:10:11 |
合計ジャッジ時間 | 2,719 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 84 |
ソースコード
#include<cstdio>#include<iostream>#include<algorithm>#include<string>#include<queue>#include<vector>#include<functional>#include<cmath>#include<map>#include<stack>#include<set>#include<numeric>#include<limits>#define all(x) (x).begin(),(x).end()#define rall(x) (x).rbegin(),(x).rend()using namespace std;typedef long long ll;typedef pair<int, int> pi;typedef pair<ll, ll> pl;typedef pair<ll, string> pls;ll mod = ll(1e9 + 7);ll fuc(ll n) {ll res = 1;for (int i = 1; i <= n; i++) {res *= i;res %= mod;}return res;}int numofbits(ll v) {ll count = (v & 0x5555555555555555) + ((v >> 1) & 0x5555555555555555);count = (count & 0x3333333333333333) + ((count >> 2) & 0x3333333333333333);count = (count & 0x0f0f0f0f0f0f0f0f) + ((count >> 4) & 0x0f0f0f0f0f0f0f0f);count = (count & 0x00ff00ff00ff00ff) + ((count >> 8) & 0x00ff00ff00ff00ff);count = (count & 0x0000ffff0000ffff) + ((count >> 16) & 0x0000ffff0000ffff);return (int)((count & 0x00000000ffffffff) + ((count >> 32) & 0x00000000ffffffff));}int main(){int n, k;ll a[100] = {0};ll ans;cin >> n >> k;for (int i = 0; i < k; i++) {cin >> a[i];}sort(a, a + k);for (int i = 0; i < k-1; i++) {if ((a[i + 1] | a[i]) != a[i + 1]) {cout << 0 << endl;return 0;}}if (k == 0) {ans = fuc(n);cout << ans << endl;return 0;}ans = fuc(numofbits(a[0]));for (int i = 1; i < k; i++) {ans *= fuc(numofbits(a[i]) - numofbits(a[i - 1]));ans %= mod;}ans *= fuc(n - numofbits(a[k - 1]));ans %= mod;cout << ans << endl;return 0;}