結果
問題 | No.2592 おでぶなおばけさん 2 |
ユーザー |
![]() |
提出日時 | 2023-12-19 04:31:57 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 7,891 bytes |
コンパイル時間 | 10,815 ms |
コンパイル使用メモリ | 536,936 KB |
実行使用メモリ | 6,948 KB |
最終ジャッジ日時 | 2024-09-27 09:10:30 |
合計ジャッジ時間 | 19,709 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 79 WA * 4 |
ソースコード
/*このコード、と~おれ!Be accepted!∧_∧(。・ω・。)つ━☆・*。⊂ ノ ・゜+.しーJ °。+ *´¨).· ´¸.·*´¨) ¸.·*¨)(¸.·´ (¸.·'* ☆*/#include <cstdio>#include <algorithm>#include <string>#include <cmath>#include <cstring>#include <vector>#include <numeric>#include <iostream>#include <random>#include <map>#include <unordered_map>#include <queue>#include <regex>#include <functional>#include <complex>#include <list>#include <cassert>#include <iomanip>#include <set>#include <stack>#include <bitset>#include <array>#include <chrono>#include <unordered_set>//#pragma GCC target("arch=skylake-avx512")//#pragma GCC target("avx2")//#pragma GCC optimize("O3")#pragma GCC optimize("Ofast")//#pragma GCC target("sse4")#pragma GCC optimize("unroll-loops")//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")#define repeat(i, n, m) for(int i = n; i < (m); ++i)#define rep(i, n) for(int i = 0; i < (n); ++i)#define printynl(a) printf(a ? "yes\n" : "no\n")#define printyn(a) printf(a ? "Yes\n" : "No\n")#define printYN(a) printf(a ? "YES\n" : "NO\n")#define printim(a) printf(a ? "possible\n" : "imposible\n")#define printdb(a) printf("%.50lf\n", a)#define printLdb(a) printf("%.50Lf\n", a)#define printdbd(a) printf("%.16lf\n", a)#define prints(s) printf("%s\n", s.c_str())#define all(x) (x).begin(), (x).end()#define deg_to_rad(deg) (((deg)/360.0L)*2.0L*PI)#define rad_to_deg(rad) (((rad)/2.0L/PI)*360.0L)#define Please return#define AC 0#define manhattan_dist(a, b, c, d) (abs(a - c) + abs(b - d))using ll = long long;using ull = unsigned long long;constexpr int INF = 1073741823;constexpr int MINF = -1073741823;constexpr ll LINF = ll(4661686018427387903);constexpr ll MOD = 1e9 + 7;constexpr ll mod = 998244353;constexpr long double eps = 1e-14;const long double PI = acosl(-1.0L);using namespace std;void scans(string& str) {char c;str = "";scanf("%c", &c);if (c == '\n')scanf("%c", &c);while (c != '\n' && c != -1 && c != ' ') {str += c;scanf("%c", &c);}}void scanc(char& str) {char c;scanf("%c", &c);if (c == -1)return;while (c == '\n') {scanf("%c", &c);}str = c;}double acot(double x) {return PI / 2 - atan(x);}ll LSB(ll n) { return (n & (-n)); }template<typename T>inline T chmin(T& a, const T& b) {if (a > b)a = b;return a;}template<typename T>inline T chmax(T& a, const T& b) {if (a < b)a = b;return a;}//cpp_int#if __has_include(<boost/multiprecision/cpp_int.hpp>)#include <boost/multiprecision/cpp_int.hpp>#include <boost/multiprecision/cpp_dec_float.hpp>using namespace boost::multiprecision;#elseusing cpp_int = ll;#endif//atcoder library#if __has_include(<atcoder/all>)#include <atcoder/all>//using namespace atcoder;#endif/*random_device seed_gen;mt19937 engine(seed_gen());uniform_int_distribution dist(1, 100);*//*----------------------------------------------------------------------------------*/// montgomery modint (MOD < 2^62, MOD is odd)struct MontgomeryModInt64 {using mint = MontgomeryModInt64;using u64 = uint64_t;using u128 = __uint128_t;// static menberstatic u64 MOD;static u64 INV_MOD; // INV_MOD * MOD ≡ 1 (mod 2^64)static u64 T128; // 2^128 (mod MOD)// inner valueu64 val;// constructorMontgomeryModInt64() : val(0) { }MontgomeryModInt64(long long v) : val(reduce((u128(v) + MOD)* T128)) { }u64 get() const {u64 res = reduce(val);return res >= MOD ? res - MOD : res;}// mod getter and setterstatic u64 get_mod() { return MOD; }static void set_mod(u64 mod) {assert(mod < (1LL << 62));assert((mod & 1));MOD = mod;T128 = -u128(mod) % mod;INV_MOD = get_inv_mod();}static u64 get_inv_mod() {u64 res = MOD;for (int i = 0; i < 5; ++i) res *= 2 - MOD * res;return res;}static u64 reduce(const u128& v) {return (v + u128(u64(v) * u64(-INV_MOD)) * MOD) >> 64;}// arithmetic operatorsmint operator - () const { return mint() - mint(*this); }mint operator + (const mint& r) const { return mint(*this) += r; }mint operator - (const mint& r) const { return mint(*this) -= r; }mint operator * (const mint& r) const { return mint(*this) *= r; }mint operator / (const mint& r) const { return mint(*this) /= r; }mint& operator += (const mint& r) {if ((val += r.val) >= 2 * MOD) val -= 2 * MOD;return *this;}mint& operator -= (const mint& r) {if ((val += 2 * MOD - r.val) >= 2 * MOD) val -= 2 * MOD;return *this;}mint& operator *= (const mint& r) {val = reduce(u128(val) * r.val);return *this;}mint& operator /= (const mint& r) {*this *= r.inv();return *this;}mint inv() const { return pow(MOD - 2); }mint pow(u128 n) const {mint res(1), mul(*this);while (n > 0) {if (n & 1) res *= mul;mul *= mul;n >>= 1;}return res;}// other operatorsbool operator == (const mint& r) const {return (val >= MOD ? val - MOD : val) == (r.val >= MOD ? r.val - MOD : r.val);}bool operator != (const mint& r) const {return (val >= MOD ? val - MOD : val) != (r.val >= MOD ? r.val - MOD : r.val);}friend istream& operator >> (istream& is, mint& x) {long long t;is >> t;x = mint(t);return is;}friend ostream& operator << (ostream& os, const mint& x) {return os << x.get();}friend mint modpow(const mint& r, long long n) {return r.pow(n);}friend mint modinv(const mint& r) {return r.inv();}};typename MontgomeryModInt64::u64MontgomeryModInt64::MOD, MontgomeryModInt64::INV_MOD, MontgomeryModInt64::T128;// Miller-Rabinbool MillerRabin(long long N, vector<long long> A) {using mint = MontgomeryModInt64;mint::set_mod(N);long long s = 0, d = N - 1;while (d % 2 == 0) {++s;d >>= 1;}for (auto a : A) {if (N <= a) return true;mint x = mint(a).pow(d);if (x != 1) {long long t;for (t = 0; t < s; ++t) {if (x == N - 1) break;x *= x;}if (t == s) return false;}}return true;}bool is_prime(long long N) {if (N <= 1) return false;else if (N == 2) return true;else if (N % 2 == 0) return false;else if (N < 4759123141LL)return MillerRabin(N, { 2, 7, 61 });elsereturn MillerRabin(N, { 2, 325, 9375, 28178, 450775, 9780504, 1795265022 });}//https://drken1215.hatenablog.com/entry/2023/05/23/233000random_device seed_gen;mt19937 engine(seed_gen());uniform_int_distribution<ll> dist(1e9, 3e9);int main() {int n, q;ll k;scanf("%d%d", &n, &q);cin >> k;vector<ll> a(n);rep(i, n)cin >> a[i];vector<ll> rnd(1);rep(i, 1) {ll x = dist(engine);while (not is_prime(x))x = dist(engine);rnd[i] = x;}vector<vector<ll>> cs;rep(i, 1) {ll kk = rnd[i];ll x = 1;x %= kk;vector<ll> b(n);rep(j, n) {b[j] = (a[j] % kk) * x;b[j] %= kk;x *= k;x %= kk;}vector<ll> c(n + 1);rep(j, n) {c[j + 1] = c[j] + b[j];c[j + 1] %= kk;}cs.push_back(c);}rep(i, q) {int l, r;scanf("%d%d", &l, &r);--l;int ans = 0;rep(j, 1) {ll x = cs[j][r] - cs[j][l];x += rnd[j];x %= rnd[j];if (x != 0) {ans = 1;break;}}printyn(ans);}Please AC;}