結果
| 問題 | No.802 だいたい等差数列 |
| ユーザー |
 snrnsidy
|
| 提出日時 | 2021-05-03 22:38:29 |
| 言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 4,630 bytes |
| コンパイル時間 | 1,910 ms |
| コンパイル使用メモリ | 150,552 KB |
| 実行使用メモリ | 30,252 KB |
| 最終ジャッジ日時 | 2024-07-22 12:53:56 |
| 合計ジャッジ時間 | 6,935 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge4 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | WA | - |
| testcase_01 | AC | 107 ms
12,008 KB |
| testcase_02 | WA | - |
| testcase_03 | WA | - |
| testcase_04 | WA | - |
| testcase_05 | AC | 120 ms
11,260 KB |
| testcase_06 | WA | - |
| testcase_07 | WA | - |
| testcase_08 | WA | - |
| testcase_09 | WA | - |
| testcase_10 | TLE | - |
| testcase_11 | TLE | - |
| testcase_12 | -- | - |
| testcase_13 | -- | - |
| testcase_14 | -- | - |
| testcase_15 | -- | - |
| testcase_16 | -- | - |
| testcase_17 | -- | - |
| testcase_18 | -- | - |
| testcase_19 | -- | - |
| testcase_20 | -- | - |
| testcase_21 | -- | - |
| testcase_22 | -- | - |
| testcase_23 | -- | - |
| testcase_24 | -- | - |
| testcase_25 | -- | - |
| testcase_26 | -- | - |
| testcase_27 | -- | - |
| testcase_28 | -- | - |
| testcase_29 | -- | - |
| testcase_30 | -- | - |
| testcase_31 | -- | - |
| testcase_32 | -- | - |
| testcase_33 | -- | - |
コンパイルメッセージ
main.cpp: In function 'std::vector<int> berlekamp_massey(std::vector<int>)':
main.cpp:55:44: warning: 'ld' may be used uninitialized [-Wmaybe-uninitialized]
55 | lint k = -(x[i] - t) * ipow(ld, mod - 2) % mod;
| ~~~~^~~~~~~~~~~~~
main.cpp:42:17: note: 'ld' was declared here
42 | int lf, ld;
| ^~
main.cpp:56:33: warning: 'lf' may be used uninitialized [-Wmaybe-uninitialized]
56 | vector<int> c(i - lf - 1);
| ~~^~~~
main.cpp:42:13: note: 'lf' was declared here
42 | int lf, ld;
| ^~
ソースコード
#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <cstdio>
#include <limits>
#include <vector>
#include <cstdlib>
#include <numeric>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <functional>
#include <iomanip>
#include <unordered_map>
#include <memory.h>
#include <unordered_set>
#include <fstream>
#include <random>
using namespace std;
const long long int mod = 1e9 + 7;
using lint = long long;
lint ipow(lint x, lint p) {
lint ret = 1, piv = x;
while (p) {
if (p & 1) ret = ret * piv % mod;
piv = piv * piv % mod;
p >>= 1;
}
return ret;
}
vector<int> berlekamp_massey(vector<int> x) {
vector<int> ls, cur;
int lf, ld;
for (int i = 0; i < x.size(); i++) {
lint t = 0;
for (int j = 0; j < cur.size(); j++) {
t = (t + 1ll * x[i - j - 1] * cur[j]) % mod;
}
if ((t - x[i]) % mod == 0) continue;
if (cur.empty()) {
cur.resize(i + 1);
lf = i;
ld = (t - x[i]) % mod;
continue;
}
lint k = -(x[i] - t) * ipow(ld, mod - 2) % mod;
vector<int> c(i - lf - 1);
c.push_back(k);
for (auto& j : ls) c.push_back(-j * k % mod);
if (c.size() < cur.size()) c.resize(cur.size());
for (int j = 0; j < cur.size(); j++) {
c[j] = (c[j] + cur[j]) % mod;
}
if (i - lf + (int)ls.size() >= (int)cur.size()) {
tie(ls, lf, ld) = make_tuple(cur, i, (t - x[i]) % mod);
}
cur = c;
}
for (auto& i : cur) i = (i % mod + mod) % mod;
return cur;
}
int get_nth(vector<int> rec, vector<int> dp, lint n) {
int m = rec.size();
vector<int> s(m), t(m);
s[0] = 1;
if (m != 1) t[1] = 1;
else t[0] = rec[0];
auto mul = [&rec](vector<int> v, vector<int> w) {
int m = v.size();
vector<int> t(2 * m);
for (int j = 0; j < m; j++) {
for (int k = 0; k < m; k++) {
t[j + k] += 1ll * v[j] * w[k] % mod;
if (t[j + k] >= mod) t[j + k] -= mod;
}
}
for (int j = 2 * m - 1; j >= m; j--) {
for (int k = 1; k <= m; k++) {
t[j - k] += 1ll * t[j] * rec[k - 1] % mod;
if (t[j - k] >= mod) t[j - k] -= mod;
}
}
t.resize(m);
return t;
};
while (n) {
if (n & 1) s = mul(s, t);
t = mul(t, t);
n >>= 1;
}
lint ret = 0;
for (int i = 0; i < m; i++) ret += 1ll * s[i] * dp[i] % mod;
return ret % mod;
}
int guess_nth_term(vector<int> x, lint n) {
if (n < x.size()) return x[n];
vector<int> v = berlekamp_massey(x);
if (v.empty()) return 0;
return get_nth(v, x, n);
}
struct elem { int x, y, v; }; // A_(x, y) <- v, 0-based. no duplicate please..
vector<int> get_min_poly(int n, vector<elem> M) {
// smallest poly P such that A^i = sum_{j < i} {A^j \times P_j}
vector<int> rnd1, rnd2;
mt19937 rng(0x14004);
auto randint = [&rng](int lb, int ub) {
return uniform_int_distribution<int>(lb, ub)(rng);
};
for (int i = 0; i < n; i++) {
rnd1.push_back(randint(1, mod - 1));
rnd2.push_back(randint(1, mod - 1));
}
vector<int> gobs;
for (int i = 0; i < 2 * n + 2; i++) {
int tmp = 0;
for (int j = 0; j < n; j++) {
tmp += 1ll * rnd2[j] * rnd1[j] % mod;
if (tmp >= mod) tmp -= mod;
}
gobs.push_back(tmp);
vector<int> nxt(n);
for (auto& i : M) {
nxt[i.x] += 1ll * i.v * rnd1[i.y] % mod;
if (nxt[i.x] >= mod) nxt[i.x] -= mod;
}
rnd1 = nxt;
}
auto sol = berlekamp_massey(gobs);
reverse(sol.begin(), sol.end());
return sol;
}
lint det(int n, vector<elem> M) {
vector<int> rnd;
mt19937 rng(0x14004);
auto randint = [&rng](int lb, int ub) {
return uniform_int_distribution<int>(lb, ub)(rng);
};
for (int i = 0; i < n; i++) rnd.push_back(randint(1, mod - 1));
for (auto& i : M) {
i.v = 1ll * i.v * rnd[i.y] % mod;
}
auto sol = get_min_poly(n, M)[0];
if (n % 2 == 0) sol = mod - sol;
for (auto& i : rnd) sol = 1ll * sol * ipow(i, mod - 2) % mod;
return sol;
}
long long int dp[1000001];
long long int psum[1000001];
int main(void)
{
cin.tie(0);
ios::sync_with_stdio(false);
int N, M, D1, D2;
vector <int> v;
cin >> N >> M >> D1 >> D2;
v.push_back(0);
for (int i = 1; i <= M; i++)
{
dp[i] = 1;
}
for (int i = 0; i < 300; i++)
{
psum[0] = dp[0];
for (int j = 1; j <= M; j++)
{
psum[j] = ((dp[j] % mod) + (psum[j - 1] % mod) % mod);
psum[j] %= mod;
}
memset(dp, 0, sizeof(dp));
//cout << i << ' ' << psum[M] << '\n';
v.push_back(psum[M]);
for (int j = 1; j <= M; j++)
{
int l = j - D2;
int r = j - D1;
if (r >= 0)
{
long long int val = psum[r];
if (l - 1 >= 0)
{
val -= psum[l - 1];
if (val < 0)
{
val += mod;
}
}
dp[j] = val;
}
}
}
cout << guess_nth_term(v, N) << '\n';
return 0;
}