#628732 (C++11) No.1426 Got a Covered OR

提出ソース

結果

問題	No.1426 Got a Covered OR
ユーザー	leaf_1415
提出日時	2021-03-12 22:41:00
言語	C++11 (gcc 11.4.0)
結果	AC
実行時間	1,791 ms / 2,000 ms
コード長	3,721 bytes
コンパイル時間	643 ms
コンパイル使用メモリ	82,704 KB
実行使用メモリ	33,024 KB
最終ジャッジ日時	2024-10-14 13:14:57
合計ジャッジ時間	14,107 ms
ジャッジサーバーID （参考情報）	judge4 / judge3

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	6 ms 6,528 KB
testcase_01	AC	6 ms 6,528 KB
testcase_02	AC	6 ms 6,528 KB
testcase_03	AC	6 ms 6,528 KB
testcase_04	AC	6 ms 6,528 KB
testcase_05	AC	6 ms 6,528 KB
testcase_06	AC	6 ms 6,400 KB
testcase_07	AC	6 ms 6,400 KB
testcase_08	AC	6 ms 6,656 KB
testcase_09	AC	5 ms 6,528 KB
testcase_10	AC	6 ms 6,528 KB
testcase_11	AC	5 ms 6,400 KB
testcase_12	AC	872 ms 20,992 KB
testcase_13	AC	799 ms 23,680 KB
testcase_14	AC	693 ms 19,584 KB
testcase_15	AC	743 ms 19,968 KB
testcase_16	AC	124 ms 8,320 KB
testcase_17	AC	183 ms 9,216 KB
testcase_18	AC	1,239 ms 24,832 KB
testcase_19	AC	1,268 ms 25,088 KB
testcase_20	AC	493 ms 13,696 KB
testcase_21	AC	761 ms 17,536 KB
testcase_22	AC	1,771 ms 33,024 KB
testcase_23	AC	1,783 ms 33,024 KB
testcase_24	AC	14 ms 7,168 KB
testcase_25	AC	1,791 ms 33,024 KB
testcase_26	AC	16 ms 7,296 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include <iostream>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstdlib>
#include <cassert>
#include <vector>
#include <list>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <bitset>
#include <string>
#include <algorithm>
#include <utility>
#include <complex>
#define rep(x, s, t) for(llint (x) = (s); (x) <= (t); (x)++)
#define reps(x, s) for(llint (x) = 0; (x) < (llint)(s).size(); (x)++)
#define chmin(x, y) (x) = min((x), (y))
#define chmax(x, y) (x) = max((x), (y))
#define sz(x) ((ll)(x).size())
#define ceil(x, y) (((x)+(y)-1) / (y))
#define all(x) (x).begin(),(x).end()
#define outl(...) dump_func(__VA_ARGS__)
#define inf 1e18

using namespace std;

typedef long long llint;
typedef long long ll;
typedef pair<ll, ll> P;
bool exceed(ll x, ll y, ll m){return x >= m / y + 1;}

struct edge{
	ll to, cost;
	edge(){}
	edge(ll a, ll b){
		to = a, cost = b;
	}
};

template<typename T>
ostream& operator << (ostream& os, vector<T>& vec) {
	for(int i = 0; i<vec.size(); i++) {
		os << vec[i] << (i + 1 == vec.size() ? "" : " ");
	}
	return os;
}
template<typename T, typename U>
ostream& operator << (ostream& os, pair<T, U>& pair_var) {
	os << "(" << pair_var.first << ", " << pair_var.second << ")";
	return os;
}
template<typename T, typename U>
ostream& operator << (ostream& os, map<T, U>& map_var) {
	for(typename map<T, U>::iterator itr = map_var.begin(); itr != map_var.end(); itr++) {
		os << "(" << itr->first << ", " << itr->second << ")";
		itr++;
		if(itr != map_var.end()) os << ",";
		itr--;
	}
	return os;
}
template<typename T>
ostream& operator << (ostream& os, set<T>& set_var) {
	for(typename set<T>::iterator itr = set_var.begin(); itr != set_var.end(); itr++) {
		os << *itr;
		++itr;
		if(itr != set_var.end()) os << " ";
		itr--;
	}
	return os;
}
void dump_func() {cout << endl;}
template <class Head, class... Tail>
void dump_func(Head &&head, Tail &&... tail) {
    cout << head;
    if(sizeof...(Tail) > 0) cout << " ";
    dump_func(std::move(tail)...);
}

#define mod 1000000007

const int FACT_MAX = 200005;
llint fact[FACT_MAX], fact_inv[FACT_MAX];

llint modpow(llint a, llint n)
{
	if(n == 0) return 1;
	if(n % 2){
		return ((a%mod) * (modpow(a, n-1)%mod)) % mod;
	}
	else{
		return modpow((a*a)%mod, n/2) % mod;
	}
}

void make_fact()
{
	llint val = 1;
	fact[0] = 1;
	for(int i = 1; i < FACT_MAX; i++){
		val *= i;
		val %= mod;
		fact[i] = val;
	}
	fact_inv[FACT_MAX-1] = modpow(fact[FACT_MAX-1], mod-2);
	for(int i = FACT_MAX-2; i >= 0; i--){
		fact_inv[i] = fact_inv[i+1] * (i+1) % mod;
	}
}

llint comb(llint n, llint k)
{
	llint ret = 1;
	ret *= fact[n];
	ret *= fact_inv[k], ret %= mod;
	ret *= fact_inv[n-k], ret %= mod;
	return ret;
}

ll n;
ll b[100005];
ll add[100005], sum[100005];
ll dp[100005][32];

int main(void)
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	make_fact();
	
	cin >> n;
	rep(i, 1, n) cin >> b[i];
	
	ll ans = 1;
	rep(i, 0, 29){
		ll l = 0, r = n+1;
		rep(j, 1, n){
			if(b[j] == -1) continue;
			if(b[j]&(1<<i)) chmin(r, j);
			else chmax(l, j);
		}
		if(l >= r){
			outl(0);
			return 0;
		}
		if(r < n+1) add[l]++;
	}
	
	sum[0] = add[0];
	rep(i, 1, n) sum[i] = sum[i-1] + add[i];
	
	//rep(i, 0, n) cout << sum[i] << " "; cout << endl;
	
	dp[0][0] = 1;
	rep(i, 0, n-1){
		if(i > 0 && b[i] != -1){
			rep(j, 0, 30) if(j != sum[i-1]) dp[i][j] = 0;
		}
		rep(j, 0, 30){
			rep(k, 0, 30){
				if(j+k > sum[i]) break;
				ll mul = modpow(2, j);
				if(k == 0) mul += mod-1, mul %= mod;
				dp[i+1][j+k] += dp[i][j] * mul % mod * comb(sum[i]-j, k) % mod, dp[i+1][j+k] %= mod;
			}
		}
	}
	
	/*rep(i, 0, n){
		rep(j, 0, 5) cout << dp[i][j] << " "; cout << endl;
	}*/
	
	outl(dp[n][sum[n]]);
	
	return 0;
}

yukicoder

結果

テストケース

ソースコード