大概是 ABC 有史以来最难的 F 题？

· · 题解

思路

相邻两个茶壶中至少有一个装茶，等同于不能有两壶相邻的咖啡。我们考虑朴素的动态规划，f_{i,j,0/1} 表示 i 个茶壶，其中有 j 壶咖啡，最后一壶是茶/咖啡的方案数。递推式为（当前不考虑 a_i 的限制）：

f_{i,j,0}\leftarrow f_{i-1,j,0}+f_{i-1,j,1}\\ f_{i,j,1}\leftarrow f_{i-1,j-1,0}

发现这个式子很像组合数的递推式啊，简单思考发现令 G_{i,j} 为 i 壶中有 j 壶为咖啡的方案数，则有 G_{i,j}=\begin{pmatrix}i-j+1\\j\end{pmatrix}。这个是插板法经典结论就不在这里细说了。

接下来我们考虑在两个相邻的有值的 a_i 之间进行状态转移，接下来我们令 f_{i,0/1} 表示前 i 个茶壶，有 a_i 个装了咖啡，最后一壶是茶/咖啡的方案数。考虑由 i 转移到 j，令 l=j-i,d=a_j-a_i，有：

f_{i,0}\times G_{l-1,d}\to f_{j,0}

因为我们限制了第 j 壶是茶，所以要在剩下 l-1 个位置中选出 d 壶咖啡。

f_{i,0}\times G_{l-2,d-1}\to f_{j,1}

因为我们限制了第 j 壶是咖啡，所以第 j-1 壶是茶，剩下 l-2 个位置中有 d-1 壶咖啡。

f_{i,1}\times G_{l-2,d}\to f_{j,0}

第 i+1 个位置一定是茶，第 j 个位置为茶，剩下 l-2 个位置中有 d 壶咖啡。

f_{i,1}\times G_{l-3,d-1}\to f_{j,1}

第 i+1 个位置一定是茶，第 j 个位置为咖啡，所以第 j-1 个位置为茶，剩下 l-3 个位置中有 d-1 壶咖啡。

发现可以写成矩阵乘法的形式：

\begin{bmatrix} f_{i,0} & f_{i,1} \end{bmatrix} \times \begin{bmatrix} G_{l-1,d} & G_{l-2,d-1}\\ G_{l-2,d} & G_{l-3,d-1} \end{bmatrix} = \begin{bmatrix} f_{j,0} & f_{j,1} \end{bmatrix}

然后就比较明了了，我们对每个有值的 a_X 挂一个矩阵，求值就是用 \begin{bmatrix}1 & 0\end{bmatrix} 和依次乘起来的所有矩阵相乘即可。

结束了吗？没有结束，最后还有一段是没有咖啡的个数的限制的。手玩或者简单推可以发现长度为 i 的没有个数限制的填充方案数为 F_{i+2}，F 为斐波那契数列。

整理可得令上面求值那一步得到的矩阵是 \begin{bmatrix}A & B\end{bmatrix}，最后一个有值的 a_i 为 a_{lst}，则答案为 A\times F_{n-lst+2}+B\times F_{n-lst+1}。

挂矩阵的操作用一个线段树维护矩阵乘法即可，另开一个 set 记录有值的 a_X 的位置，易知修改 a_X 只会影响 X 和 X 后第一个有值的位置的矩阵，做单点修改就行。

我们视矩乘复杂度为常数，时间复杂度为 O(N+Q\log N)。

代码

参考代码使用了 AtCoder 库中的线段树和 vector 实现矩阵。不建议使用 vector 实现矩乘，否则需要大力卡常。

#include<bits/stdc++.h>
#include<atcoder/all>
#define ll long long
#define fr(a,b,c) for(int a = b;a <= c;a ++)
using namespace std;
template<typename T> void read(T &x){x = 0;char c = getchar();int f = 1;while(!isdigit(c)){if(c == '-') f = -1;c = getchar();}while(isdigit(c)) x = x * 10 + c - '0',c = getchar();x *= f;}
const int N = 300000;
const ll MOD = 998244353;
int n,q,a[N],x,y;
ll fct[N],inv[N],F[N];
set<int> hn;//维护有值位置的集合
ll qp(ll a,ll b){if(!b) return 1ll;ll c = qp(a,b >> 1);c = c * c % MOD;if(b & 1) c = c * a % MOD;return c;}//快速幂
vector<vector<ll>> mul(vector<vector<ll>> a,vector<vector<ll>> b){//矩乘函数
  int n = a.size(),m = b.size(),x = b[0].size();
  vector<vector<ll>>c(n,vector<ll>(x,0));
  fr(k,0,m - 1) fr(i,0,n - 1) fr(j,0,x - 1) c[i][j] = (c[i][j] + a[i][k] * b[k][j]) % MOD;
  return c;
}
vector<vector<ll>> e(){return {{1ll,0ll},{0ll,1ll}};}//单位矩阵
ll C(ll n,ll m){//组合数
  if(m < 0 || m > n) return 0;
  return fct[n] * inv[m] % MOD * inv[n - m] % MOD;
}
ll g(ll a,ll b){return C(a - b + 1,b);}
inline void cal(atcoder::segtree<vector<vector<ll>>,mul,e> &sgt,int y){//更新 y 位置的矩阵
  auto it = hn.find(y);
  int x = it == hn.begin() ? 0 : *-- it;
  int len = y - x,d = a[y] - a[x];
  sgt.set(y - 1,{{g(len - 1,d),g(len - 2,d - 1)},{g(len - 2,d),g(len - 3,d - 1)}});
}
int main(){
  fct[0] = F[1] = 1;
  fr(i,1,N - 1) fct[i] = fct[i - 1] * i % MOD;
  fr(i,2,N - 1) F[i] = (F[i - 1] + F[i - 2]) % MOD;//预处理斐波那契数列
  inv[N - 1] = qp(fct[N - 1],MOD - 2);
  for(int i = N - 1;i;i --) inv[i - 1] = inv[i] * i % MOD;//预处理阶乘及其逆元
  cin.tie(0)->sync_with_stdio(0);
  cin >> n >> q;
  atcoder::segtree<vector<vector<ll>>,mul,e> sgt(n);
  while(q --){
    cin >> x >> y;
    sgt.set(x - 1,e()),hn.erase(x),a[x] = y;
    if(~y){
      hn.emplace(x);
      cal(sgt,x);
    }
    auto it = hn.upper_bound(x);
    if(it != hn.end()) cal(sgt,*it);
    if(hn.empty()){//特判没有位置有值
      printf("%lld\n",F[n + 2]);
      continue;
    }
    auto ans = mul({{1,0}},sgt.prod(0,n));
    int lst = *-- hn.end();
    printf("%lld\n",(ans[0][0] * F[n - lst + 2] + ans[0][1] * F[n - lst + 1]) % MOD);
  }
  return 0;
}