省队集训Ⅱ-Day8

· · 个人记录

Day8

Color

这道题的优化是真的爽, 考场上的代码我存了 6 个版本, 每个版本都有大改, 有时候能优化掉一个复杂度, 而且越快的版本貌似码量越少.

开始的开始, 写了二维的 DP, f_{i, j} 表示第 i 个格子是第 j 个连续的白格子的方案数, 结果发现转移非常麻烦, 于是就弃了.

color-40'.cpp

然后考虑用 f_i 表示第 i 个格子涂黑, i + 1 到 n 不涂黑的方案数, 写出方程:

f_{i} = \sum_{j}^{j + k \leq i} f_{j}

然后发现如果要得到正确的答案, j 可能会出现负数, 因为 f_{i \in [1, k]} 的答案要从 f_{j\in[1 - k, 0]} 转移过来. 为了防止 RE, 只能把坐标向右平移 k.

对于每个 k 都会进行一次 O(n^2) 的 DP, 将询问离线, 按 k 排序, O(nlogn), 得到了 f 数组.

对于点 x 是不涂色的, 分两部分考虑, 枚举它左边的最近的黑点 i, 右边最近的黑点 j. 对于每对 j - i \geq k 的点, 答案就是 f_if_{n - j + 1}, 不要忘了左边不涂, 右边不涂和左右都不涂的情况.

写了非常麻烦的版本, 标称 40', 实测 20', 因为有一半的点 WA 掉了, 应该是因为我的思路太繁杂, 有一点细节没有处理好.

总复杂度 O(nlogn + n^2(k + m))

unsigned n, m, Ans(0), f[1005];
char flg(0);
struct Que {
  unsigned Quex, Quek, Num, Ans;
  inline const char operator<(const Que &x) const{
    return this->Quek < x.Quek;
  }
}Q[100005];
int main() {
  n = RD(), m = RD();
  for (register unsigned i(1); i <= m; ++i) {
    Q[i].Quex = RD(), Q[i].Quek = RD(), Q[i].Num = i;
  }
  sort(Q + 1, Q + m + 1);
  for (register unsigned T(1); T <= m; ++T) {
    if(Q[T].Quek ^ Q[T - 1].Quek){
      memset(f, 0, sizeof(f));
        f[1] = 1;
      for (register unsigned i(Q[T].Quek); i <= n + Q[T].Quek; ++i) {
        for (register unsigned j(1); j <= i - Q[T].Quek; ++j) {
          f[i] += f[j];
          if(f[i] >= MOD) f[i] -= MOD;
        }
      }
    }
    register unsigned long long TmpA(1);
    for (register unsigned i(1 + Q[T].Quek); i <= n + Q[T].Quek - Q[T].Quex; ++i) {
      TmpA += f[i];
      if(TmpA >= MOD) TmpA -= MOD;
    }
    for (register unsigned i(1 + Q[T].Quek); i < Q[T].Quex + Q[T].Quek; ++i) {
      TmpA += f[i];
      if(TmpA >= MOD) TmpA -= MOD;
    }
    for (register unsigned i(1 + Q[T].Quek); i < Q[T].Quex + Q[T].Quek; ++i) {
      for (register unsigned j(1 + Q[T].Quek); j <= min(n + Q[T].Quek - Q[T].Quex, n + Q[T].Quek + 1 - i); ++j) {
        TmpA = (TmpA + (unsigned long long)f[i] * f[j]) % MOD;
      }
    }
    Q[Q[T].Num].Ans = TmpA;
  }
  for (register unsigned i(1); i <= m; ++i) {
    printf("%u\n", Q[i].Ans);
  }
  return 0;
}

color-50'Ex.cpp

这个版本已经能过 40' 了, 显然我对我的时间复杂度没有准确的估计.

这个版本的更新是设 Sum_i = \displaystyle{\sum_{j = 1}^{j < i}}, 用前缀和优化将每次求 f 的 DP 降到了 O(n), x 的左右不选情况降到了 O(1), 单次询问降到了 O(n), 所以时间复杂度来到了 O(nlogn + n(k + m)). 这是里程碑式的飞跃.

unsigned n, m, Ans(0), f[100005], Sum[100005];
char flg(0);
struct Que {
  unsigned Quex, Quek, Num, Ans;
  inline const char operator<(const Que &x) const{
    return (this->Quek ^ x.Quek) ? (this->Quek < x.Quek) : (this->Quex < x.Quex);
  }
}Q[100005];
int main() {
  n = RD(), m = RD();
  for (register unsigned i(1); i <= m; ++i) {
    Q[i].Quex = RD(), Q[i].Quek = RD(), Q[i].Num = i;
  }
  sort(Q + 1, Q + m + 1);
  for (register unsigned T(1); T <= m; ++T) {
    if(Q[T].Quek ^ Q[T - 1].Quek){
      memset(f, 0, sizeof(f)), f[1] = 1, Sum[0] = 0;
      for (register unsigned i(Q[T].Quek), j(1), TmpFj(0); i <= n + Q[T].Quek; ++i) {
        while (j <= i - Q[T].Quek) {TmpFj += f[j], ++j; if(TmpFj >= MOD) TmpFj -= MOD;}
        f[i] += TmpFj; if(f[i] >= MOD) f[i] -= MOD;
      }
      for (register unsigned i(1); i <= n + Q[T].Quek; ++i) {Sum[i] = Sum[i - 1] + f[i]; if(Sum[i] >= MOD) Sum[i] -= MOD;}
    }
    register unsigned long long TmpA(1);//都不选
    TmpA += Sum[n + Q[T].Quek - Q[T].Quex] - 1;
    if(TmpA >= MOD) TmpA -= MOD;
    TmpA += Sum[Q[T].Quex + Q[T].Quek - 1] - 1;
    if(TmpA >= MOD) TmpA -= MOD;
    for (register unsigned i(Q[T].Quex + Q[T].Quek - 1), TmpFj(0), j(1 + Q[T].Quek); i > Q[T].Quek; --i) {
      while (j <= min(n + Q[T].Quek - Q[T].Quex, n + Q[T].Quek + 1 - i)) {TmpFj += f[j],++j; if(TmpFj >= MOD) TmpFj -= MOD;}
      TmpA = (TmpA + (unsigned long long)f[i] * TmpFj) % MOD;
    }
    Q[Q[T].Num].Ans = TmpA;
  }
  for (register unsigned i(1); i <= m; ++i) {
    printf("%u\n", Q[i].Ans);
  }
  return 0;
}

color-50'Ex_Pro.cpp

很遗憾, 这个版本还是 40'.

重新审视我们的转移方程:

f_{i} = \sum_{j = 1}^{j + k \leq i} f_{j}

我们发现, 因为 f_{1 - k} = 1, f_{i \in (1 - k, 0]} = 0. 那么对于 i <= k, 对它做出贡献的值只有 f_{1 - k} = 1 (下标是平移之前的, 可能有负数, 平移后不会越界). 这样就可以改一下方程, 让数组下标从 1 开始, 无需平移.

f_{i} = 1 + \sum_{j = 1}^{j \leq \max(i - k, 1)} f_{j}

方程的正确性是这样保证的: 原来的 f_{1 - k} = 1 所转移的情况是除了 i 点涂黑, 其它的点都留白的情况. 对于 f_{i\in[1, n]}, 显然这种情况都存在, 所以就拿出来当一个边界条件讨论, 避免了更多的转移.

所以这次更新是对代码难度的更新, 之前总是算下标恶心死人.

unsigned n, m, Ans(0), f[100005], Sum[100005];
char flg(0);
struct Que {
  unsigned Quex, Quek, Num, Ans;
  inline const char operator<(const Que &x) const{
    return (this->Quek ^ x.Quek) ? (this->Quek > x.Quek) : (this->Quex < x.Quex);
  }
}Q[100005];
int main() {
  n = RD(), m = RD();
  for (register unsigned i(1); i <= m; ++i) {
    Q[i].Quex = RD(), Q[i].Quek = RD(), Q[i].Num = i;
  }
  sort(Q + 1, Q + m + 1);
  for (register unsigned T(1); T <= m; ++T) {
    if(Q[T].Quek ^ Q[T - 1].Quek){
      memset(f, 0, sizeof(f)), Sum[0] = 0;
      for (register unsigned i(1), j(1), TmpFj(1); i <= n; ++i) {
        while (j + Q[T].Quek <= i) {TmpFj += f[j], ++j; if(TmpFj >= MOD) TmpFj -= MOD;}
        f[i] = TmpFj;
      }
      for (register unsigned i(1); i <= n; ++i) {Sum[i] = Sum[i - 1] + f[i]; if(Sum[i] >= MOD) Sum[i] -= MOD;}
    }
    register unsigned long long TmpA(1);//都不选
    TmpA += Sum[n - Q[T].Quex];//不选左 
    if(TmpA >= MOD) TmpA -= MOD;
    TmpA += Sum[Q[T].Quex - 1];//不选右 
    if(TmpA >= MOD) TmpA -= MOD;
    for (register unsigned i(Q[T].Quex - 1), j(1), AddDown; i; --i) {
      AddDown = n - max(Q[T].Quex, i + Q[T].Quek - 1);
      if(AddDown > 0x3f3f3f3f) {AddDown = 0;}
      TmpA = (TmpA + (unsigned long long)f[i] * Sum[AddDown]) % MOD;
    }
    Q[Q[T].Num].Ans = TmpA;
  }
  for (register unsigned i(1); i <= m; ++i) printf("%u\n", Q[i].Ans);
  return 0;
}

color-50'Ex_Pro_Max.cpp

这个版本无愧它 Pro Max 的称号, 得了 60', 这是因为对求答案时的部分进行了剪枝, 因为有时候, 对于 i + k <= x, j 可以随便选, 不用枚举, 可以前缀和优化掉, 对于 x > k 的情况, i \in [1, x - k] 也可以随便选, 可以优化, 所以询问复杂度变成 O(n - 2k), 相当于优化了很大的常数.

unsigned n, m, Ans(0), f[100005], Sum[100005];
char flg(0);
struct Que {
  unsigned Quex, Quek, Num, Ans;
  inline const char operator<(const Que &x) const{
    return (this->Quek ^ x.Quek) ? (this->Quek < x.Quek) : (this->Quex < x.Quex);
  }
}Q[100005];
int main() {
  n = RD(), m = RD();
  for (register unsigned i(1); i <= m; ++i) {
    Q[i].Quex = RD(), Q[i].Quek = RD(), Q[i].Num = i;
  }
  sort(Q + 1, Q + m + 1);
  for (register unsigned T(1); T <= m; ++T) {
    if(Q[T].Quek ^ Q[T - 1].Quek){
      memset(f, 0, sizeof(f)), Sum[0] = 0;
      for (register unsigned i(1), j(1), TmpFj(1); i <= n; ++i) {
        while (j + Q[T].Quek <= i) {TmpFj += f[j], ++j; if(TmpFj >= MOD) TmpFj -= MOD;}
        f[i] = TmpFj;
      }
      for (register unsigned i(1); i <= n; ++i) {Sum[i] = Sum[i - 1] + f[i]; if(Sum[i] >= MOD) Sum[i] -= MOD;}
    }
    register unsigned long long TmpA(1);//都不选
    TmpA += Sum[n - Q[T].Quex];//不选左 
    if(TmpA >= MOD) TmpA -= MOD;
    TmpA += Sum[Q[T].Quex - 1];//不选右 
    if(TmpA >= MOD) TmpA -= MOD;
    if(Q[T].Quex + 1 > Q[T].Quek) {
      if(Q[T].Quek < 2) TmpA = (TmpA + (unsigned long long)Sum[Q[T].Quex - 1] * Sum[n - Q[T].Quex]) % MOD;
      else {
        TmpA = (TmpA + (unsigned long long)(Sum[Q[T].Quex - Q[T].Quek + 1]) * Sum[n - Q[T].Quex]) % MOD;
        for (register unsigned i(Q[T].Quex - 1), AddDown; i > Q[T].Quex - Q[T].Quek + 1; --i) {
          AddDown = n + 1 - i - Q[T].Quek;
          if(AddDown > 0x3f3f3f3f) AddDown = 0;
          TmpA = (TmpA + (unsigned long long)f[i] * Sum[AddDown]) % MOD;
        }
      }
    } else {
      for (register unsigned i(Q[T].Quex - 1), AddDown; i; --i) {
        AddDown = n - max(Q[T].Quex, i + Q[T].Quek - 1);
        if(AddDown > 0x3f3f3f3f) AddDown = 0;
        TmpA = (TmpA + (unsigned long long)f[i] * Sum[AddDown]) % MOD;
      }
    }
    Q[Q[T].Num].Ans = TmpA;
  }
  for (register unsigned i(1); i <= m; ++i) printf("%u\n", Q[i].Ans);
  return 0;
}

color-70'Ex_Pro_Max_Ti.cpp

这个 70' 非常的丢人, 因为它只有 60'.

优化力度不大, 代码方面减少了讨论, 将两种情况合为一种, 因为两种唯一的区别是枚举 i 的上界. 时间方面只是剪枝了一下, 利用了求答案时利用下标 AddDown 的单调性, 实现了 AddDown = 0 的情况自动跳过, 也体现在 i 的枚举上界上, 询问的复杂度变得十分玄学 O(k) or O(x) or O(n - x) or O(n - k)... 但是它短呀!

unsigned n, m, Ans(0), f[100005], Sum[100005];
char flg(0);
struct Que {
  unsigned Quex, Quek, Num, Ans;
  inline const char operator<(const Que &x) const{
    return (this->Quek ^ x.Quek) ? (this->Quek < x.Quek) : (this->Quex < x.Quex);
  }
}Q[100005];
int main() {
  n = RD(), m = RD();
  for (register unsigned i(1); i <= m; ++i) Q[i].Quex = RD(), Q[i].Quek = RD(), Q[i].Num = i;
  sort(Q + 1, Q + m + 1);
  for (register unsigned T(1); T <= m; ++T) {
    if(Q[T].Quek ^ Q[T - 1].Quek){
      memset(f, 0, sizeof(f)), Sum[0] = 0;
      for (register unsigned i(1), j(1), TmpFj(1); i <= n; ++i) {
        while (j + Q[T].Quek <= i) {TmpFj += f[j], ++j; if(TmpFj >= MOD) TmpFj -= MOD;}
        f[i] = TmpFj;
      }
      for (register unsigned i(1); i <= n; ++i) {Sum[i] = Sum[i - 1] + f[i]; if(Sum[i] >= MOD) Sum[i] -= MOD;}
    }
    register unsigned long long TmpA(1);//都不选
    register unsigned Flor(min(Q[T].Quex - 1, n + 1 - Q[T].Quek)), Ceil(0);
    TmpA += Sum[n - Q[T].Quex];//不选左 
    if(TmpA >= MOD) TmpA -= MOD;
    TmpA += Sum[Q[T].Quex - 1];//不选右 
    if(TmpA >= MOD) TmpA -= MOD;
    if(Q[T].Quex + 1 > Q[T].Quek)
      Ceil = Q[T].Quex - Q[T].Quek + 1, TmpA = (TmpA + (unsigned long long)Sum[Q[T].Quex - max(Q[T].Quek - 1, _1)] * Sum[n - Q[T].Quex]) % MOD;
    for (register unsigned i(Flor), AddDown(n + 1 - i - Q[T].Quek); i > Ceil; --i, ++AddDown) TmpA = (TmpA + (unsigned long long)f[i] * Sum[AddDown]) % MOD;
    Q[Q[T].Num].Ans = TmpA;
  }
  for (register unsigned i(1); i <= m; ++i) printf("%u\n", Q[i].Ans);
  return 0;
}

color-70'Ex_Pro_Max_Ti_X.cpp

重新审视这个询问的过程, 发现所有的方案数 Sum_i + 1, 减去 x 涂黑的方案数 f_x f_{n - x + 1}, 就是不涂 x 的方案数.

所以变成了 O(1) 询问. 这是复杂度的巨大飞跃, 也是代码的进一步缩减, 但是更遗憾的是, 它还是只有 60'

unsigned n, m, Ans(0), f[100005], Sum[100005];
char flg(0);
struct Que {
  unsigned Quex, Quek, Num, Ans;
  inline const char operator<(const Que &x) const{
    return (this->Quek ^ x.Quek) ? (this->Quek < x.Quek) : (this->Quex < x.Quex);
  }
}Q[100005];
int main() {
  n = RD(), m = RD();
  for (register unsigned i(1); i <= m; ++i)
    Q[i].Quex = RD(), Q[i].Quek = RD(), Q[i].Num = i;
  sort(Q + 1, Q + m + 1);
  for (register unsigned T(1); T <= m; ++T) {
    if(Q[T].Quek ^ Q[T - 1].Quek){
      memset(f, 0, sizeof(f)), Sum[0] = 0;
      for (register unsigned i(1), j(1), TmpFj(1); i <= n; ++i) {
        while (j + Q[T].Quek <= i) {TmpFj += f[j], ++j; if(TmpFj >= MOD) TmpFj -= MOD;}
        f[i] = TmpFj;
      }
      for (register unsigned i(1); i <= n; ++i) {Sum[i] = Sum[i - 1] + f[i]; if(Sum[i] >= MOD) Sum[i] -= MOD;}
    }
    Q[Q[T].Num].Ans = (MOD + (Sum[n] + 1) - ((unsigned long long)f[Q[T].Quex] * f[n - Q[T].Quex + 1] % MOD));
    if(Q[Q[T].Num].Ans >= MOD) Q[Q[T].Num].Ans -= MOD;
  }
  for (register unsigned i(1); i <= m; ++i) printf("%u\n", Q[i].Ans);
  return 0;
}

color-70'Ex_Pro_Max_Ti_X_S.cpp

这个 70' 实测得了 80'. (No -O2) 也是全场唯一的 80' (为什么我总是得这么奇怪的分啊?)

这是我考试时最后一个版本, 这份代码主要是对 DP 的过程进行剪枝, 因为打表可得, 对于某个 k, f_{i \in [1, k]} 等于 1. 又因为排序后 k 单增, 所以我们自然不用每次再求一遍 f_{i \in [1, k]} 了, 复杂度变成 O(n - k), 对于 k 大的情况下理论上能将整个程序复杂度优化 50\% 左右. 所以总复杂度 O(nlogn + \frac {nk}2 + m).

unsigned n, m, Ans(0), f[100005], Sum[100005];
char flg(0);
struct Que {
  unsigned Quex, Quek, Num, Ans;
  inline const char operator<(const Que &x) const{
    return (this->Quek ^ x.Quek) ? (this->Quek < x.Quek) : (this->Quex < x.Quex);
  }
}Q[100005];
int main() {
  n = RD(), m = RD();
  for (register unsigned i(1); i <= m; ++i)
    Q[i].Quex = RD(), Q[i].Quek = RD(), Q[i].Num = i;
  sort(Q + 1, Q + m + 1);
  for (register unsigned T(1); T <= m; ++T) {
    if(Q[T].Quek ^ Q[T - 1].Quek){
      for (register unsigned i(Q[T - 1].Quek + 1); i <= Q[T].Quek; ++i) f[i] = 1, Sum[i] = i;
      for (register unsigned i(Q[T].Quek + 1); i <= n; ++i) {
        f[i] = Sum[i - Q[T].Quek] + 1;
        Sum[i] = Sum[i - 1] + f[i]; if(Sum[i] >= MOD) Sum[i] -= MOD;
      }
    }
    Q[Q[T].Num].Ans = (MOD + (Sum[n] + 1) - ((unsigned long long)f[Q[T].Quex] * f[n - Q[T].Quex + 1] % MOD));
    if(Q[Q[T].Num].Ans >= MOD) Q[Q[T].Num].Ans -= MOD;
  }
  for (register unsigned i(1); i <= m; ++i) printf("%u\n", Q[i].Ans);
  return 0;
}

color-100'Ex_Pro_Max_Ti_X_Ultra_Extreme.cpp

在写正解之前, 先来看一下以张业琛为代表的选手的 O(\frac{nm}{k}) 做法. 我一听也很疑惑, 我的算法 k 在分子上, 为什么你的 k 在分子上?

我们知道一个黑点前面一定有 k - 1 个连续的白点, 所以我们可以把这些白点和对应的黑点绑到一起, 成为一个长度为 k 的段, 值得一提的是, 由于第一个黑点前面不一定有 k - 1 个白点, 所以可以在格子 1 前面加 k - 1 的格子, 可以作为容纳第一个黑点对应白点的位置, 这样我们就有最多 \lfloor \frac{n + k - 1}{k} \rfloor = \lceil \frac nk \rceil 个黑点了.

考虑有 i 个点, 那么它们占用的长度是 ki, 则还剩下 n + k - 1 - ki 个自由的, 没有约束的白点, 像放哪放哪. 这时, 把黑点加上它们对应的尾巴看成一个点, 和自由白点加在一起做组合数即可求出方案数. 点数是 n + k - 1 - ki + i, 从这些点中选 i 个点定为带尾巴的黑点, 剩下的是自由白点的方案数是 \binom{n + k - 1 - ki + i}{i}.

对于 i \in [1, \lfloor \frac{n + k - 1}{k} \rfloor] 求 \binom{n + k - 1 - ki + i}{i}, 就能得到对于 n 长度和 k 间隔没有约束条件的合法涂色方案数.

接下来考虑 x 点为白的情况, 仍然是前面的想法, 即所有的情况减去 x 为黑的情况.

求 x 为黑的情况, 我们知道 i \in [x - k + 1, x - 1] \cup [x + 1, x + k - 1] 必须是白点. 所以 x 右边最多有 \lfloor \frac{n - x}{k} \rfloor, 左边最多有 \lfloor \frac{x - 1 + k - 1 - k + 1}{k} \rfloor = \lfloor \frac{x - 1}{k} \rfloor. 对于 i > x 由于黑点的尾巴在左边, 所以带尾巴的黑点可以贴脸放, 而且不需要像求整段一样在左端加上 k - 1 个点, 则 x 右边放 i 个黑点的合法方案数为 \binom {n - x - ki + i}{i}, 则 x 的左边放 i 个的合法方案数为 \binom {x - 1 - ki + i}{i}.

也就是说, 对于询问 x, k, 答案是:

\Bigg(\sum_{i = 1}^{i \leq \lfloor \frac{n + k - 1}{k} \rfloor}\dbinom {n + k - 1 - ki + i}{i}\Bigg) - \Bigg(\sum_{i = 1}^{i \leq \lfloor \frac{n - x}{k} \rfloor}\dbinom {n - x - ki + i}{i}\Bigg) * \Bigg(\sum_{i = 1}^{i \leq \lfloor \frac{x - 1}{k} \rfloor}\dbinom {x - 1 - ki + i}{i}\Bigg)

只要可以 O(1) 求二项式系数, 我们就可以 O(\frac{n}{k}) 回答询问了.

众所周知, 二项式系数:

\binom {a}{b} = \frac{a!}{b!(a - b)!}

我们只要预处理出 i! 和 inv_{i!} 即可, O(n) 求阶乘没问题, 主要问题是逆元.

要预处理 inv_{i!}, i \in [1, n], 我们需要先用快速幂求出 inv_{n!}.

假设 inv_{i!} 已经求出, 要求 inv_{(i - 1)!} 使得 (i - 1)!inv_{(i - 1)!} \equiv 1(\bmod p).

则 i!inv_{(i - 1)!} \equiv i(\bmod p), 又因为 i!inv_{i!} \equiv 1(\bmod p), 所以 inv_{(i - 1)!} \equiv inv_{i!} * i (\bmod p).

这样, 总的复杂度就是 O(\frac {nm}k) 了.

接下来考虑正解.

我们现在有算法可以做到 O(nlogn + \frac {nk}2 + m), 也有算法能做到 O(\frac {nm}k). 所以可以数据分治, 对于 k \leq \sqrt n 的询问, 用前一种算法, 对于 k > \sqrt n 的做法, 用后一种做法, 这样, 最坏的复杂度是 O(nlogn + (n + m) \sqrt n).

最后是代码:

unsigned n, m, Ans(0), f[100005], Sum[100005], T(1), Sq;
unsigned long long Inv[200005], Fac[200005];
char flg(0);
struct Que {
  unsigned Quex, Quek, Num, Ans;
  inline const char operator<(const Que &x) const{
    return (this->Quek ^ x.Quek) ? (this->Quek < x.Quek) : (this->Quex < x.Quex);
  }
}Q[100005];
int main() {
  n = RD(), m = RD(), Sq = sqrt(n);
  for (register unsigned i(1); i <= m; ++i) Q[i].Quex = RD(), Q[i].Quek = RD(), Q[i].Num = i;
  sort(Q + 1, Q + m + 1), Fac[0] = 1;
  for (register unsigned i(1); i <= n + Q[m].Quek; ++i) Fac[i] = Fac[i - 1] * i % MOD;
  register unsigned TmpM(MOD - 2);
  register unsigned long long TmpFac(Fac[n + Q[m].Quek]);
  Inv[n + Q[m].Quek] = 1;
  while (TmpM) {
    if(TmpM & 1) Inv[n + Q[m].Quek] = Inv[n + Q[m].Quek] * TmpFac % MOD;
    TmpFac = TmpFac * TmpFac % MOD, TmpM >>= 1;}
  for (register unsigned i(n + Q[m].Quek - 1); i < 0x3f3f3f3f; --i) Inv[i] = Inv[i + 1] * (i + 1) % MOD;
  for (; Q[T].Quek <= Sq && T <= m; ++T) {
    if(Q[T].Quek ^ Q[T - 1].Quek){
      for (register unsigned i(Q[T - 1].Quek + 1); i <= Q[T].Quek; ++i) f[i] = 1, Sum[i] = i;
      for (register unsigned i(Q[T].Quek + 1); i <= n; ++i){
        f[i] = Sum[i - Q[T].Quek] + 1, Sum[i] = Sum[i - 1] + f[i]; if(Sum[i] >= MOD) Sum[i] -= MOD;}
    }
    Q[Q[T].Num].Ans = (MOD + (Sum[n] + 1) - ((unsigned long long)f[Q[T].Quex] * f[n - Q[T].Quex + 1] % MOD));
    if(Q[Q[T].Num].Ans >= MOD) Q[Q[T].Num].Ans -= MOD;
  }
  for (register unsigned long long TmpTotal(1), TmpLe(1), TmpRi(1); T <= m; ++T) {
    for (register unsigned i((n + Q[T].Quek - 1)/ Q[T].Quek), Len(n + Q[T].Quek - 1 - Q[T].Quek * i + i); i; --i, Len += (Q[T].Quek - 1))
      TmpTotal = (TmpTotal + (Fac[Len] * Inv[i] % MOD) * Inv[Len - i]) % MOD;
    for (register unsigned i((n - Q[T].Quex)/ Q[T].Quek), Len(n - Q[T].Quex - Q[T].Quek * i + i); i; --i, Len += (Q[T].Quek - 1))
      TmpLe = (TmpLe + (Fac[Len] * Inv[i] % MOD) * Inv[Len - i]) % MOD;
    for (register unsigned i((Q[T].Quex - 1) / Q[T].Quek), Len(Q[T].Quex - 1 - Q[T].Quek * i + i); i; --i, Len += (Q[T].Quek - 1))
      TmpRi = (TmpRi + (Fac[Len] * Inv[i] % MOD) * Inv[Len - i]) % MOD;
    Q[Q[T].Num].Ans = MOD + TmpTotal - (TmpLe * TmpRi % MOD), TmpTotal = TmpLe = TmpRi = 1;
    if(Q[Q[T].Num].Ans >= MOD) Q[Q[T].Num].Ans -= MOD;
  }
  for (register unsigned i(1); i <= m; ++i) printf("%u\n", Q[i].Ans);
  return 0;
}