B 赛博算命

Description:

Constraints:

• \(1 \leq q \leq 10^6, 2 \leq k \leq 10^9, q\leq k\)

Analysis:

Solution:

#include<bits/stdc++.h>
using namespace std;

#define mod 1000000007

typedef long long ll;
typedef unsigned long long ull;

const int maxn = 1e5+5;
const int maxm = 1e6+5;

ll qpow(ll a,ll n) {
	ll ans = 1;
	while(n) {
		if(n & 1) ans *= a;
		a *= a;
		n >>= 1; 
	}
	return ans;
}
map<int,ll> mp; //记录幂指数
vector<int> v;
int main() {
	for(int i=0;i<31;i++) mp[i] = qpow(2,i); //初始化
	
	int n,k; cin >> n >> k;
	for(int i=0;i<n;i++) {
		int id; cin >> id;
		v.push_back(id);
	}
	ll ans = 1;
	for(int i=0;i<31;i++) {
		if(k == mp[i]) {
			for(int j=0;j<v.size();j++) {
				ans = ans * (k-v[j]+1) % mod;
			}
			break;
		}
		if(mp[i] < k && k < mp[i+1]) {
			for(int j=0;j<v.size();j++) {
				if(v[j] >= mp[i]+1 || v[j] <= k-mp[i]) ans = ans * (k+1-v[j]) % mod;
				else ans = ans * (k+1) % mod;
			}
			break;
		}
	}
	cout << ans << endl;
	return 0;
}