QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #386857 | #8543. Periodic Sequence | ucup-team087# | AC ✓ | 1094ms | 5604kb | C++14 | 10.4kb | 2024-04-11 20:46:09 | 2024-04-11 20:46:09 |
Judging History
answer
#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
using Int = long long;
template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }
#define COLOR(s) ("\x1b[" s "m")
////////////////////////////////////////////////////////////////////////////////
// Barrett
struct ModInt {
static unsigned M;
static unsigned long long NEG_INV_M;
static void setM(unsigned m) { M = m; NEG_INV_M = -1ULL / M; }
unsigned x;
ModInt() : x(0U) {}
ModInt(unsigned x_) : x(x_ % M) {}
ModInt(unsigned long long x_) : x(x_ % M) {}
ModInt(int x_) : x(((x_ %= static_cast<int>(M)) < 0) ? (x_ + static_cast<int>(M)) : x_) {}
ModInt(long long x_) : x(((x_ %= static_cast<long long>(M)) < 0) ? (x_ + static_cast<long long>(M)) : x_) {}
ModInt &operator+=(const ModInt &a) { x = ((x += a.x) >= M) ? (x - M) : x; return *this; }
ModInt &operator-=(const ModInt &a) { x = ((x -= a.x) >= M) ? (x + M) : x; return *this; }
ModInt &operator*=(const ModInt &a) {
const unsigned long long y = static_cast<unsigned long long>(x) * a.x;
const unsigned long long q = static_cast<unsigned long long>((static_cast<unsigned __int128>(NEG_INV_M) * y) >> 64);
const unsigned long long r = y - M * q;
x = r - M * (r >= M);
return *this;
}
ModInt &operator/=(const ModInt &a) { return (*this *= a.inv()); }
ModInt pow(long long e) const {
if (e < 0) return inv().pow(-e);
ModInt a = *this, b = 1U; for (; e; e >>= 1) { if (e & 1) b *= a; a *= a; } return b;
}
ModInt inv() const {
unsigned a = M, b = x; int y = 0, z = 1;
for (; b; ) { const unsigned q = a / b; const unsigned c = a - q * b; a = b; b = c; const int w = y - static_cast<int>(q) * z; y = z; z = w; }
assert(a == 1U); return ModInt(y);
}
ModInt operator+() const { return *this; }
ModInt operator-() const { ModInt a; a.x = x ? (M - x) : 0U; return a; }
ModInt operator+(const ModInt &a) const { return (ModInt(*this) += a); }
ModInt operator-(const ModInt &a) const { return (ModInt(*this) -= a); }
ModInt operator*(const ModInt &a) const { return (ModInt(*this) *= a); }
ModInt operator/(const ModInt &a) const { return (ModInt(*this) /= a); }
template <class T> friend ModInt operator+(T a, const ModInt &b) { return (ModInt(a) += b); }
template <class T> friend ModInt operator-(T a, const ModInt &b) { return (ModInt(a) -= b); }
template <class T> friend ModInt operator*(T a, const ModInt &b) { return (ModInt(a) *= b); }
template <class T> friend ModInt operator/(T a, const ModInt &b) { return (ModInt(a) /= b); }
explicit operator bool() const { return x; }
bool operator==(const ModInt &a) const { return (x == a.x); }
bool operator!=(const ModInt &a) const { return (x != a.x); }
friend std::ostream &operator<<(std::ostream &os, const ModInt &a) { return os << a.x; }
};
unsigned ModInt::M;
unsigned long long ModInt::NEG_INV_M;
// !!!Use ModInt::setM!!!
////////////////////////////////////////////////////////////////////////////////
using Mint = ModInt;
namespace exper {
void run() {
for (int m = 1; m <= 26; ++m) {
const int lim = m + 20;
vector<vector<string>> dp(lim);
string ini(m, '?');
for (int x = 0; x < m; ++x) ini[x] = 'a' + min(x, 1);
// for (int x = 0; x < m; ++x) ini[x] = 'a' + x;
dp[m] = {ini};
for (int n = m + 1; n < lim; ++n) {
for (int nn = m; nn < n; ++nn) {
for (const string &s : dp[nn]) {
string t(n, '?');
for (int x = 0; x < n; ++x) t[x] = s[x % nn];
dp[n].push_back(t);
}
}
sort(dp[n].begin(), dp[n].end());
dp[n].erase(unique(dp[n].begin(), dp[n].end()), dp[n].end());
}
cerr << m << ":";
for (int n = m; n < lim; ++n) cerr << " " << dp[n].size();
cerr << endl;
}
}
} // exper
/*
1: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
2: 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765
3: 1 1 2 4 7 13 24 44 81 149 274 504 927 1705 3136 5768 10609 19513 35890 66012
4: 1 1 2 4 8 15 29 56 108 208 401 773 1490 2872 5536 10671 20569 39648 76424 147312
5: 1 1 2 4 8 16 31 61 120 236 464 912 1793 3525 6930 13624 26784 52656 103519 203513
6: 1 1 2 4 8 16 32 63 125 248 492 976 1936 3840 7617 15109 29970 59448 117920 233904
7: 1 1 2 4 8 16 32 64 127 253 504 1004 2000 3984 7936 15808 31489 62725 124946 248888
8: 1 1 2 4 8 16 32 64 128 255 509 1016 2028 4048 8080 16128 32192 64256 128257 256005
9: 1 1 2 4 8 16 32 64 128 256 511 1021 2040 4076 8144 16272 32512 64960 129792 259328
10: 1 1 2 4 8 16 32 64 128 256 512 1023 2045 4088 8172 16336 32656 65280 130496 260864
11: 1 1 2 4 8 16 32 64 128 256 512 1024 2047 4093 8184 16364 32720 65424 130816 261568
12: 1 1 2 4 8 16 32 64 128 256 512 1024 2048 4095 8189 16376 32748 65488 130960 261888
13: 1 1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8191 16381 32760 65516 131024 262032
14: 1 1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16383 32765 65528 131052 262096
15: 1 1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 32767 65533 131064 262124
16: 1 1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768 65535 131069 262136
17: 1 1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768 65536 131071 262141
18: 1 1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768 65536 131072 262143
19: 1 1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768 65536 131072 262144
20: 1 1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768 65536 131072 262144
21: 1 1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768 65536 131072 262144
22: 1 1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768 65536 131072 262144
23: 1 1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768 65536 131072 262144
24: 1 1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768 65536 131072 262144
25: 1 1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768 65536 131072 262144
26: 1 1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768 65536 131072 262144
1: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
2: 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765
3: 1 1 2 4 7 13 24 44 81 149 274 504 927 1705 3136 5768 10609 19513 35890 66012
4: 1 1 2 4 8 15 29 56 108 208 401 773 1490 2872 5536 10671 20569 39648 76424 147312
5: 1 1 2 4 8 16 31 61 120 236 464 912 1793 3525 6930 13624 26784 52656 103519 203513
6: 1 1 2 4 8 16 32 63 125 248 492 976 1936 3840 7617 15109 29970 59448 117920 233904
7: 1 1 2 4 8 16 32 64 127 253 504 1004 2000 3984 7936 15808 31489 62725 124946 248888
8: 1 1 2 4 8 16 32 64 128 255 509 1016 2028 4048 8080 16128 32192 64256 128257 256005
9: 1 1 2 4 8 16 32 64 128 256 511 1021 2040 4076 8144 16272 32512 64960 129792 259328
10: 1 1 2 4 8 16 32 64 128 256 512 1023 2045 4088 8172 16336 32656 65280 130496 260864
11: 1 1 2 4 8 16 32 64 128 256 512 1024 2047 4093 8184 16364 32720 65424 130816 261568
12: 1 1 2 4 8 16 32 64 128 256 512 1024 2048 4095 8189 16376 32748 65488 130960 261888
13: 1 1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8191 16381 32760 65516 131024 262032
14: 1 1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16383 32765 65528 131052 262096
15: 1 1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 32767 65533 131064 262124
16: 1 1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768 65535 131069 262136
17: 1 1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768 65536 131071 262141
18: 1 1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768 65536 131072 262143
19: 1 1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768 65536 131072 262144
20: 1 1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768 65536 131072 262144
21: 1 1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768 65536 131072 262144
22: 1 1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768 65536 131072 262144
23: 1 1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768 65536 131072 262144
24: 1 1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768 65536 131072 262144
25: 1 1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768 65536 131072 262144
26: 1 1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768 65536 131072 262144
*/
int N, M;
vector<Mint> small(int K) {
vector<Mint> ans(N + 1, 0);
for (int m = 1; m <= K; ++m) {
// x^m / (1 - 2x + x^(m+1))
vector<Mint> gs(N + 1, 0);
gs[m] = 1;
for (int i = m + 1; i <= N; ++i) {
gs[i] = 2 * gs[i - 1] - gs[i - (m+1)];
}
for (int i = m; i <= N; ++i) {
ans[i] += gs[i];
}
}
return ans;
}
int main() {
// exper::run();
for (; ~scanf("%d%d", &N, &M); ) {
Mint::setM(M);
const int K = sqrt(N);
auto ans = small(K);
// 1/(1-2x)^q
vector<Mint> ts(N + 1, 0), us(N + 1, 0);
ts[0] = 1;
for (int q = 1; ; ++q) {
const int off = (K+2) * q - 1;
if (off > N) break;
for (int i = 1; i <= N; ++i) ts[i] += 2 * ts[i - 1];
for (int i = 0; i <= N; ++i) us[i] = ts[i];
for (int i = q; i <= N; ++i) us[i] += us[i - q];
if (q & 1) {
for (int i = 0; off + i <= N; ++i) ans[off + i] += us[i];
} else {
for (int i = 0; off + i <= N; ++i) ans[off + i] -= us[i];
}
}
for (int i = 1; i <= N; ++i) {
if (i > 1) printf(" ");
printf("%u", ans[i].x);
}
puts("");
#ifdef LOCAL
const auto slw=small(N);
cerr<<"slw = "<<slw<<endl;
assert(slw==ans);
#endif
}
return 0;
}
这程序好像有点Bug，我给组数据试试？
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3920kb
input:
5 1000000007
output:
1 3 6 11 19
result:
ok 5 number(s): "1 3 6 11 19"
Test #2:
score: 0
Accepted
time: 1094ms
memory: 5548kb
input:
200000 567894337
output:
1 3 6 11 19 33 57 100 177 317 573 1045 1919 3547 6592 12311 23091 43479 82153 155715 295983 564049 1077399 2062310 3955185 7598755 14622317 28179337 54379519 105071497 203254163 393607533 195106662 344669981 35619335 477103886 79913732 147415830 329955039 273123672 546045352 337527455 443978690 4597...
result:
ok 200000 numbers
Test #3:
score: 0
Accepted
time: 2ms
memory: 4096kb
input:
2000 1000000009
output:
1 3 6 11 19 33 57 100 177 317 573 1045 1919 3547 6592 12311 23091 43479 82153 155715 295983 564049 1077399 2062310 3955185 7598755 14622317 28179337 54379519 105071497 203254163 393607533 763000999 480458646 875091002 588152874 869906045 159506110 218346934 346224469 716986623 864678016 300921504 68...
result:
ok 2000 numbers
Test #4:
score: 0
Accepted
time: 1089ms
memory: 5548kb
input:
200000 998244853
output:
1 3 6 11 19 33 57 100 177 317 573 1045 1919 3547 6592 12311 23091 43479 82153 155715 295983 564049 1077399 2062310 3955185 7598755 14622317 28179337 54379519 105071497 203254163 393607533 763000999 482213802 878601314 596928654 887457605 196364386 290308330 486636949 990790959 401755743 350504783 12...
result:
ok 200000 numbers
Test #5:
score: 0
Accepted
time: 1090ms
memory: 5356kb
input:
200000 1000000009
output:
1 3 6 11 19 33 57 100 177 317 573 1045 1919 3547 6592 12311 23091 43479 82153 155715 295983 564049 1077399 2062310 3955185 7598755 14622317 28179337 54379519 105071497 203254163 393607533 763000999 480458646 875091002 588152874 869906045 159506110 218346934 346224469 716986623 864678016 300921504 68...
result:
ok 200000 numbers
Test #6:
score: 0
Accepted
time: 0ms
memory: 3728kb
input:
1 998244853
output:
1
result:
ok 1 number(s): "1"
Test #7:
score: 0
Accepted
time: 467ms
memory: 4760kb
input:
114514 1009999999
output:
1 3 6 11 19 33 57 100 177 317 573 1045 1919 3547 6592 12311 23091 43479 82153 155715 295983 564049 1077399 2062310 3955185 7598755 14622317 28179337 54379519 105071497 203254163 393607533 763000999 470458656 855091022 538152924 769906145 959506319 818347343 556225268 166988182 844681063 390927468 51...
result:
ok 114514 numbers
Test #8:
score: 0
Accepted
time: 1085ms
memory: 5604kb
input:
199998 500000003
output:
1 3 6 11 19 33 57 100 177 317 573 1045 1919 3547 6592 12311 23091 43479 82153 155715 295983 564049 1077399 2062310 3955185 7598755 14622317 28179337 54379519 105071497 203254163 393607533 263000996 480458649 375091005 88152886 369906072 159506173 218347057 346224709 216987088 364678928 300923295 688...
result:
ok 199998 numbers
Extra Test:
score: 0
Extra Test Passed