結果

問題 No.754 畳み込みの和
ユーザー ngtkanangtkana
提出日時 2020-02-26 13:25:31
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 29 ms / 5,000 ms
コード長 5,325 bytes
コンパイル時間 1,981 ms
コンパイル使用メモリ 165,936 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-04-21 16:21:23
合計ジャッジ時間 2,392 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 29 ms
5,248 KB
testcase_01 AC 28 ms
5,376 KB
testcase_02 AC 28 ms
5,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using longlong=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>std::string to_string(const modular<T>& a) {
    return std::to_string(a.value);
}
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&> {
    long long x;is>>x;
    a=T(x);
    return is;
}

// using mod_type = int;
// struct variable_mod { static mod_type value; };
// mod_type variable_mod::value;
// mod_type& mod = variable_mod::value;
// using mint = modular< variable_mod >;

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::cin.sync_with_stdio(false);
    int n;std::cin>>n;
    n++;
    std::vector<mint>a(n),b(n+1);
    for(int i=0;i<n;i++)std::cin>>a.at(i);
    for(int i=1;i<=n;i++){
        std::cin>>b.at(i);
        b.at(i)+=b.at(i-1);
    }
    mint ans=0;
    for(int i=0;i<n;i++){
        ans+=a.at(i)*b.at(n-i);
    }
    std::cout<<ans<<std::endl;
}
0