結果
| 問題 |
No.1684 Find Brackets
|
| ユーザー |
 ecottea
|
| 提出日時 | 2025-07-10 15:38:50 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 503 ms / 2,000 ms |
| コード長 | 15,768 bytes |
| コンパイル時間 | 4,705 ms |
| コンパイル使用メモリ | 270,924 KB |
| 実行使用メモリ | 11,440 KB |
| 最終ジャッジ日時 | 2025-07-10 15:39:03 |
| 合計ジャッジ時間 | 11,691 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 21 |
ソースコード
#ifndef HIDDEN_IN_VS // 折りたたみ用
// 警告の抑制
#define _CRT_SECURE_NO_WARNINGS
// ライブラリの読み込み
#include <bits/stdc++.h>
using namespace std;
// 型名の短縮
using ll = long long; using ull = unsigned long long; // -2^63 ～ 2^63 = 9e18（int は -2^31 ～ 2^31 = 2e9）
using pii = pair<int, int>; using pll = pair<ll, ll>; using pil = pair<int, ll>; using pli = pair<ll, int>;
using vi = vector<int>; using vvi = vector<vi>; using vvvi = vector<vvi>; using vvvvi = vector<vvvi>;
using vl = vector<ll>; using vvl = vector<vl>; using vvvl = vector<vvl>; using vvvvl = vector<vvvl>;
using vb = vector<bool>; using vvb = vector<vb>; using vvvb = vector<vvb>;
using vc = vector<char>; using vvc = vector<vc>; using vvvc = vector<vvc>;
using vd = vector<double>; using vvd = vector<vd>; using vvvd = vector<vvd>;
template <class T> using priority_queue_rev = priority_queue<T, vector<T>, greater<T>>;
using Graph = vvi;
// 定数の定義
const double PI = acos(-1);
int DX[4] = { 1, 0, -1, 0 }; // 4 近傍（下，右，上，左）
int DY[4] = { 0, 1, 0, -1 };
int INF = 1001001001; ll INFL = 4004004003094073385LL; // (int)INFL = INF, (int)(-INFL) = -INF;
// 入出力高速化
struct fast_io { fast_io() { cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(18); } } fastIOtmp;
// 汎用マクロの定義
#define all(a) (a).begin(), (a).end()
#define sz(x) ((int)(x).size())
#define lbpos(a, x) (int)distance((a).begin(), std::lower_bound(all(a), (x)))
#define ubpos(a, x) (int)distance((a).begin(), std::upper_bound(all(a), (x)))
#define Yes(b) {cout << ((b) ? "Yes\n" : "No\n");}
#define rep(i, n) for(int i = 0, i##_len = int(n); i < i##_len; ++i) // 0 から n-1 まで昇順
#define repi(i, s, t) for(int i = int(s), i##_end = int(t); i <= i##_end; ++i) // s から t まで昇順
#define repir(i, s, t) for(int i = int(s), i##_end = int(t); i >= i##_end; --i) // s から t まで降順
#define repe(v, a) for(const auto& v : (a)) // a の全要素（変更不可能）
#define repea(v, a) for(auto& v : (a)) // a の全要素（変更可能）
#define repb(set, d) for(int set = 0, set##_ub = 1 << int(d); set < set##_ub; ++set) // d ビット全探索（昇順）
#define repis(i, set) for(int i = lsb(set), bset##i = set; i < 32; bset##i -= 1 << i, i = lsb(bset##i)) // set の全要素（昇順）
#define repp(a) sort(all(a)); for(bool a##_perm = true; a##_perm; a##_perm = next_permutation(all(a))) // a の順列全て（昇順）
#define uniq(a) {sort(all(a)); (a).erase(unique(all(a)), (a).end());} // 重複除去
#define EXIT(a) {cout << (a) << endl; exit(0);} // 強制終了
#define inQ(x, y, u, l, d, r) ((u) <= (x) && (l) <= (y) && (x) < (d) && (y) < (r)) // 半開矩形内判定
// 汎用関数の定義
template <class T> inline ll powi(T n, int k) { ll v = 1; rep(i, k) v *= n; return v; }
template <class T> inline bool chmax(T& M, const T& x) { if (M < x) { M = x; return true; } return false; } // 最大値を更新（更新されたら true を返す）
template <class T> inline bool chmin(T& m, const T& x) { if (m > x) { m = x; return true; } return false; } // 最小値を更新（更新されたら true を返す）
template <class T> inline T getb(T set, int i) { return (set >> i) & T(1); }
template <class T> inline T smod(T n, T m) { n %= m; if (n < 0) n += m; return n; } // 非負mod
// 演算子オーバーロード
template <class T, class U> inline istream& operator>>(istream& is, pair<T, U>& p) { is >> p.first >> p.second; return is; }
template <class T> inline istream& operator>>(istream& is, vector<T>& v) { repea(x, v) is >> x; return is; }
template <class T> inline vector<T>& operator--(vector<T>& v) { repea(x, v) --x; return v; }
template <class T> inline vector<T>& operator++(vector<T>& v) { repea(x, v) ++x; return v; }
#endif // 折りたたみ用
#if __has_include(<atcoder/all>)
#include <atcoder/all>
using namespace atcoder;
#ifdef _MSC_VER
#include "localACL.hpp"
#endif
//using mint = modint998244353;
using mint = static_modint<(int)1e9+7>;
//using mint = modint; // mint::set_mod(m);
using vm = vector<mint>; using vvm = vector<vm>; using vvvm = vector<vvm>; using vvvvm = vector<vvvm>; using pim = pair<int, mint>;
#endif
#ifdef _MSC_VER // 手元環境（Visual Studio）
#include "local.hpp"
#else // 提出用（gcc）
int mute_dump = 0;
int frac_print = 0;
#if __has_include(<atcoder/all>)
namespace atcoder {
inline istream& operator>>(istream& is, mint& x) { ll x_; is >> x_; x = x_; return is; }
inline ostream& operator<<(ostream& os, const mint& x) { os << x.val(); return os; }
}
#endif
inline int popcount(int n) { return __builtin_popcount(n); }
inline int popcount(ll n) { return __builtin_popcountll(n); }
inline int lsb(int n) { return n != 0 ? __builtin_ctz(n) : 32; }
inline int lsb(ll n) { return n != 0 ? __builtin_ctzll(n) : 64; }
inline int msb(int n) { return n != 0 ? (31 - __builtin_clz(n)) : -1; }
inline int msb(ll n) { return n != 0 ? (63 - __builtin_clzll(n)) : -1; }
#define dump(...)
#define dumpel(v)
#define dump_math(v)
#define input_from_file(f)
#define output_to_file(f)
#define Assert(b) { if (!(b)) { vc MLE(1<<30); EXIT(MLE.back()); } } // RE の代わりに MLE を出す
#endif
//【部分集合の全探索（大きさ固定）】O(nCr)
/*
* 大きさ n の全体集合 Ω のうち，大きさ r の部分集合 set⊂Ω を昇順に全探索する．
*
* 制約：r > 0
*/
// verify : https://onlinejudge.u-aizu.ac.jp/courses/lesson/8/ITP2/all/ITP2_11_D
#define repbc(set, n, r) for(int set = (1 << int(r)) - 1, lb, nx; set < (1 << int(n)); lb = set & -set, nx = set + lb, set = (((set & ~nx) / lb) >> 1) | nx)
ll naive(int n, int m) {
if (m == 0) return 2 * n;
ll res = 0;
repbc(set, n, m) {
vi acc(n + 1);
rep(i, n) acc[i + 1] = acc[i] + (getb(set, i) ? 1 : -1);
int acc_min = *min_element(all(acc));
res += (acc[0] - acc_min) + n + (acc[n] - acc_min);
}
return res;
}
void zikken() {
int N = 28;
vvl tbl(N);
repi(n, 1, N) {
tbl[n - 1].resize(n);
repi(m, 1, n) {
dump(n, m);
tbl[n - 1][m - 1] = naive(n, m);
}
}
dumpel(tbl);
dump_math(tbl);
exit(0);
}
/*
0: 2
1: 6 4
2: 14 14 6
3: 26 34 26 8
4: 42 72 72 42 10
5: 62 134 164 134 62 12
6: 86 226 338 338 226 86 14
7: 114 354 634 746 634 354 114 16
8: 146 524 1100 1520 1520 1100 524 146 18
9: 182 742 1792 2872 3292 2872 1792 742 182 20
10: 222 1014 2774 5084 6668 6668 5084 2774 1014 222 22
11: 266 1346 4118 8518 12676 14260 12676 8518 4118 1346 266 24
12: 314 1744 5904 13626 22778 28784 28784 22778 13626 5904 1744 314 26
13: 366 2214 8220 20960 38978 54994 61000 54994 38978 20960 8220 2214 366 28
14: 422 2762 11162 31182 63942 99978 122858 122858 99978 63942 31182 11162 2762 422 30
15: 482 3394 14834 45074 101130 173930 235706 258586 235706 173930 101130 45074 14834 3394 482 32
16: 546 4116 19348 63548 154940 291076 432516 520032 520032 432516 291076 154940 63548 19348 4116 546 34
17: 614 4934 24824 87656 230864 470768 762488 1001168 1088684 1001168 762488 470768 230864 87656 24824 4934 614 36
18: 686 5854 31390 118600 335656 738760 1296904 1851172 2187092 2187092 1851172 1296904 738760 335656 118600 31390 5854 686 38
19: 762 6882 39182 157742 477512 1128680 2136440 3299240 4223020 4558940 4223020 3299240 2136440 1128680 477512 157742 39182 6882 762 40
20: 842 8024 48344 206614 666262 1683712 3420160 5687620 7858180 9151472 9151472 7858180 5687620 3420160 1683712 666262 206614 48344 8024 842 42
21: 926 9286 59028 266928 913574 2458502 5336432 9514760 14133660 17715084 19008376 17715084 14133660 9514760 5336432 2458502 913574 266928 59028 9286 926 44
22: 1014 10674 71394 340586 1233170 3521302 8136022 15490732 24643260 33142036 38134324 38134324 33142036 24643260 15490732 8136022 3521302 1233170 340586 71394 10674 1014 46
23: 1106 12194 85610 429690 1641054 4956366 12147638 24607382 41768372 60073428 73980516 78972804 73980516 60073428 41768372 24607382 12147638 4956366 1641054 429690 85610 12194 1106 48
24: 1202 13852 101852 536552 2155752 6866612 17796212 38225962 68990762 105764312 139046232 158361632 158361632 139046232 105764312 68990762 38225962 17796212 6866612 2155752 536552 101852 13852 1202 50
25: 1302 15654 120304 663704 2798564 9376564 25624224 58185324 111302674 181292594 253725344 307808464 327123864 307808464 253725344 181292594 111302674 58185324 25624224 9376564 2798564 663704 120304 15654 1302 52
26: 1406 17606 141158 813908 3593828 12635588 36316388 86934098 175737098 303218738 450470258 580849208 655733528 655733528 580849208 450470258 303218738 175737098 86934098 36316388 12635588 3593828 813908 141158 17606 1406 54
27: 1514 19714 164614 990166 4569196 16821436 50728036 127690636 272044846 495828406 779764786 1066087186 1276699336 1351583656 1276699336 1066087186 779764786 495828406 272044846 127690636 50728036 16821436 4569196 990166 164614 19714 1514 56
{{2},{6,4},{14,14,6},{26,34,26,8},{42,72,72,42,10},{62,134,164,134,62,12},{86,226,338,338,226,86,14},{114,354,634,746,634,354,114,16},{146,524,1100,1520,1520,1100,524,146,18},{182,742,1792,2872,3292,2872,1792,742,182,20},{222,1014,2774,5084,6668,6668,5084,2774,1014,222,22},{266,1346,4118,8518,12676,14260,12676,8518,4118,1346,266,24},{314,1744,5904,13626,22778,28784,28784,22778,13626,5904,1744,314,26},{366,2214,8220,20960,38978,54994,61000,54994,38978,20960,8220,2214,366,28},{422,2762,11162,31182,63942,99978,122858,122858,99978,63942,31182,11162,2762,422,30},{482,3394,14834,45074,101130,173930,235706,258586,235706,173930,101130,45074,14834,3394,482,32},{546,4116,19348,63548,154940,291076,432516,520032,520032,432516,291076,154940,63548,19348,4116,546,34},{614,4934,24824,87656,230864,470768,762488,1001168,1088684,1001168,762488,470768,230864,87656,24824,4934,614,36},{686,5854,31390,118600,335656,738760,1296904,1851172,2187092,2187092,1851172,1296904,738760,335656,118600,31390,5854,686,38},{762,6882,39182,157742,477512,1128680,2136440,3299240,4223020,4558940,4223020,3299240,2136440,1128680,477512,157742,39182,6882,762,40},{842,8024,48344,206614,666262,1683712,3420160,5687620,7858180,9151472,9151472,7858180,5687620,3420160,1683712,666262,206614,48344,8024,842,42},{926,9286,59028,266928,913574,2458502,5336432,9514760,14133660,17715084,19008376,17715084,14133660,9514760,5336432,2458502,913574,266928,59028,9286,926,44},{1014,10674,71394,340586,1233170,3521302,8136022,15490732,24643260,33142036,38134324,38134324,33142036,24643260,15490732,8136022,3521302,1233170,340586,71394,10674,1014,46},{1106,12194,85610,429690,1641054,4956366,12147638,24607382,41768372,60073428,73980516,78972804,73980516,60073428,41768372,24607382,12147638,4956366,1641054,429690,85610,12194,1106,48},{1202,13852,101852,536552,2155752,6866612,17796212,38225962,68990762,105764312,139046232,158361632,158361632,139046232,105764312,68990762,38225962,17796212,6866612,2155752,536552,101852,13852,1202,50},{1302,15654,120304,663704,2798564,9376564,25624224,58185324,111302674,181292594,253725344,307808464,327123864,307808464,253725344,181292594,111302674,58185324,25624224,9376564,2798564,663704,120304,15654,1302,52},{1406,17606,141158,813908,3593828,12635588,36316388,86934098,175737098,303218738,450470258,580849208,655733528,655733528,580849208,450470258,303218738,175737098,86934098,36316388,12635588,3593828,813908,141158,17606,1406,54},{1514,19714,164614,990166,4569196,16821436,50728036,127690636,272044846,495828406,779764786,1066087186,1276699336,1351583656,1276699336,1066087186,779764786,495828406,272044846,127690636,50728036,16821436,4569196,990166,164614,19714,1514,56}};
これを 2D P-recursive チェッカーにぶち込みコードを自動生成する．
0 除算で漸化式が使えないところがあるが，対称性を利用して解決する．
*/
int main() {
// input_from_file("input.txt");
// output_to_file("output.txt");
// zikken();
int n, m;
cin >> n >> m;
vm dp(n + 1);
auto Power = [&](const mint& x, int n) { mint res = 1; rep(hoge, n) res *= x; return res; };
{
dp[0] = 2 * n;
}
{
mint nn1 = n;
dp[1] = 2 * (1 - nn1 + Power(nn1, 2));
}
{
vm dp2{ -1, 4, 14, 34, 72, 134, 226, 354, 524, 742, 1014, 1346, 1744, 2214, \
2762, 3394, 4116, 4934, 5854, 6882, 8024, 9286, 10674, 12194, 13852, \
15654, 17606, 19714 };
dp2.resize(n + 1);
{
auto dpsub1 = [&](const mint& x) { return dp2[x.val()]; };
repi(i, 5, n) {
mint nn = i;
dp2[i] = ((-3 + nn) * (5 + 2 * nn) * dpsub1(-2 + nn) + (33 + nn * (8 + 5 * nn)) * dpsub1(-1 + nn)) / (39 + nn * (-20 + 7 * nn));
}
}
dp[2] = dp2[n - 1];
}
{
vm dp2{ -1, 6, 26, 72, 164, 338, 634, 1100, 1792, 2774, 4118, 5904, 8220, 11162, \
14834, 19348, 24824, 31390, 39182, 48344, 59028, 71394, 85610, \
101852, 120304, 141158, 164614 };
dp2.resize(n + 1);
{
auto dpsub1 = [&](const mint& x) { return dp2[x.val()]; };
repi(i, 5, n) {
mint nn = i;
dp2[i] = (-8 * (-5 + nn) * nn * dpsub1(-3 + nn) + (168 + (-62 + nn) * nn) * dpsub1(-2 + nn) + (4 + nn * (-53 + 12 * nn)) * dpsub1(-1 + nn)) /
(44 + 5 * (-7 + nn) * nn);
}
}
dp[3] = dp2[n - 2];
}
auto dpsub = [&](const mint& x, const mint& y) { return dp[y.val()]; };
// 0 除算の発生しないギリギリまでは漸化式で埋める．
repi(i, 4, n / 2) {
mint nn1 = n;
mint nn2 = i;
dp[i] = -(((700581974 * Power(nn1, 6) + Power(nn1, 5) * (-2491270481 + 994180316 * nn2) +
Power(nn1, 4) * (4752959221 - 3572746162 * nn2 + 723860738 * Power(nn2, 2)) +
Power(nn1, 3) * (-8334138866 + 2 * nn2 * (4023081423 + nn2 * (-1380696345 + 174393361 * nn2))) +
(-3 + nn2) * (-2 + nn2) * (1813967271 + nn2 *
(-9058196973 + nn2 * (7081475723 + nn2 * (-2046557542 + 209311507 * nn2)))) +
Power(nn1, 2) * (46081673365 + nn2 * (-68335126131 + nn2 * (38172371942 + nn2 * (-9384099669 + 860524792 * nn2)))) +
nn1 * (1244427029 + nn2 * (7446734673 + nn2 *
(-11620733324 + nn2 * (6661865864 + nn2 * (-1697376082 + 162753979 * nn2)))))) * dpsub(nn1, -3 + nn2) +
(299418033 * Power(nn1, 6) + Power(nn1, 5) * (-1107565606 + 604655757 * nn2) +
Power(nn1, 4) * (1863335960 + 3 * nn2 * (-884674820 + 295538239 * nn2)) +
Power(-2 + nn2, 2) * (-1 + nn2) * (2197672139 + nn2 * (-383704868 + 209311507 * (-3 + nn2) * nn2)) +
Power(nn1, 3) * (-4380893735 + 2 * nn2 * (3776237978 + nn2 * (-2142483759 + 406983632 * nn2))) +
nn1 * (-2 + nn2) * (3808147594 + nn2 * (-9994180379 + nn2 * (9732491653 + nn2 * (-3930163736 + 581376993 * nn2)))) +
Power(nn1, 2) * (4523180111 + nn2 * (-10322499498 + nn2 * (9787680033 + nn2 * (-3988360646 + 604655757 * nn2))))) *
dpsub(nn1, -2 + nn2) + (-1 + nn2) * (401163941 * Power(nn1, 5) + Power(nn1, 4) * (616295139 + 90106526 * nn2) +
Power(nn1, 3) * (284967490 + nn2 * (-308246254 + 232590271 * nn2)) +
Power(nn1, 2) * (-395146881 + nn2 * (1688547861 - 941605728 * nn2 + 348786722 * Power(nn2, 2))) +
(-1 + nn2) * (906884951 + nn2 * (-1953245117 + 2 * nn2 * (1494081635 + 2 * nn2 * (-581376993 + 197672125 * nn2)))) +
nn1 * (628131890 + nn2 * (-2239002083 + nn2 * (4826198781 + nn2 * (-3256066425 + 837246028 * nn2))))) *
dpsub(nn1, -1 + nn2)) /
(nn2 * (69836292 + Power(nn1, 4) * (700581974 + 299418033 * nn2) +
Power(nn1, 3) * (808147573 + 9 * nn2 * (65244076 + 67183973 * nn2)) +
Power(nn1, 2) * (741319811 + nn2 * (409794793 + nn2 * (662852667 + 186032743 * nn2))) +
nn2 * (150917228 + nn2 * (744525710 + nn2 * (569540242 + 7 * nn2 * (96356007 + 112955500 * nn2)))) +
nn1 * (889623247 + nn2 * (145097537 + nn2 * (663050036 + nn2 * (883606187 + 418623014 * nn2)))))));
}
// 0 残りは対称性を利用して埋める．
repi(i, n / 2 + 1, n) dp[i] = dp[n - i];
//dump(dp);
mint res = 0;
repi(i, m, n) res += dp[i];
EXIT(res);
}