結果
| 問題 | No.8112 区間和係数多項式？ |
| ユーザー |
👑  Nachia
|
| 提出日時 | 2024-04-01 22:46:59 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 939 ms / 6,000 ms |
| コード長 | 6,995 bytes |
| コンパイル時間 | 1,225 ms |
| コンパイル使用メモリ | 105,672 KB |
| 最終ジャッジ日時 | 2025-02-20 19:21:37 |
|
ジャッジサーバーID （参考情報） |
judge3 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 29 |
ソースコード
#ifdef NACHIA#define _GLIBCXX_DEBUG#else#define NDEBUG#endif#include <iostream>#include <string>#include <vector>#include <algorithm>#include <utility>#include <queue>#include <array>#include <cmath>#include <atcoder/modint>#include <cstdio>#include <cctype>#include <cstdint>namespace nachia{struct CInStream{private:static const unsigned int INPUT_BUF_SIZE = 1 << 17;unsigned int p = INPUT_BUF_SIZE;static char Q[INPUT_BUF_SIZE];public:using MyType = CInStream;char seekChar(){if(p == INPUT_BUF_SIZE){size_t len = fread(Q, 1, INPUT_BUF_SIZE, stdin);if(len != INPUT_BUF_SIZE) Q[len] = '\0';p = 0;}return Q[p];}void skipSpace(){ while(isspace(seekChar())) p++; }private:template<class T, int sp = 1>T nextUInt(){if constexpr (sp) skipSpace();T buf = 0;while(true){char tmp = seekChar();if('9' < tmp || tmp < '0') break;buf = buf * 10 + (tmp - '0');p++;}return buf;}public:uint32_t nextU32(){ return nextUInt<uint32_t>(); }int32_t nextI32(){skipSpace();if(seekChar() == '-'){p++; return (int32_t)(-nextUInt<uint32_t, 0>());}return (int32_t)nextUInt<uint32_t, 0>();}uint64_t nextU64(){ return nextUInt<uint64_t>();}int64_t nextI64(){skipSpace();if(seekChar() == '-'){p++; return (int64_t)(-nextUInt<int64_t, 0>());}return (int64_t)nextUInt<int64_t, 0>();}template<class T>T nextInt(){skipSpace();if(seekChar() == '-'){p++;return - nextUInt<T, 0>();}return nextUInt<T, 0>();}char nextChar(){ skipSpace(); char buf = seekChar(); p++; return buf; }std::string nextToken(){skipSpace();std::string buf;while(true){char ch = seekChar();if(isspace(ch) || ch == '\0') break;buf.push_back(ch);p++;}return buf;}MyType& operator>>(unsigned int& dest){ dest = nextU32(); return *this; }MyType& operator>>(int& dest){ dest = nextI32(); return *this; }MyType& operator>>(unsigned long& dest){ dest = nextU64(); return *this; }MyType& operator>>(long& dest){ dest = nextI64(); return *this; }MyType& operator>>(unsigned long long& dest){ dest = nextU64(); return *this; }MyType& operator>>(long long& dest){ dest = nextI64(); return *this; }MyType& operator>>(std::string& dest){ dest = nextToken(); return *this; }MyType& operator>>(char& dest){ dest = nextChar(); return *this; }} cin;struct FastOutputTable{char LZ[1000][4] = {};char NLZ[1000][4] = {};constexpr FastOutputTable(){using u32 = uint_fast32_t;for(u32 d=0; d<1000; d++){LZ[d][0] = ('0' + d / 100 % 10);LZ[d][1] = ('0' + d / 10 % 10);LZ[d][2] = ('0' + d / 1 % 10);LZ[d][3] = '\0';}for(u32 d=0; d<1000; d++){u32 i = 0;if(d >= 100) NLZ[d][i++] = ('0' + d / 100 % 10);if(d >= 10) NLZ[d][i++] = ('0' + d / 10 % 10);if(d >= 1) NLZ[d][i++] = ('0' + d / 1 % 10);NLZ[d][i++] = '\0';}}};struct COutStream{private:using u32 = uint32_t;using u64 = uint64_t;using MyType = COutStream;static const u32 OUTPUT_BUF_SIZE = 1 << 17;static char Q[OUTPUT_BUF_SIZE];static constexpr FastOutputTable TB = FastOutputTable();u32 p = 0;static constexpr u32 P10(u32 d){ return d ? P10(d-1)*10 : 1; }static constexpr u64 P10L(u32 d){ return d ? P10L(d-1)*10 : 1; }template<class T, class U> static void Fil(T& m, U& l, U x){ m = l/x; l -= m*x; }public:void next_dig9(u32 x){u32 y;Fil(y, x, P10(6));nextCstr(TB.LZ[y]);Fil(y, x, P10(3));nextCstr(TB.LZ[y]); nextCstr(TB.LZ[x]);}void nextChar(char c){Q[p++] = c;if(p == OUTPUT_BUF_SIZE){ fwrite(Q, p, 1, stdout); p = 0; }}void nextEoln(){ nextChar('\n'); }void nextCstr(const char* s){ while(*s) nextChar(*(s++)); }void nextU32(uint32_t x){u32 y = 0;if(x >= P10(9)){Fil(y, x, P10(9));nextCstr(TB.NLZ[y]); next_dig9(x);}else if(x >= P10(6)){Fil(y, x, P10(6));nextCstr(TB.NLZ[y]);Fil(y, x, P10(3));nextCstr(TB.LZ[y]); nextCstr(TB.LZ[x]);}else if(x >= P10(3)){Fil(y, x, P10(3));nextCstr(TB.NLZ[y]); nextCstr(TB.LZ[x]);}else if(x >= 1) nextCstr(TB.NLZ[x]);else nextChar('0');}void nextI32(int32_t x){if(x >= 0) nextU32(x);else{ nextChar('-'); nextU32((u32)-x); }}void nextU64(uint64_t x){u32 y = 0;if(x >= P10L(18)){Fil(y, x, P10L(18));nextU32(y);Fil(y, x, P10L(9));next_dig9(y); next_dig9(x);}else if(x >= P10L(9)){Fil(y, x, P10L(9));nextU32(y); next_dig9(x);}else nextU32(x);}void nextI64(int64_t x){if(x >= 0) nextU64(x);else{ nextChar('-'); nextU64((u64)-x); }}template<class T>void nextInt(T x){if(x < 0){ nextChar('-'); x = -x; }if(!(0 < x)){ nextChar('0'); return; }std::string buf;while(0 < x){buf.push_back('0' + (int)(x % 10));x /= 10;}for(int i=(int)buf.size()-1; i>=0; i--){nextChar(buf[i]);}}void writeToFile(bool flush = false){fwrite(Q, p, 1, stdout);if(flush) fflush(stdout);p = 0;}COutStream(){ Q[0] = 0; }~COutStream(){ writeToFile(); }MyType& operator<<(unsigned int tg){ nextU32(tg); return *this; }MyType& operator<<(unsigned long tg){ nextU64(tg); return *this; }MyType& operator<<(unsigned long long tg){ nextU64(tg); return *this; }MyType& operator<<(int tg){ nextI32(tg); return *this; }MyType& operator<<(long tg){ nextI64(tg); return *this; }MyType& operator<<(long long tg){ nextI64(tg); return *this; }MyType& operator<<(const std::string& tg){ nextCstr(tg.c_str()); return *this; }MyType& operator<<(const char* tg){ nextCstr(tg); return *this; }MyType& operator<<(char tg){ nextChar(tg); return *this; }} cout;char CInStream::Q[INPUT_BUF_SIZE];char COutStream::Q[OUTPUT_BUF_SIZE];} // namespace nachiausing i64 = long long;using u64 = unsigned long long;#define rep(i,n) for(int i=0; i<int(n); i++)#define repr(i,n) for(int i=int(n)-1; i>=0; i--)using namespace std;int main(){using nachia::cin;using nachia::cout;using Modint = atcoder::modint;int N, B, Q; cin >> N >> B >> Q;Modint::set_mod(B);vector<Modint> A(N);i64 C[6] = {}, D[6] = {};rep(i,5) cin >> C[i+1] >> D[i+1];vector<Modint> Araw(N);Araw[0] = C[1];rep(i,N-1) Araw[i+1] = Araw[i] * D[1];auto addA = [&](int i, Modint a){if(i == 0){ A[0] += a; return; }for(int p=i; p<N; p+=p&-p) A[p] += a;};C[2] %= int(N); D[2] %= int(N);C[3] %= int(N); D[3] %= int(N);rep(i,N) addA(i, Araw[i]);rep(qi,Q){int i = C[2]; C[2] = C[2] * D[2] % int(N);int j = C[3]; C[3] = C[3] * D[3] % int(N);Modint x = C[4]; C[4] = (x * D[4]).val();Modint y = C[5]; C[5] = (y * D[5]).val();x -= Araw[i]; Araw[i] += x; addA(i,x);Modint yy = 1;Modint ans = 0;while(j){ans += yy * A[j];yy *= y;j -= j&-j;}ans += yy * A[0];cout << ans.val() << '\n';}return 0;}