ll f_cal(ll m, ll k){ ll ans = 0; ll up = (m + k - 1) / k; for (int c = 0; c <= up; ++c) { ans += CC(m - (c - 1) * (k - 1), c); ans %= mod; } ans %= mod; if (ans < 0) ans += mod; return ans; }
voidSolve(){ Cin(N, Q); map<ll, vector<ll> > mp; vector<vector<ll> > F(N + 2, vector<ll>(min(N, SQRT) + 2)); for (int k = 1; k <= min(N, SQRT); ++k) { F[0][k] = 1; for (int i = 1; i <= N; ++i) { F[i][k] = F[i - 1][k] + (i - k < 0 ? 1 : F[i - k][k]); F[i][k] %= mod; } } for (int _ = 1; _ <= Q; ++_) { ll x, k; Cin(x, k); ll up = (N + k - 1) / k; if (k > SQRT) { // 这个的计算是 k 越小，计算的越多的啊。 ll ans = f_cal(N, k) - (x - k < 0 ? 1 : f_cal(x - k, k)) * ( N - x - k + 1 < 0 ? 1 : f_cal(N - x - k + 1, k)); ans %= mod; if (ans < 0) ans += mod; write(ans); putc('\n'); } else { // 因此我们把这个 k 比较小的这个直接用数组存起来，后面直接输出即可 ll ans = 0; ans = F[N][k] - (x - k < 0 ? 1 : F[x - k][k]) * (N - x - k + 1 < 0 ? 1 : F[N - x - k + 1][k]); ans %= mod; if (ans < 0) ans += mod; write(ans); putc('\n'); } } }
template<typename T> voidCin(T &a){ T ans = 0; bool f = 0; char c = getc(); for (; c < '0' || c > '9'; c = getc()) { if (c == '-') f = 1; } for (; c >= '0' && c <= '9'; c = getc()) { ans = ans * 10 + c - '0'; } a = f ? -ans : ans; }
voidgetc(char &a){ char c = getc(); while (isspace(c)) { c = getc(); } a = c; }
namespace Comb { // 组合数加逆元，依赖于这个MAXN（初始化） vector<ll> frac, infrac; int ln = 1; bool initialized = false; // 在 k=0或者更小的时候 return 1 inline ll binpow(ll a, ll k){ ll res = 1; a %= mod; while (k > 0) { if (k & 1) res = (res * a) % mod; a = (a * a) % mod; k >>= 1; } return res; }
voidComb(int n){ ln = n; frac.assign(n + 5, 1); infrac.assign(n + 5, 1); for (int i = 1; i <= ln; ++i) { frac[i] = (frac[i - 1] * i) % mod; } infrac[ln] = binpow(frac[ln], mod - 2); for (int i = ln - 1; i >= 0; --i) { infrac[i] = (infrac[i + 1] * (i + 1)) % mod; } }
inline ll CC(ll n, ll k){ if (k < 0 || k > n) { #ifdef LOCAL cerr << "CC 组合数传入参数不合法，可能是传入顺序错了\n"; #endif return0; // Return 0 if k is out of range [0, n] } if (!initialized) { Comb(MAXN); initialized = true; } ll res = frac[n]; res = (res * infrac[n - k]) % mod; res = (res * infrac[k]) % mod; return res; }
inline ll PP(ll n, ll k){ if (k < 0 || k > n) { #ifdef LOCAL cerr << "PP 排列数传入参数不合法，可能是传入顺序错了\n"; #endif return0; } if (!initialized) { Comb(MAXN); initialized = true; } ll res = frac[n] * infrac[n - k]; res %= mod; return res; } }
usingnamespace Comb;
ll N, Q;
constexpr ll SQRT = 200;
ll f_cal(ll m, ll k){ ll ans = 0; ll up = (m + k - 1) / k; for (int c = 0; c <= up; ++c) { ans += CC(m - (c - 1) * (k - 1), c); ans %= mod; } ans %= mod; if (ans < 0) ans += mod; return ans; }
voidSolve(){ Cin(N, Q); map<ll, vector<ll> > mp; vector<vector<ll> > F(N + 2, vector<ll>(min(N, SQRT) + 2)); for (int k = 1; k <= min(N, SQRT); ++k) { F[0][k] = 1; for (int i = 1; i <= N; ++i) { F[i][k] = F[i - 1][k] + (i - k < 0 ? 1 : F[i - k][k]); F[i][k] %= mod; } } for (int _ = 1; _ <= Q; ++_) { ll x, k; Cin(x, k); ll up = (N + k - 1) / k; if (k > SQRT) { ll ans = f_cal(N, k) - (x - k < 0 ? 1 : f_cal(x - k, k)) * ( N - x - k + 1 < 0 ? 1 : f_cal(N - x - k + 1, k)); ans %= mod; if (ans < 0) ans += mod; write(ans); putc('\n'); } else { ll ans = 0; ans = F[N][k] - (x - k < 0 ? 1 : F[x - k][k]) * (N - x - k + 1 < 0 ? 1 : F[N - x - k + 1][k]); ans %= mod; if (ans < 0) ans += mod; write(ans); putc('\n'); } } }
signedmain(){ ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); #ifdef LOCAL cout.setf(ios::unitbuf); // 无缓冲流，方便我们调试 #endif
新建一个 clone 状态，专门用来存放原本 to 中较短的、成为了当前后缀的子串。所以它的长度严丝合缝地设为 st[p].len+1。
clone 继承 to 的所有出边和后缀链接（因为它本质上是 to 的一部分，后续可以接的字符是一样的）。
我们把 to 和新状态 cur 的后缀链接都指向这个更“纯粹”的 clone 状态。
最后，把 p 的后缀链上，所有原本指向 to 的转移边，全部重定向到 clone（纠正历史遗留的指针）。 1. 核心前提：什么会打破原有的endpos等价类？
在一个已经建好的 SAM 中，如果两个子串在同一个状态（节点）里，意味着它们在原串中出现的结束位置集合 (endpos) 是完全相同的。
现在，我们在原字符串末尾追加了一个新字符 c。产生了一个新的末尾位置，我们叫它 L。 请问：哪些子串的endpos集合会多出一个L？
答案是：只有新字符串的“后缀”们，它们的endpos才会新增L。 其他任何子串的 endpos 都不变。
这就会导致一个致命问题：原本同属于一个状态的两个子串，可能一个是新字符串的后缀，另一个不是。它们的 endpos 集合分道扬镳了，不能再待在同一个状态里了！ 2. 代码是如何精准识别并处理“分道扬镳”的？i
当我们顺着 last 的 link 链往上回溯时，其实是在按长度从大到小遍历旧字符串的所有后缀。
代码将新产生的后缀分为了三类，对应了代码里的三种情况： 情况一：从未出现过的全新后缀**（对应** cur状态）
旧字符串的这些后缀加上 c 后，形成的新子串以前从来没在串里出现过。
• endpos变化： 这些子串是全新的，它们的endpos集合只有唯一的一个值：{L}。
• 代码操作： 因为它们 endpos 完全一样（都是 {L}），所以把它们全塞进新创建的 cur 状态中。
1 2 3 4 5
// 沿着 link 链回溯，将所有没有字符 c 转移边的状态连向 cur while (p != -1 && st[p].next[c - 'a'] == -1) { st[p].next[c - 'a'] = cur; p = st[p].link; }
情况二：和平共处，没有分化（对应len(p) + 1 == len(q)****）
如果 len(p)+1==len(q)，说明状态q里面最长的子串就是X。
因为 X 是状态 q 里最长的，那么 q 里面所有比 X 短的子串，必然是 X 的后缀。既然 X 是新字符串的后缀，那它的后缀当然也全是新字符串的后缀。
• endpos变化： 状态 q 里的所有子串，统统都是新字符串的后缀。它们的endpos集合全部都齐刷刷地增加了L。
• 结论： 它们的 endpos 集合依然保持完全一致！不需要拆分。直接让 cur.link = q 即可。
情况三：发生阶级分化，必须拆分（对应len(p) + 1 < len(q)****，克隆的本质）
这是最精妙的地方。如果 len(p)+1<len(q)，说明状态 q 里面还有比X更长的子串（我们叫它Y）。
• X 的长度是 len(p)+1，它是新字符串的后缀，它的 endpos 需要加入 L。
• Y 呢？Y 也是 q 里的子串，它原本和 X 的出现位置一模一样。但是，Y不是新字符串的后缀！ （如果 Y 也是新后缀，那么我们在回溯 link 链时，应该在一个比 p 更长的后缀处就遇到 c 的转移边，而不是等到 p 才遇到）。
• endpos变化：X 的 endpos 变成了 old_endpos∪{L}，而 Y 的 endpos 依然是 old_endpos。
• 结论： 状态 q 内部“分裂”了！代表短子串的 X 和代表长子串的 Y 不能再共用一个状态了。
// 增量法向自动机中插入一个字符 voidsam_extend(char c){ int cur = sz++; // 新状态的最长子串长度是之前最长长度加 1 st[cur].len = st[last].len + 1; for (int i = 0; i < 26; ++i) { st[cur].next[i] = -1; }
int p = last; // 沿着 link 链回溯，将所有没有字符 c 转移边的状态连向 cur while (p != -1 && st[p].next[c - 'a'] == -1) { st[p].next[c - 'a'] = cur; p = st[p].link; }
// 如果一直回溯到了虚拟边界（-1），说明没有任何后缀有 c 的转移 if (p == -1) { st[cur].link = 0; } else { // 找到了第一个存在字符 c 转移边的状态 p，它转移到了状态 q int q = st[p].next[c - 'a']; // 情况一：连续转移，没有长度断层 if (st[p].len + 1 == st[q].len) { st[cur].link = q; } else { // 情况二：存在长度断层，必须拆分状态 q int clone = sz++; // 克隆状态继承 q 的转移边和 link，但修正其最长长度 st[clone].len = st[p].len + 1; for (int i = 0; i < 26; ++i) { st[clone].next[i] = st[q].next[i]; } st[clone].link = st[q].link; // 将 q 和 cur 的后缀链接都指向这个更“纯粹”的克隆状态 while (p != -1 && st[p].next[c - 'a'] == q) { st[p].next[c - 'a'] = clone; p = st[p].link; } st[q].link = clone; st[cur].link = clone; } } // 更新最后插入的状态 last = cur; }
插入字符，构造后缀自动机：函数 sma_insert()
插入一个后缀字符 c，我们到底要修改什么，其影响范围是什么？
只有新字符串的“后缀”们，它们的endpos才会新增L。 其他任何子串的 endpos 都不变。
所以我们要对所有的新字符串的后缀进行修改。
新字符串即：比如说，abaab，遍历到了 abaa， 最后的 b 还没遍历到，abaa就是我们的新字符串。
建立新字符串对应的 State 节点
这个就是平平无奇的这个初始化啊。相当于 new 一个下标为 cur 的这个节点啊，代表目前整个后缀字符串啊。（比如说，abaab，遍历到了 abaa， 最后的 b 还没遍历到，abaa 的这个长度为 4 啊）
1 2 3 4 5 6
sz++; int cur = sz; st[cur].len = st[last].len + 1; for (int i = 0; i < 26; ++i) { st[cur].next[i] = -1; }
2. 更新旧后缀的转移边
1 2 3 4
while (p != -1 && st[p].next[c - 'a'] == -1) { st[p].next[c - 'a'] = cur; p = st[p].link; }
此时我们要把之前字符串的所有后缀都加上字符 c，让它们变成新字符串的后缀。
我们通过 link 链不断回溯 last 的各个后缀状态 p：
如果 p 没有字符 c 的转移边，说明这个后缀加上c后形成的新子串以前从未出现过（即 maxstr(p)+‘c’对应的字符串后缀之前没有出现过啊（maxstr(p)，就是状态 p 所包含的最长子串，+ 是指的字符串与字符拼接）），我们直接给它连一条边指向 cur。
如果回溯过程中遇到了一个状态 p 已经有了 c 的转移边，说明从这个长度开始的后缀加上c形成的子串，在之前的字符串里已经出现过了，循环终止。
如果我们强行继续更新下面的，由于不是新子串，我们不能够保证这个任何一条转移边 u --(c)--> v 必须满足：字符串 maxstr(u)+c 的 endpos 集合，必须等于状态 v 代表的 endpos 集合。
3. 处理后缀链接 (核心难点，分三种情况)
1 2 3
if (p == -1) { st[cur].link = 0; }
如果一直回溯到了虚拟边界（p=−1），说明字符 c 以前压根就没出现过。新状态 cur 没有其它真后缀曾在图中出现，它的后缀链接直接指向根节点（状态 0，代表空串）。
1 2 3 4 5 6 7 8
int to = st[cur].next[c - BASE]; // to 可以作为我们的 link 啊 // 但是我们需要其为最小串的这个去掉首字母以后的串啊 if (st[p].len + 1 == st[to].len) { // （p 是字符串）p + ‘c’ 就是 to 中的最长子串，因此不需要对这个 to 进行这个分裂 // 根据 end pos 性质，to 中更短的，也是这个 cur 的这个后缀啊 st[cur].link = to; }
状态 p 是我们找到的第一个拥有 c 转移边的状态，它转移到了 to。
如果 st[p].len+1==st[to].len，说明to状态恰好只包含我们需要的那部分后缀（没有比它更长的了，如果有比这个 maxstr(p)+c 更长的啊，就麻烦了，因为我们保证 maxstr(p)+c 这个是 cur 的后缀，但是更长的，就一定不是 cur 的后缀了）。这是一种完美的平滑过渡，to 理所当然地成为了 cur 的后缀链接。
在一棵普通的树上求反链的数量，可以通过树形 DP 解决。
设 dp[u]表示在以u为根的子树中，选择反链的方案数加上1（加1代表在 u 的子树中什么都不选的空集方案）。
• 如果我们不选 u：可以在其各个子树中自由选择反链，根据乘法原理，方案数为 ∏v∈child(u)dp[v]。
• 如果我们选了 u：那么 u 的所有子孙都不能被选，方案数为 1。
两者相加，即：dp[u]=1+∏v∈child(u)dp[v]。
若在树中存在一条没有分叉的长为 L 的链（即连续 L 个节点都只有一个子节点），且链底部的子树 DP 值乘积为 D，那么经过这 L 个节点后，链顶部的 DP 值将恰好是 L+D。
3. 利用后缀自动机 (SAM) 压缩字典树
由于 s 的长度可达 5×105，前缀字典树的节点数可能是 O(∣s∣2) 的，直接建树会超时超空间。
这里有一个经典结论：字符串s的前缀字典树，可以通过构建其反串sR的后缀自动机 (SAM) 的 Link Tree (Parent Tree) 来完美压缩。
• 将 s 反转得到 sR，对 sR 建立后缀自动机。
• sR 的 SAM 的 Link Tree，其边代表在 sR 串前添加字符，也就等价于在原串 s 后面添加字符。
• 因此，Link Tree 中的每一个节点 u，实际上代表了前缀字典树上的一条没有分叉的链。链上每个节点对应的子串，它们在原串 s 中都有相同的起始位置 Bu。链上包含的字符串长度范围是 [len(link(u))+1,len(u)]。
4. KMP 结合 SAM 进行剪枝
我们需要知道 SAM 中每一个节点 u 所代表的那条链，有多少个节点是“有效”的（即不包含 p）。
在建立 SAM 时，记录每个节点在 sR 中第一次出现的结束位置，以此可以推算出它在原串 s 中的起始位置 Bu。
使用 KMP算法 找出 p 在原串 s 中的所有出现位置。然后预处理出数组 nxt[i]，表示在原串 s 中，起点大于等于i的最靠左的p出现位置的终点索引。
vector<string> s(n + 1); for (int i = 1; i <= n; ++i) { cin >> s[i]; int u = 1; for (char c : s[i]) { int idx = c - 'a'; if (!ch[u][idx]) { ch[u][idx] = ++tot; depth[tot] = depth[u] + 1; } u = ch[u][idx]; // 记录该节点在第 i 个请求中被访问 // 因为是从左到右处理字符串，所以每个节点在同一次请求中最多被记录一次 visits[u].push_back(i); } }
vector<string> s(n + 1); for (int i = 1; i <= n; ++i) { cin >> s[i]; int u = 1; for (char c : s[i]) { int idx = c - 'a'; if (!ch[u][idx]) { ch[u][idx] = ++tot; depth[tot] = depth[u] + 1; } u = ch[u][idx]; // 记录该节点在第 i 个请求中被访问 // 因为是从左到右处理字符串，所以每个节点在同一次请求中最多被记录一次 visits[u].push_back(i); } }
vector<string> s(n + 1); for (int i = 1; i <= n; ++i) { cin >> s[i]; int u = 1; for (char c : s[i]) { int idx = c - 'a'; if (!ch[u][idx]) { ch[u][idx] = ++tot; depth[tot] = depth[u] + 1; } u = ch[u][idx]; // 记录该节点在第 i 个请求中被访问 // 因为是从左到右处理字符串，所以每个节点在同一次请求中最多被记录一次 visits[u].push_back(i); } }
vector<int> a(m); bool possible = true; for (int i = 0; i < m; ++i) { cin >> a[i]; // 如果汐被强制要求选大于 2n 的牌，则她在前 2n 里的牌数不足 n 张，必然无法挡住风子前 n 小的牌 if (a[i] > 2 * n) { possible = false; } }
if (!possible) { cout << 0 << "\n"; return; }
// 标记哪些数字是汐必须选的（即折线图中必须向右上走的位置） vector<bool> is_fixed(2 * n + 1, false); for (int i = 0; i < m; ++i) { is_fixed[a[i]] = true; }
using ll = longlong; using ull = unsignedlonglong; using ld = longdouble; using pii = pair<int, int>; using pll = pair<ll, ll>; using vi = vector<int>; using vl = vector<ll>; using vii = vector<pii>; using vll = vector<pll>;
#define endl '\n' #define pb push_back #define eb emplace_back #define mp make_pair #define fi first #define se second #define all(x) (x).begin(), (x).end() #define rall(x) (x).rbegin(), (x).rend() #define sz(x) (int)(x).size() #define mem(a, b) memset(a, b, sizeof(a)) #define rep(i, a, n) for (int i = a; i < n; i++) #define per(i, a, n) for (int i = n - 1; i >= a; i--) #define fastio ios::sync_with_stdio(false), cin.tie(0), cout.tie(0) #define clock cerr << "Time elapsed: " << (double)clock() / CLOCKS_PER_SEC << " s.\n"
// 快速幂（带模）：返回 a^b mod template <typename T> inline T qpow(T a, T b, T mod){ T res = 1; while (b) { if (b & 1) { res = res * a % mod; } a = a * a % mod; b >>= 1; } return res; }
// 快速幂（不带模）：返回 a^b template <typename T> inline T qpow(T a, T b){ T res = 1; while (b) { if (b & 1) { res = res * a; } a = a * a; b >>= 1; } return res; }
voidsolve(){ ll n, m; cin >> n >> m;
vl a(m);
// possible = false 表示存在无法满足的必选数，答案直接是 0 bool possible = true;
// constraint[v] = true 表示值 v 是「必须选入手牌」的数 // 只需要开到 2n-1（下标 0 .. 2n-1），因为更大的值不可能出现在必胜手牌里 vl constraint(2 * n, false);
for (int i = 0; i < m; ++i) { cin >> a[i]; if (a[i] > 2 * n - 1) { // 必胜条件要求 s_n <= 2n-1，即手牌中最大的数也不能超过 2n-1。 // 现在被强制要选一个超过 2n-1 的数，必胜手牌不存在。 // 注意：这里不能直接 return，必须把剩下的 m 个数读完，否则输入流会错位。 possible = false; } else { constraint[a[i]] = true; } }
// 转移 2：不选 v，选中数量不变。只有 v 不是必选数时才允许 if (!need) { next[c] = (next[c] + dp[c]) % MOD; } }
// 施加必胜条件：v 为奇数时，写 v = 2k-1，则 k = (v+1)/2。 // 条件 s_k <= 2k-1 等价于「前缀 [1, 2k-1] 里至少已经选了 k 个数」， // 所以把所有 c < k 的状态判死（清零）。 // v 为偶数时不产生新约束，无需处理。 if (v % 2 == 1) { int k = (v + 1) / 2; for (int c = 0; c < k; ++c) { next[c] = 0; } }
