51nod1798 打怪兽

设f[i] 为至少击败 i个怪兽的方案数 那么
击败i个的方案数则为 f[i] - f[i + 1]
答案即为 1~n f[i]的求和

设sum[i]为前 i个怪兽的攻击力
因为能量从1 ~ n分别为 0~n - 1那么 1 ~ i + 1都是可以被选择为前 i 个的 所以每次就是 乘2

如果sum[i] >= m的话那么就是 2^i * fac[n - i]
如果sum[i] < m的话 就要从前面选择一个 去减掉 因为每次都乘 fac[n - i]所以和只需要看 i 只需要存一个优先队列 判断即可

#include
#include
#include
#define x first
#define y secondusing namespace std;const int N = 5e5 + 10,mod = 1e9 + 7;
typedef pair<int,int> PII;
typedef long long ll;ll a[N];ll b[N],f[N];
ll fac[N];
priority_queue<PII,vector<PII>,greater<PII> > q;ll qpow(ll a,ll b){if(b == -1) return 1;ll s = 1;while(b){if(b & 1) s = s * a % mod;a = a * a % mod;b >>= 1;}return s;
}int main(){fac[0] = 1;for(int i = 1; i <= 5e5; i++){fac[i] = 1ll * fac[i - 1] * i % mod;}ll n,m;cin >> n >> m;for(int i = 1; i <= n; i++){scanf("%lld",&a[i]);b[i] = b[i - 1] + a[i];}q.push({a[1],1});ll ans = 0;ll sum = 0;sum += 1;for(int i = 1; i <= n - 1; i++){q.push({a[i + 1],i + 1});sum += qpow(2,i - 1);sum %= mod;if(b[i + 1] <= m){ans += qpow(2,i) * fac[n - i] % mod;}else{while(q.size()){PII p = q.top();if(b[i + 1] - p.x <= m) break;sum -= qpow(2,p.y - 2);sum %= mod;sum += mod;sum %= mod;q.pop();}ans += sum * fac[n - i] % mod;}ans %= mod;}if(b[n] <= m) ans += qpow(2,n - 1);cout << ((ans) % mod + mod) % mod << endl;return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！