結果
問題 | No.754 畳み込みの和 |
ユーザー | sigma425 |
提出日時 | 2018-12-20 03:09:01 |
言語 | C++11 (gcc 11.4.0) |
結果 |
AC
|
実行時間 | 82 ms / 5,000 ms |
コード長 | 2,587 bytes |
コンパイル時間 | 1,331 ms |
コンパイル使用メモリ | 160,744 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-09-25 08:19:32 |
合計ジャッジ時間 | 2,177 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 82 ms
6,812 KB |
testcase_01 | AC | 82 ms
6,944 KB |
testcase_02 | AC | 82 ms
6,940 KB |
ソースコード
#include <bits/stdc++.h> #define rep(i,n) for(int i=0;i<(int)(n);i++) #define rep1(i,n) for(int i=1;i<=(int)(n);i++) #define all(c) c.begin(),c.end() #define pb push_back #define fs first #define sc second #define show(x) cout << #x << " = " << (x) << endl #define chmin(x,y) x=min(x,y) #define chmax(x,y) x=max(x,y) using namespace std; template<class S,class T> ostream& operator<<(ostream& o,const pair<S,T> &p){ return o<<"("<<p.fs<<","<<p.sc<<")"; } template<class T> ostream& operator<<(ostream& o,const vector<T> &vc){ o<<"{"; for(const T& v:vc) o<<v<<","; o<<"}"; return o; } using ll = long long; template<class T> using V = vector<T>; template<class T> using VV = vector<vector<T>>; template<unsigned int mod_> struct ModInt{ using uint = unsigned int; using ll = long long; using ull = unsigned long long; constexpr static uint mod = mod_; uint v; ModInt():v(0){} ModInt(ll v):v(normS(v%mod+mod)){} explicit operator bool() const {return v!=0;} static uint normS(const uint &x){return (x<mod)?x:x-mod;} // [0 , 2*mod-1] -> [0 , mod-1] static ModInt make(const uint &x){ModInt m; m.v=x; return m;} ModInt operator+(const ModInt& b) const { return make(normS(v+b.v));} ModInt operator-(const ModInt& b) const { return make(normS(v+mod-b.v));} ModInt operator-() const { return make(normS(mod-v)); } ModInt operator*(const ModInt& b) const { return make((ull)v*b.v%mod);} ModInt operator/(const ModInt& b) const { return *this*b.inv();} ModInt& operator+=(const ModInt& b){ return *this=*this+b;} ModInt& operator-=(const ModInt& b){ return *this=*this-b;} ModInt& operator*=(const ModInt& b){ return *this=*this*b;} ModInt& operator/=(const ModInt& b){ return *this=*this/b;} ll extgcd(ll a,ll b,ll &x,ll &y) const{ ll u[]={a,1,0},v[]={b,0,1}; while(*v){ ll t=*u/ *v; rep(i,3) swap(u[i]-=t*v[i],v[i]); } if(u[0]<0) rep(i,3) u[i]=-u[i]; x=u[1],y=u[2]; return u[0]; } ModInt inv() const{ ll x,y; extgcd(v,mod,x,y); return make(normS(x+mod)); } bool operator==(const ModInt& b) const { return v==b.v;} bool operator!=(const ModInt& b) const { return v!=b.v;} friend istream& operator>>(istream &o,ModInt& x){ ll tmp; o>>tmp; x=ModInt(tmp); return o; } friend ostream& operator<<(ostream &o,const ModInt& x){ return o<<x.v;} }; using mint = ModInt<1000000007>; int main(){ int N; cin>>N; V<mint> a(N+1),b(N+1); rep(i,N+1){ int x; cin>>x; a[i] = x; } rep(i,N+1){ int x; cin>>x; b[i] = x; } mint res = 0; mint s = 0; for(int i=N;i>=0;i--){ s += b[N-i]; res += a[i]*s; } cout<<res<<endl; }