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;
}