結果
問題 | No.535 自然数の収納方法 |
ユーザー |
![]() |
提出日時 | 2017-06-23 23:15:12 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 80 ms / 2,000 ms |
コード長 | 4,685 bytes |
コンパイル時間 | 1,713 ms |
コンパイル使用メモリ | 179,252 KB |
実行使用メモリ | 19,072 KB |
最終ジャッジ日時 | 2024-10-03 03:35:48 |
合計ジャッジ時間 | 3,335 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 23 |
ソースコード
#include "bits/stdc++.h"using namespace std;#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))static const int INF = 0x3f3f3f3f; static const long long INFL = 0x3f3f3f3f3f3f3f3fLL;typedef vector<int> vi; typedef pair<int, int> pii; typedef vector<pair<int, int> > vpii; typedef long long ll;template<typename T, typename U> static void amin(T &x, U y) { if (y < x) x = y; }template<typename T, typename U> static void amax(T &x, U y) { if (x < y) x = y; }template<int MOD>struct ModInt {static const int Mod = MOD;unsigned x;ModInt() : x(0) {}ModInt(signed sig) { int sigt = sig % MOD; if (sigt < 0) sigt += MOD; x = sigt; }ModInt(signed long long sig) { int sigt = sig % MOD; if (sigt < 0) sigt += MOD; x = sigt; }int get() const { return (int)x; }ModInt &operator+=(ModInt that) { if ((x += that.x) >= MOD) x -= MOD; return *this; }ModInt &operator-=(ModInt that) { if ((x += MOD - that.x) >= MOD) x -= MOD; return *this; }ModInt &operator*=(ModInt that) { x = (unsigned long long)x * that.x % MOD; return *this; }ModInt &operator/=(ModInt that) { return *this *= that.inverse(); }ModInt operator+(ModInt that) const { return ModInt(*this) += that; }ModInt operator-(ModInt that) const { return ModInt(*this) -= that; }ModInt operator*(ModInt that) const { return ModInt(*this) *= that; }ModInt operator/(ModInt that) const { return ModInt(*this) /= that; }ModInt inverse() const {signed a = x, b = MOD, u = 1, v = 0;while (b) {signed t = a / b;a -= t * b; std::swap(a, b);u -= t * v; std::swap(u, v);}if (u < 0) u += Mod;ModInt res; res.x = (unsigned)u;return res;}bool operator==(ModInt that) const { return x == that.x; }bool operator!=(ModInt that) const { return x != that.x; }ModInt operator-() const { ModInt t; t.x = x == 0 ? 0 : Mod - x; return t; }};typedef ModInt<1000000007> mint;#pragma region for precomputingint berlekampMassey(const vector<mint> &s, vector<mint> &C) {int N = (int)s.size();C.assign(N + 1, mint());vector<mint> B(N + 1, mint());C[0] = B[0] = 1;int degB = 0;vector<mint> T;int L = 0, m = 1;mint b = 1;for (int n = 0; n < N; ++ n) {mint d = s[n];for (int i = 1; i <= L; ++ i)d += C[i] * s[n - i];if (d == mint()) {++ m;} else {if (2 * L <= n)T.assign(C.begin(), C.begin() + (L + 1));mint coeff = -d * b.inverse();for (int i = 0; i <= degB; ++ i)C[m + i] += coeff * B[i];if (2 * L <= n) {L = n + 1 - L;B.swap(T);degB = (int)B.size() - 1;b = d;m = 1;} else {++ m;}}}C.resize(L + 1);return L;}void computeMinimumPolynomialForLinearlyRecurrentSequence(const vector<mint> &a, vector<mint> &phi) {int n2 = (int)a.size(), n = n2 / 2;assert(n2 % 2 == 0);int L = berlekampMassey(a, phi);reverse(phi.begin(), phi.begin() + (L + 1));}template<int MOD> int mintToSigned(ModInt<MOD> a) {int x = a.get();if (x <= MOD / 2)return x;elsereturn x - MOD;}int outputPrecomputedMinimalPolynomial(vector<mint> seq, ostream &os) {if (seq.size() % 2 == 1) seq.pop_back();vector<mint> phi;computeMinimumPolynomialForLinearlyRecurrentSequence(seq, phi);if (phi.size() >= seq.size() / 2 - 2) {cerr << "warning: maybe not enough terms" << endl;}cerr << "/*" << phi.size() - 1 << "*/";os << "{{ ";rep(i, phi.size() - 1) {if (i != 0) os << ", ";os << seq[i].get();}os << " }, { ";rep(i, phi.size()) {if (i != 0) os << ", ";os << mintToSigned(phi[i]);}os << " }}";return (int)phi.size() - 1;}#pragma endregionint main() {//A_{i-1} - (i - 1) < A_i//A_{i-1} - i < A_i//A_N - N < A_1//A_N <= A_1//A_{N-1} - {N-1} < A_N//A_{N-1} < A_N + Nint N;while (~scanf("%d", &N)) {mint ans;rep(ANis1, 2) {vector<vector<mint>> dp(N - 1, vector<mint>(N + 2));if (ANis1) {dp[0][1] += 1;} else {rer(AN, 2, N)dp[0][AN] += 1;}rep(i, N - 2) {rer(j, 1, N) {mint x = dp[i][j];if (x.x == 0) continue;if (i + 1 <= j) {dp[i + 1][j - i] += x;dp[i + 1][N + 1 - i] -= x;} else {//k = 1 + idp[i + 1][1] += x * (i + 1 - j);dp[i + 1][2] -= x * (i + 1 - j);dp[i + 1][1] += x;dp[i + 1][N + 1 - i] -= x;}}rer(j, 1, N)dp[i + 1][j + 1] += dp[i + 1][j];}mint sum;rer(j, 1, N) {mint x = dp[N - 2][j];if (x.x == 0) continue;sum += x * (N - j);if (!ANis1)sum += x;}ans += sum;}printf("%d\n", ans.get());}return 0;}