結果
問題 | No.1067 #いろいろな色 / Red and Blue and more various colors (Middle) |
ユーザー |
![]() |
提出日時 | 2021-03-20 00:18:00 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 98 ms / 2,000 ms |
コード長 | 3,204 bytes |
コンパイル時間 | 3,650 ms |
コンパイル使用メモリ | 240,232 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-11-19 03:23:49 |
合計ジャッジ時間 | 5,280 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 25 |
ソースコード
#ifndef ONLINE_JUDGE #define _GLIBCXX_DEBUG #endif #include<bits/stdc++.h> #include<atcoder/all> using namespace std; using namespace atcoder; #define rep(i, n) for (ll i = 0; i < (ll)(n); i++) #define bit(n,k) (((ll)n>>(ll)k)&1) /*nのk bit目*/ #define pb push_back #define pf push_front #define fi first #define se second #define eb emplace_back #define endl '\n' #define SZ(x) ((ll)(x).size()) #define all(x) (x).begin(),(x).end() #define rall(x) (x).rbegin(),(x).rend() #define debug(v) cout<<#v<<":";for(auto x:v){cout<<x<<' ';}cout<<endl; #define PI 3.14159265359 const double eps = 1e-12; const long long INF= (long long)1e18+20; typedef double D; // 座標値の型。doubleかlong doubleを想定 typedef complex<D> Point; // Point typedef long long ll; typedef vector<ll> vl; typedef vector<vl>vvl; typedef vector<vvl>vvvl; typedef vector<vvvl>vvvvl; typedef vector<vvvvl>vvvvvl; typedef pair<ll,ll> P; typedef tuple<ll,ll,ll> T; template<class T> using minpq=priority_queue<T,vector<T>,greater<T>>; // const ll MOD=1000000007LL; const ll MOD=998244353LL; const ll mod=MOD; string abc="abcdefghijklmnopqrstuvwxyz"; string ABC="ABCDEFGHIJKLMNOPQRSTUVWXYZ"; vl dx={0,0,1,-1,1,1,-1,-1}; vl dy={1,-1,0,0,-1,1,-1,1}; template<class T> vector<T> make_vec(size_t a) { return vector<T>(a); } template<class T, class... Ts> auto make_vec(size_t a, Ts... ts) { return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...)); } template<class T>bool chmax(T &a,const T &b){if(a<b){a=b;return true;}return false;} template<class T>bool chmin(T &a,const T &b){if(b<a){a=b;return true;}return false;} using mint=modint998244353; ll modpow(ll a, ll n,ll mod=MOD) { ll res = 1; while (n > 0) { if (n & 1) res = res * a % mod; a = a * a % mod; n >>= 1; } return res; } int main(){ ios::sync_with_stdio(false); std::cin.tie(nullptr); cout << fixed << setprecision(12); /*--------------------------------*/ int n,q;cin>>n>>q; vl a(n); rep(i,n)cin>>a[i]; sort(all(a)); vl l(q),r(q),p(q); rep(i,q)cin>>l[i]>>r[i]>>p[i]; vvl ans(q); //(値,個数) //累積積 vector<mint> pro(n+1); pro[0]=1; for(int i=0;i<n;i++)pro[i+1]=pro[i]*a[i]; auto dp=make_vec<mint>(2,n+1); dp[n%2][0]=1; for(int i=n-1;i>=0;i--){ for(int j=n;j>=0;j--){ dp[i%2][j]=0; if(j)dp[i%2][j]+=dp[(i+1)%2][j-1]; dp[i%2][j]+=dp[(i+1)%2][j]*(a[i]-1); } if(i==0||a[i]!=a[i-1]){ //終端 //ここで更新 ll big,small; if(i==0){ big=a[i]; small=1; } else{ big=a[i]; small=a[i-1]+1; } rep(j,q){ if(max(l[j],small)<=min(r[j],big)){ ll cnt=min(r[j],big)-max(l[j],small)+1; mint value=pro[i]*dp[i%2][p[j]]; if(cnt%2)ans[j].pb(value.val()); } } } } for(ll i=0;i<q;i++){ ll res=0; for(auto x:ans[i])res^=x; cout<<res<<endl; } }