結果
問題 | No.754 畳み込みの和 |
ユーザー | ngtkana |
提出日時 | 2020-02-26 13:25:31 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 23 ms / 5,000 ms |
コード長 | 5,325 bytes |
コンパイル時間 | 1,415 ms |
コンパイル使用メモリ | 170,260 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-10-13 15:17:37 |
合計ジャッジ時間 | 1,935 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 22 ms
5,248 KB |
testcase_01 | AC | 22 ms
5,248 KB |
testcase_02 | AC | 23 ms
5,248 KB |
ソースコード
#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; }