結果
問題 | No.1067 #いろいろな色 / Red and Blue and more various colors (Middle) |
ユーザー |
![]() |
提出日時 | 2020-05-29 23:18:59 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
CE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 3,869 bytes |
コンパイル時間 | 734 ms |
コンパイル使用メモリ | 85,752 KB |
最終ジャッジ日時 | 2025-03-21 07:24:36 |
合計ジャッジ時間 | 1,870 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。(リジャッジ後のコンパイルエラーは公開されます)
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
コンパイルメッセージ
main.cpp:65:16: error: ‘std::uint_fast64_t’ has not been declared 65 | template <std::uint_fast64_t Modulus> class modint { | ^~~~~~~~~~~~~ main.cpp:66:20: error: ‘uint_fast64_t’ in namespace ‘std’ does not name a type 66 | using u64 = std::uint_fast64_t; | ^~~~~~~~~~~~~ main.cpp:15:1: note: ‘std::uint_fast64_t’ is defined in header ‘<cstdint>’; did you forget to ‘#include <cstdint>’? 14 | #include <assert.h> +++ |+#include <cstdint> 15 | using namespace std; main.cpp:69:3: error: ‘u64’ does not name a type 69 | u64 a; | ^~~ main.cpp:71:26: error: ‘u64’ does not name a type 71 | constexpr modint(const u64 x = 0) noexcept : a(x % Modulus) {} | ^~~ main.cpp:72:13: error: ‘u64’ does not name a type 72 | constexpr u64 &value() noexcept { return a; } | ^~~ main.cpp:73:19: error: ‘u64’ does not name a type 73 | constexpr const u64 &value() const noexcept { return a; } | ^~~ main.cpp:119:1: error: ‘mint’ does not name a type; did you mean ‘uint’? 119 | mint dp[2][6005]; | ^~~~ | uint main.cpp: In function ‘int main()’: main.cpp:141:24: error: ‘mint’ was not declared in this scope; did you mean ‘uint’? 141 | vector<pair<ll,mint>> v; | ^~~~ | uint main.cpp:141:24: error: template argument 2 is invalid main.cpp:141:28: error: template argument 1 is invalid 141 | vector<pair<ll,mint>> v; | ^~ main.cpp:141:28: error: template argument 2 is invalid main.cpp:142:9: error: ‘dp’ was not declared in this scope; did you mean ‘dy’? 142 | dp[0][0] = 1; | ^~ | dy main.cpp:143:13: error: expected ‘;’ before ‘acc’ 143 | mint acc = 1; | ^~~~ | ; main
ソースコード
#include <iostream> #include <string> #include <cstdlib> #include <cmath> #include <vector> #include <map> #include <set> #include <algorithm> #include <ctime> #include <queue> #include <stack> #include <functional> #include <bitset> #include <assert.h> using namespace std; typedef long long ll; typedef vector<ll> vl; typedef vector<vl> vvl; typedef vector<char> vc; typedef vector<string> vs; typedef vector<bool> vb; typedef vector<double> vd; typedef pair<ll,ll> P; typedef vector<P> vpl; typedef tuple<ll,ll,ll> tapu; #define rep(i,n) for(ll i=0; i<(n); i++) #define REP(i,a,b) for(int i=(a); i<(b); i++) #define all(x) (x).begin(), (x).end() #define rall(x) (x).rbegin(), (x).rend() const int inf = 1<<30; const ll linf = 1LL<<62; const int MAX = 510000; ll dy[8] = {0,1,0,-1,1,-1,1,-1}; ll dx[8] = {1,0,-1,0,1,-1,-1,1}; const double pi = acos(-1); const double eps = 1e-7; template<typename T1,typename T2> inline bool chmin(T1 &a,T2 b){ if(a>b){ a = b; return true; } else return false; } template<typename T1,typename T2> inline bool chmax(T1 &a,T2 b){ if(a<b){ a = b; return true; } else return false; } template<typename T> inline void print(T &a){ rep(i,a.size()) cout << a[i] << " "; cout << "\n"; } template<typename T1,typename T2> inline void print2(T1 a, T2 b){cout << a << " " << b << "\n";} template<typename T1,typename T2,typename T3> inline void print3(T1 a, T2 b, T3 c){ cout << a << " " << b << " " << c << "\n"; } //const int mod = 1e9 + 7; const int mod = 998244353; double dist(ll a, ll b, ll c, ll d){ double res = sqrt((a-c)*(a-c) + (b-d)*(b-d)); return res; } template <std::uint_fast64_t Modulus> class modint { using u64 = std::uint_fast64_t; public: u64 a; constexpr modint(const u64 x = 0) noexcept : a(x % Modulus) {} constexpr u64 &value() noexcept { return a; } constexpr const u64 &value() const noexcept { return a; } constexpr modint operator+(const modint rhs) const noexcept { return modint(*this) += rhs; } constexpr modint operator-(const modint rhs) const noexcept { return modint(*this) -= rhs; } constexpr modint operator*(const modint rhs) const noexcept { return modint(*this) *= rhs; } constexpr modint operator/(const modint rhs) const noexcept { return modint(*this) /= rhs; } constexpr modint &operator+=(const modint rhs) noexcept { a += rhs.a; if (a >= Modulus) { a -= Modulus; } return *this; } constexpr modint &operator-=(const modint rhs) noexcept { if (a < rhs.a) { a += Modulus; } a -= rhs.a; return *this; } constexpr modint &operator*=(const modint rhs) noexcept { a = a * rhs.a % Modulus; return *this; } constexpr modint &operator/=(modint rhs) noexcept { u64 exp = Modulus - 2; while (exp) { if (exp % 2) { *this *= rhs; } rhs *= rhs; exp /= 2; } return *this; } }; using mint = modint<mod>; mint dp[2][6005]; struct dat{ ll m,p,id; bool operator< (const dat &d) const { return m < d.m; } }; int main(){ ll n,q; cin >> n >> q; vector<dat> query; vl a(n); rep(i,n) cin >> a[i]; rep(i,q){ ll l,r,p; cin >> l >> r >> p; for(ll j=l; j<=r; j++){ query.push_back({j,p,i}); } } ll Q = query.size(); sort(rall(query)); vl ans(q,0); sort(rall(a)); vector<pair<ll,mint>> v; dp[0][0] = 1; mint acc = 1; ll id = 0; rep(i,n) acc *= a[i]; rep(i,n){ rep(j,n+1){ dp[1][j] += dp[0][j] * (a[i] - 1); dp[1][j+1] += dp[0][j]; } while(id < Q && query[id].m > a[i]){ mint tmp = dp[0][query[id].p] * acc; ll tmp2 = tmp.value(); ans[query[id].id] ^= tmp2; //print2(query[id].m, dp[0][query[id].p].value()); id++; } swap(dp[0], dp[1]); rep(j,n+1) dp[1][j] = 0; acc /= a[i]; } while(id < Q){ ans[query[id].id] ^= dp[0][query[id].p].value(); //print2(query[id].m, dp[0][query[id].p].value()); id++; } rep(i,q){ cout << ans[i] % mod << "\n"; } }