結果
問題 | No.2111 Sum of Diff |
ユーザー |
|
提出日時 | 2022-10-28 21:36:44 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 179 ms / 2,000 ms |
コード長 | 11,451 bytes |
コンパイル時間 | 2,328 ms |
コンパイル使用メモリ | 208,184 KB |
最終ジャッジ日時 | 2025-02-08 14:11:54 |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 20 |
ソースコード
#include<bits/stdc++.h>#pragma GCC target("avx2")#pragma GCC optimize("O3")#pragma GCC optimize("unroll-loops")using namespace std;using ll=long long;using ld=long double;using ull=unsigned long long;using i128 = __int128_t;#define rep(i,n) for(ll i=0;i<ll(n);i++)#define rep2(i,n) for(ll i=n-1;i>=0;i--)#define rep3(i,a,b) for(ll i=a;i<=ll(b);i++)#define rep4(i,a,b) for(ll i=a;i>=ll(b);i--)#define forv(i,V) for(const auto& i:V)#define all(x) x.begin(),x.end()#define fi first#define se second#define SIZE(x) int(x.size())//constexpr ll mod=998244353;//constexpr ll mod=1000000007;#define pi 3.14159265358979323#define INF32 2147483647#define INF64 9223372036854775807#define faster ios::sync_with_stdio(false);std::cin.tie(nullptr)#define pii pair<int, int>#define pll pair<ll, ll>#define pb push_back#define eb emplace_back#define mp make_pair#define rev reverse#define vi vector<int>#define vll vector<ll>#define vpi vector<pair<int,int>>#define vpll vector<pair<ll,ll>>#define vvi vector<vector<int>>#define vvll vector<vector<ll>>#define prq priority_queue#define lb lower_bound#define ub upper_bound#define popcnt __builtin_popcountll#define TLE while(true)#define RE assert(false);#define MLE vector<vector<vector<long long>>> mle_mle(400,vector<vector<long long>>(1000,vector<long long>(1000)));const string YESNO[2] = {"NO", "YES"};const string YesNo[2] = {"No", "Yes"};const string yesno[2] = {"no", "yes"};#define rall(n) (n).rbegin(),(n).rend()#define INT(...) int __VA_ARGS__;scan(__VA_ARGS__)#define LL(...) ll __VA_ARGS__;scan(__VA_ARGS__)#define STR(...) string __VA_ARGS__;scan(__VA_ARGS__)#define CHR(...) char __VA_ARGS__;scan(__VA_ARGS__)#define DBL(...) double __VA_ARGS__;scan(__VA_ARGS__)#define LD(...) ld __VA_ARGS__;scan(__VA_ARGS__)template<typename T,typename U>ostream &operator<<(ostream&os,const pair<T,U>&p){os<<p.first<<" "<<p.second;return os;}template<typename T,typename U>istream &operator>>(istream&is,pair<T,U>&p){is>>p.first>>p.second;return is;}template<typename T>ostream &operator<<(ostream&os,const vector<T>&v){for(auto it=v.begin();it!=v.end();){os<<*it<<((++it)!=v.end()?" ":"");}return os;}template<typename T>istream &operator>>(istream&is,vector<T>&v){for(T &in:v){is>>in;}return is;}void scan(){}template<class Head,class... Tail>void scan(Head&head,Tail&... tail){cin>>head;scan(tail...);}template<class T>void print(const T &t){cout<<t<<'\n';}template<class Head, class... Tail>void print(const Head &head, const Tail &... tail){cout<<head<<' ';print(tail...);}template<class... T>void fin(const T &... a){print(a...);exit(0);}ll max(int a,ll b){return max((ll)a,b);}ll max(ll a,int b){return max((ll)b,a);}ll min(int a,ll b){return min((ll)a,b);}ll min(ll a,int b){return min((ll)b,a);}//a以上b以下の個数template<typename T>ll RangeOK(ll a,ll b,vector<T> &v){return max(ub(all(v),b)-lb(all(v),a),0);}template <typename T>vector<T> compress(vector<T> &X) {vector<T> vals = X;sort(vals.begin(), vals.end());vals.erase(unique(vals.begin(), vals.end()), vals.end());for (int i = 0; i < (int)X.size(); i++) {X[i] = lower_bound(vals.begin(), vals.end(), X[i]) - vals.begin();}return vals;}//setprecision(20)namespace yakisoba{struct dsu{dsu() : _n(0) {}dsu(int n) : _n(n), parent(n, -1), groupsize(n) {}int merge(int a,int b){if(a<0||a>=_n||b<0||b>=_n) cerr<<"UnionFind Range out:"<<a<<" "<<b<<endl;int x=leader(a);int y=leader(b);if(x==y) return x;groupsize--;if(parent[x]>parent[y]) swap(x,y);parent[x]+=parent[y];parent[y]=x;return x;}bool same(int a,int b){if(a<0||a>=_n||b<0||b>=_n) cerr<<"UnionFind Range out:"<<a<<" "<<b<<endl;if(leader(a)==leader(b)) return true;else return false;}int leader(int a){if(a<0||a>=_n) cerr<<"UnionFind Range out:"<<a<<endl;if(parent[a]<0) return a;parent[a]=leader(parent[a]);return parent[a];}int size(int a){if(a<0||a>=_n) cerr<<"UnionFind Range out:"<<a<<endl;return -parent[leader(a)];}vector<vector<int>> groups(){vector<int> group_size(_n),leader_list(_n);for(int i=0;i<_n;i++){leader_list[i]=leader(i);group_size[leader_list[i]]++;}vector<vector<int>> ans(_n);for(int i=0;i<_n;i++){ans[i].reserve(group_size[i]);}for(int i=0;i<_n;i++){ans[leader_list[i]].push_back(i);}ans.erase(remove_if(ans.begin(),ans.end(),[&](const vector<int>& v){return v.empty();}),ans.end());return ans;}public:int groupsize;private://代表元はそのグループの要素数を符号を反転させて持つ//それ以外は親を持つint _n;vector<int> parent;};}using namespace yakisoba;struct Barrett {using u32=unsigned int;using i64=long long;using u64=unsigned long long;u32 m;u64 im;Barrett():m(),im(){}Barrett(int n):m(n),im(u64(-1)/m+1){}constexpr inline i64 quo(u64 n){u64 x=u64((__uint128_t(n)*im)>>64);u32 r=n-x*m;return m<=r?x-1:x;}constexpr inline i64 rem(u64 n){u64 x=u64((__uint128_t(n)*im)>>64);u32 r=n-x*m;return m<=r?r+m:r;}constexpr inline pair<i64,int> quorem(u64 n){u64 x=u64((__uint128_t(n)*im)>>64);u32 r=n-x*m;if(m<=r)return{x-1,r+m};return{x,r};}constexpr inline i64 pow(u64 n,i64 p){u32 a=rem(n),r=m==1?0:1;while(p){if(p&1)r=rem(u64(r)*a);a=rem(u64(a)*a);p>>=1;}return r;}};struct Amint{int get() const {return x;}inline unsigned int rem(unsigned long long p){return barrett().rem(p);}static inline Barrett &barrett(){static Barrett b;return b;}static inline int &get_mod(){static int modp = 0;return modp;}static void set_mod(int md){assert(0<md&&md<=(1LL<<30)-1);get_mod()=md;barrett()=Barrett(md);}int x;Amint():x(0){}Amint(int64_t y){int z=y%get_mod();if(z<0) z+=get_mod();x=z;}Amint &operator+=(const Amint &p){if((x+=p.x)>=get_mod())x-=get_mod();return *this;}Amint &operator-=(const Amint &p){if((x+=get_mod()-p.x)>=get_mod())x-=get_mod();return *this;}Amint &operator*=(const Amint &p){x=rem((unsigned long long)x*p.x);return *this;}Amint &operator/=(const Amint &p){*this *=p.inv();return *this;}Amint &operator++(){if(++x==get_mod()) x=0;return *this;}Amint &operator--(){if(x--==0) x=get_mod()-1;return *this;}Amint operator-() const{return Amint(-x);}Amint operator+(const Amint &p) const{return Amint(*this)+=p;}Amint operator-(const Amint &p) const{return Amint(*this)-=p;}Amint operator*(const Amint &p) const{return Amint(*this)*= p;}Amint operator/(const Amint &p) const{return Amint(*this)/= p;}bool operator==(const Amint &p) const {return x==p.x;}bool operator!=(const Amint &p) const {return x!=p.x;}bool operator<(const Amint &p) const {return x<p.x;}bool operator>(const Amint &p) const {return x>p.x;}bool operator<=(const Amint &p) const {return x<=p.x;}bool operator>=(const Amint &p) const {return x>=p.x;}Amint pow(int64_t n) const{Amint r(1),m(x);while(n>0){if (n&1) r*=m;m*=m;n>>=1;}return r;}Amint inv() const{int a=x,b=get_mod(),u=1,v=0,t;while(b>0){t=a/b;swap(a-=t*b,b);swap(u-=t*v,v);}return Amint(u);}friend ostream &operator<<(ostream &os,const Amint &p){return os<<p.x;}friend istream &operator>>(istream &is,Amint &a){int64_t t;is>>t;a=Amint(t);return(is);}};template<int modp>struct modint{int get() const{return x;}static constexpr int get_mod(){return modp;}int x;modint():x(0){}modint(int64_t y):x(y>=0?y%modp:(modp-(-y)%modp)%modp){}modint &operator+=(const modint &p){if((x+=p.x)>=modp)x-=modp;return *this;}modint &operator-=(const modint &p){if((x+=modp-p.x)>=modp)x-=modp;return *this;}modint &operator*=(const modint &p){x=(int)(1LL*x*p.x%modp);return *this;}modint &operator/=(const modint &p){*this*=p.inverse();return *this;}modint operator-() const{return modint(-x);}modint operator+(const modint &p) const{return modint(*this)+=p;}modint operator-(const modint &p) const{return modint(*this)-=p;}modint operator*(const modint &p) const{return modint(*this)*= p;}modint operator/(const modint &p) const{return modint(*this)/= p;}modint &operator++(){if(++x==get_mod()) x=0;return *this;}modint &operator--(){if(x--==0) x=get_mod()-1;return *this;}bool operator==(const modint &p) const {return x==p.x;}bool operator!=(const modint &p) const {return x!=p.x;}bool operator<(const modint &p) const {return x<p.x;}bool operator>(const modint &p) const {return x>p.x;}bool operator<=(const modint &p) const {return x<=p.x;}bool operator>=(const modint &p) const {return x>=p.x;}modint pow(int64_t n) const{modint r(1),m(x);while(n>0){if (n&1) r*=m;m*=m;n>>=1;}return r;}modint inv()const{int a=x,b=get_mod(),u=1,v=0,t;while(b>0){t=a/b;swap(a-=t*b,b);swap(u-=t*v,v);}return modint(u);}friend ostream &operator<<(ostream &os,const modint &p){return os<<p.x;}friend istream &operator>>(istream &is,modint &a){int64_t t;is>>t;a=modint(t);return(is);}};#define mint Amint//#define MOD Amint::set_mod(1000000007);#define MOD Amint::set_mod(998244353);//#define mint modint//modが不変の場合は上3つを利用//modが10^9+7と998244353の時は, MOD; を最初に実行する//modが可変の場合は1番下を利用 mint<998244353>のように宣言long long pow(long long n,long long k){long long ans=1;while(k){if(k&1) ans*=n;n*=n;k>>=1;}return ans;}//modをとらない場合の累乗 modをとる場合はa.pow(1000)のようにmodintを使うmint comb_naive(mint n,mint k){if(k<0||n<k) return 0;k=min(k,n-k);mint a=1,b=1;for(mint i=1;i<=k;++i){a*=i;b*=n-i+1;}return a.inv()*b;}#define k_max 1000000vector<mint> fac(k_max);vector<mint> inv_fac(k_max);void set_comb(){MOD;fac[0]=1;for(mint i=1;i<k_max;++i){fac[i.get()]=fac[i.get()-1]*i;}inv_fac[k_max-1]=fac[k_max-1].inv();inv_fac[0]=1;for(mint i=k_max-2;i>=1;--i){inv_fac[i.get()]=inv_fac[i.get()+1]*(i+1);}}mint comb(mint n,mint k){if(k<0||n<k) return 0;return fac[n.get()]*inv_fac[k.get()]*inv_fac[(n-k).get()];}int main(){set_comb();LL(n);vector<mint> v(n);scan(v);mint ans=0;rep(i,n){ans+=v[i]*(mint(2).pow(n-i-1)-1);ans-=v[i]*(mint(2).pow(i)-1);}fin(ans);}