結果

問題 No.995 タピオカオイシクナーレ
ユーザー ngtkanangtkana
提出日時 2020-03-28 00:04:25
言語 C++17
(gcc 13.2.0 + boost 1.83.0)
結果
AC  
実行時間 14 ms / 2,000 ms
コード長 5,501 bytes
コンパイル時間 1,860 ms
コンパイル使用メモリ 201,852 KB
実行使用メモリ 4,380 KB
最終ジャッジ日時 2023-08-30 17:04:51
合計ジャッジ時間 4,686 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge12
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,380 KB
testcase_01 AC 2 ms
4,376 KB
testcase_02 AC 1 ms
4,380 KB
testcase_03 AC 1 ms
4,380 KB
testcase_04 AC 1 ms
4,380 KB
testcase_05 AC 2 ms
4,380 KB
testcase_06 AC 1 ms
4,380 KB
testcase_07 AC 2 ms
4,380 KB
testcase_08 AC 2 ms
4,376 KB
testcase_09 AC 1 ms
4,376 KB
testcase_10 AC 1 ms
4,380 KB
testcase_11 AC 2 ms
4,376 KB
testcase_12 AC 2 ms
4,376 KB
testcase_13 AC 1 ms
4,380 KB
testcase_14 AC 2 ms
4,376 KB
testcase_15 AC 2 ms
4,380 KB
testcase_16 AC 13 ms
4,376 KB
testcase_17 AC 13 ms
4,380 KB
testcase_18 AC 13 ms
4,380 KB
testcase_19 AC 13 ms
4,376 KB
testcase_20 AC 14 ms
4,376 KB
testcase_21 AC 13 ms
4,380 KB
testcase_22 AC 13 ms
4,376 KB
testcase_23 AC 13 ms
4,376 KB
testcase_24 AC 13 ms
4,376 KB
testcase_25 AC 13 ms
4,380 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
using lint=long long;
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,K;mint p,q;std::cin>>n>>m>>K>>p>>q;
    mint A=0,B=0;
    for(lint i=0;i<n;i++){
        lint x;std::cin>>x;
        (i<m?A:B)+=x;
    }
    using mat=std::array<std::array<mint,2>,2>;
    mat a;
    for(lint i=0;i<2;i++)for(lint j=0;j<2;j++){
        a.at(i).at(j)=i==j?1-p/q:p/q;
    }
    auto mul=[](mat const&a,mat const&b)->mat{
        mat c;
        for(lint i=0;i<2;i++)for(lint j=0;j<2;j++)c.at(i).at(j)=0;
        for(lint i=0;i<2;i++)for(lint j=0;j<2;j++)for(lint k=0;k<2;k++){
            c.at(i).at(k)+=a.at(i).at(j)*b.at(j).at(k);
        }
        return c;
    };
    mat b;
    for(lint i=0;i<2;i++)for(lint j=0;j<2;j++){
        b.at(i).at(j)=i==j;
    }
    for(;K;K/=2){
        if(K%2)b=mul(b,a);
        a=mul(a,a);
    }
    std::cout<<b.at(0).at(0)*A+b.at(0).at(1)*B<<'\n';
}
0