結果
問題 | No.766 金魚すくい |
ユーザー |
![]() |
提出日時 | 2020-03-31 22:18:29 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 31 ms / 1,500 ms |
コード長 | 5,504 bytes |
コンパイル時間 | 2,649 ms |
コンパイル使用メモリ | 205,588 KB |
最終ジャッジ日時 | 2025-01-09 11:22:03 |
ジャッジサーバーID (参考情報) |
judge5 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 42 |
ソースコード
#include<bits/stdc++.h>using lint=long long;using real=long double;template<class T>T inverse(T a, T m){T u=0,v=1;while(a!=0){T t=m/a;m-=t*a;std::swap(a,m);u-=t*v;std::swap(u,v);}assert(m==1);return u;}template<class T>class modular {public:int value;constexpr modular() = default;constexpr modular(const modular&) = default;constexpr modular(modular&&) = default;modular&operator=(const modular&) = default;modular&operator=(modular&&) = default;template<class U>modular(const U&x){value= normalize(x);}template<class U>static int normalize(const U& x){int v=static_cast<int>(-mod()<=x&&x<mod()?x:x%mod());if(v<0)v+=mod();return v;}template<class U>explicit operator U()const{return static_cast<U>(value);}constexpr static auto mod(){return T::value;}auto&operator+=(const modular&other) {if((value+=other.value)>=mod())value-=mod();return *this;}auto&operator-=(const modular& other){if((value-=other.value)<0)value+=mod();return *this;}template <class U>auto& operator+=(const U& other){return*this+=modular(other);}template <class U>auto& operator-=(const U& other){return*this-=modular(other);}auto operator-()const{return modular(-value);}auto&operator++(){return*this+=1;}auto&operator--(){return*this-=1;}auto operator++(int){modular result(*this);operator++();return result;}auto operator--(int){modular result(*this);operator--();return result;}template<class U=T>auto&operator*=(const modular&rhs){value=normalize(static_cast<std::int64_t>(value)*static_cast<std::int64_t>(rhs.value));return *this;}auto&operator/=(const modular&rhs){return*this*=modular(inverse(rhs.value, mod()));}};template<class T>struct is_modular:std::false_type{};template<class T>struct is_modular <modular<T>>:std::true_type{};template<class T>constexpr bool is_modular_v=is_modular<T>::value;template<class t> bool operator==(const modular<t>& lhs, const modular<t>& rhs){return lhs()==rhs();}template<class T,class U>bool operator==(const modular<T>& lhs, U rhs){return lhs==modular<T>(rhs);}template<class T,class U>bool operator==(U lhs, const modular<T>& rhs){return modular<T>(lhs)==rhs;}template<class T> bool operator!=(const modular<T>& lhs, const modular<T>& rhs){return !(lhs == rhs);}template<class T,class U>bool operator!=(const modular<T>& lhs, U rhs){return !(lhs==rhs);}template<class T,class U>bool operator!=(U lhs, const modular<T>& rhs){return !(lhs==rhs);}template<class T> modular<T> operator+(const modular<T>& lhs, const modular<T>& rhs){return modular<T>(lhs)+=rhs;}template<class T,class U>modular<T>operator+(const modular<T>& lhs,U rhs){return modular<T>(lhs)+=rhs;}template<class T,class U>modular<T>operator+(U lhs,const modular<T>& rhs){return modular<T>(lhs)+=rhs;}template<class T>modular<T>operator-(const modular<T>& lhs,const modular<T>& rhs){return modular<T>(lhs)-=rhs;}template<class T,class U>modular<T>operator-(const modular<T>& lhs,U rhs){return modular<T>(lhs)-=rhs;}template<class T,class U>modular<T>operator-(U lhs,const modular<T>& rhs){return modular<T>(lhs)-=rhs;}template<class T>modular<T>operator*(const modular<T>& lhs,const modular<T>& rhs){return modular<T>(lhs)*=rhs;}template<class T,class U>modular<T>operator*(const modular<T>& lhs,U rhs){return modular<T>(lhs)*=rhs;}template<class T,class U>modular<T>operator*(U lhs,const modular<T>& rhs){return modular<T>(lhs)*=rhs;}template<class T>modular<T>operator/(const modular<T>& lhs,const modular<T>& rhs){return modular<T>(lhs)/=rhs;}template<class T,class U>modular<T>operator/(const modular<T>& lhs,U rhs){return modular<T>(lhs)/=rhs;}template<class T,class U>modular<T>operator/(U lhs,const modular<T>& rhs){return modular<T>(lhs)/=rhs;}template<class T,class U>modular<T>power(const modular<T>&a,U b) {assert(b>=0);modular<T>x=a,ret=1;for (;b>0;b/=2){if(b%2==1)ret*=x;x*=x;}return ret;}template<class T>auto operator<<(std::ostream&os,const T&a)->std::enable_if_t<is_modular_v<T>,std::ostream&>{return os<<a.value;}template<class T>auto operator>>(std::istream&is,T&a)->std::enable_if_t<is_modular_v<T>,std::istream&>{return is>>a.value;}constexpr int mod=1'000'000'007;using mint = modular<std::integral_constant<std::decay_t<decltype(mod)>, mod>>;int main(){std::cin.tie(nullptr);std::ios_base::sync_with_stdio(false);std::cout.setf(std::ios_base::fixed);std::cout.precision(15);lint n,m;mint p;std::cin>>n>>m>>p;p=p/100;lint N=n+m;std::vector<mint>fact(N+1),finv(N+1);fact.at(0)=1;for(lint i=1;i<=N;i++)fact.at(i)=fact.at(i-1)*i;finv.at(N)=mint{1}/fact.at(N);for(lint i=N;i>=1;i--)finv.at(i-1)=finv.at(i)*i;auto binom=[&](lint n,lint k){return fact.at(n)*finv.at(k)*finv.at(n-k);};std::vector<mint>a(n+1);mint now=power(p,m);for(lint i=0;i<n;i++){a.at(i)=binom(m+i-1,i)*now;now*=1-p;}a.at(n)=1-std::accumulate(a.begin(),a.begin()+n,mint{0});std::vector<lint>b(n+1);for(lint i=1;i<=n;i++)std::cin>>b.at(i);std::sort(b.rbegin(),b.rend()-1);std::partial_sum(b.begin(),b.end(),b.begin());std::cout<<std::inner_product(a.begin(),a.end(),b.begin(),mint{0})<<'\n';}