B3903 题解

GTAH2333 · 2024-04-14 21:15:40 · 题解

提供一种支持多次询问的方法。

观察题目，发现可以一定可以将序列 x 中的元素分成四类：黑球、灰球、白球和不可存在球。其中黑球是和灰球或黑球的数相加都大于 x 的数，灰球是只与黑球相加大于 x 的数，白球则与任何数相加都小于等于 x ， 而不可存在球则是自身便大于等于 x 的数。

可以这样分类的正确性显然可以证明：首先，题目要求 a_i 一定是二的整数次幂，则可以将等于 x 的二进制最高位的数作为黑球，然后将与黑球相加大于 x 且不等于黑球的作为灰球，余下作白球。由于二的整数次幂的要求，白球一定小于等于灰球的一半，灰球一定小于等于黑球的一半，而黑球一定小于等于 x ，则可以满足要求。若序列中有一个数大于等于 x ，显然无解，因为无论是什么数排列在它旁边都不符合要求，特判设有即可。

现在我们将这个问题转化为一个排列问题。可设黑球个数为 k_1 ，灰球个数为 k_2 ，白球个数为 k_3 ，且要求黑黑不相邻，可得出如下公式：

公式的意义：将白球有序排列后，将 k_1 黑球放入 k_3+1 个空并且两个球不在同一个空，在剩下的 k_3-k_1+1 个空中依次放入灰球，而每放入一个灰球，空的个数就会加一，所以是连乘。

再特判一些特殊情况，即可正确求出答案。

code：

#include<iostream>
using namespace std;
const int N = 2e5 + 5, mod = 1e9 + 7;
inline int qpow(int a,int b) {
    int res = 1;
    while(b) {
        if(b&1) res = (1ll*a*res)%mod;
        a = (1ll*a*a)%mod;
        b>>=1;
    } 
    return res;
}
int n, k1, k2, k3;
int jc[N] = {1,1}, inv[N] = {1,1};
unsigned long long x1, val, x, a[N];
int main() {
    n = read(), x = readULL(), x1 = x>>1;
    for(int i=1;i<=n;++i) {
        a[i] = readULL(), jc[i+1] = (1ll * (i+1) * jc[i]) % mod;
        if(a[i] > x) { cout<<0; return 0; }
        else if(a[i] > x1) ++k1, val = a[i];
    }
    inv[n+1] = qpow(jc[n+1], mod-2), x -= val;
    for(int i=n;i>=1;--i) {
        inv[i] = 1ll * inv[i+1] * (i+1) % mod;
        if(a[i] > x && a[i] != val) ++k2;
        else if(a[i] <= x) ++k3;
    }
    if(k1>k3+1) cout << 0;
    else if(k2 == 0) cout << 1ll * jc[k3] * jc[k3+1] % mod * inv[k3+1-k1] % mod;
    else cout << 1ll * jc[k3] * jc[k3+1] % mod * inv[k3+1-k1] % mod * jc[k3-k1+k2] % mod * inv[k3-k1] % mod;
    return 0;
}