結果
問題 | No.754 畳み込みの和 |
ユーザー | KPCCoiL |
提出日時 | 2018-12-20 19:07:32 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 25 ms / 5,000 ms |
コード長 | 5,133 bytes |
コンパイル時間 | 761 ms |
コンパイル使用メモリ | 73,360 KB |
実行使用メモリ | 6,940 KB |
最終ジャッジ日時 | 2024-09-25 09:09:13 |
合計ジャッジ時間 | 1,114 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 25 ms
6,816 KB |
testcase_01 | AC | 25 ms
6,940 KB |
testcase_02 | AC | 25 ms
6,940 KB |
ソースコード
#include <iostream> #include <type_traits> #include <algorithm> #include <string> #include <vector> #include <numeric> // Metafunctions {{{ template <class F, class... Args> auto is_valid_fn(F fn, Args... args) -> decltype( fn(args...), std::true_type{}); std::false_type is_valid_fn(...); template <class F, class... Args> struct is_valid : decltype(is_valid_fn(std::declval<F>(), std::declval<Args>()...)) {}; struct is_container_impl { template <class T> auto operator() (T t) -> decltype(std::begin(t)); }; template <class T> struct is_container : is_valid<is_container_impl, T> {}; template <class T> struct is_nonstring_container : std::integral_constant<bool, is_container<T>{} && !std::is_same<T, std::string>{}> {}; // }}} // {{{ Dirty stuffs using ll = long long; using Z = ll; #define rep(i, n) for (decltype(n) i = 0; i < (n); ++i) #define rrep(i, n) for (auto i = (n); i >= 0; --i) #define btwn(i, from, below) for (auto i = (from); i < (below); ++i) #define rbtwn(i, from, above) for (auto i = (from); i >= (above); --i) #define each(e, c) for (auto&& e : c) #define all(c) std::begin(c), std::end(c) // }}} // Range {{{ template <class Container> class slice_wrapper { public: using iterator = typename Container::iterator; private: Container& entity; iterator start, last; public: slice_wrapper(Container& container, std::size_t head, std::size_t tail) : entity(container), start(std::next(std::begin(container), head)), last(std::prev(std::end(container), tail)) {} iterator begin() const { return start; } iterator end() const { return last; } }; template <class Container> inline slice_wrapper<Container> slice(Container& container, std::size_t head, std::size_t tail = 0) { return slice_wrapper<Container>(container, head, tail); } // }}} // I/O utlity {{{ #define HEAD(x, ...) x #define READ_INPUT(T, ...) T HEAD(__VA_ARGS__); read_input(__VA_ARGS__) #define rz(...) READ_INPUT(Z, __VA_ARGS__) #define rint(...) READ_INPUT(int, __VA_ARGS__) #define rll(...) READ_INPUT(ll, __VA_ARGS__) #define rstr(s) READ_INPUT(std::string, s) #define RCONT_IMPL(c, ...) c; static_assert(is_container<decltype(c)>::value, #c " is not a container"); read_input(c, __VA_ARGS__) #define rcont(...) __VA_ARGS__ RCONT_IMPL #define rvec(...) rcont(std::vector<__VA_ARGS__>) struct is_readable_impl { template <class T> auto operator() (T t) -> decltype(std::cin >> t); }; template <class T> struct is_readable : is_valid<is_readable_impl, T> {}; template <class T> std::enable_if_t<is_nonstring_container<T>{}> read_input(T&, std::size_t); template <class T, class U> void read_input(std::pair<T, U>&); template <class T> std::enable_if_t<is_nonstring_container<T>{}> read_input(T&); template <class T> std::enable_if_t<is_nonstring_container<T>{}> read_input(T&, std::size_t , std::size_t, std::size_t); template <class T> std::enable_if_t<is_readable<T>{}> read_input(T& value) { std::cin >> value; } template <class T> std::enable_if_t<std::is_integral<T>{}> read_input(T& value, T offset) { read_input(value); value -= offset; } template <class T> std::enable_if_t<is_nonstring_container<T>{}> read_input(T& container, std::size_t n) { container = T(n); read_input(container); } template <class T, class U> void read_input(std::pair<T, U>& pair) { read_input(pair.first); read_input(pair.second); } template <class T> std::enable_if_t<is_nonstring_container<T>{}> read_input(T& container) { for (auto& elem : container) read_input(elem); } template <class T> std::enable_if_t<is_nonstring_container<T>{}> read_input(T& container, std::size_t n, std::size_t sentinel_l, std::size_t sentinel_r) { container = T(n); for (auto& elem : slice(container, sentinel_l, sentinel_r)) { read_input(elem); } } template <class T, class U> std::ostream& operator<<(std::ostream& os, std::pair<T, U> pair) { os << '(' << pair.first << ", " << pair.second << ')'; return os; } template <class C> std::enable_if_t<is_nonstring_container<C>{}, std::ostream&> operator<< (std::ostream& os, C container) { os << *std::begin(container); for (auto& elem : slice(container, 1)) { os << ' ' << elem; } return os; } void accelerate_IO() { std::ios_base::sync_with_stdio(false); std::cin.tie(nullptr); } // }}} // Debugging {{{ #ifdef DEBUG # define show(expr) std::cerr << "\e[33m[Show : line " << __LINE__ << "] " << #expr << " = " << (expr) << "\e[m" << std::endl # define msg(message) std::cerr << "\e[33m[Message : line " << __LINE__ << "] " << message << "\e[m" << std::endl # define debug if (true) #else # define show(expr) inline void msg(...) {} # define debug if (false) #endif // }}} using namespace std; int main() { constexpr Z M = 1000000007; accelerate_IO(); rz(n); rvec(Z)(a, n + 1); rvec(Z)(b, n + 1); vector<Z> pb(n + 2); partial_sum(all(b), begin(pb) + 1, [] (Z x, Z y) { return (M + x + y) % M; }); show(pb); ll sum = 0; rep(i, n + 1) { show(sum); sum += a[i] * pb[n - i + 1]; sum %= M; } cout << sum << endl; }