2026牛客暑期多校训练营5

2026牛客暑期多校训练营5Problem E.古明地恋与非积辈只有本蒟蒻注意到这个中文名很隐晦吗我们可以打个表Ω(n)指的是这个数可以拆成多少个质数Ω(n)例子g(n)12,3,5,7质数124,6,10,14238,12,18,303416,24,36,405532,48,727664,9611这个时候我们就可以发现Ω(n)Ω(n/lp(n))1 lp就是n的最小质因子。我们可以用质数筛然后标记Ω(n) omega[i * p] omega[i] 1;#includebits/stdc.husingnamespacestd;usinglllonglong;constintMOD998244353;intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);intn,c;cinnc;vectorintis_comp(n1,0);vectorintprimes;vectorintomega(n1,0);for(inti2;in;i){if(!is_comp[i]){primes.push_back(i);omega[i]1;}for(intp:primes){if(1LL*i*pn)break;is_comp[i*p]1;omega[i*p]omega[i]1;if(i%p0)break;}}ll powcc%MOD;ll ans0;for(inti1;in;i){ll g;if(omega[i]1)g1;elseg(ll)primes[omega[i]-2];ans(ansg*powc)%MOD;powcpowc*c%MOD;}coutans\n;return0;}L- Matrix1. 问题本质一次操作 选一条从(1,1)到(n,m)的路径只能向右、向下路径经过的所有格子 1。我们要让所有格子变成同一个数T。设b[i][j] T - a[i][j] 格子 (i,j) 需要的增量操作次数假设为k。目标变成能不能把b拆成k条路径的覆盖和2. 第一个关键观察副对角线副对角线就是满足ij s的一串格子。任何一条 (1,1)→(n,m) 的单调路径都恰好经过每条副对角线上的一个格子。为什么因为路径长度固定是nm-1从ij2到ijnm每条对角线上必须选一个格子而且只能选一个。所以做 k 次操作 ⇒ 每条副对角线上被加的总和 k写成公式对每条副对角线sΣ_{ijs} b[i][j] k这就是必要条件也是后面求T的依据。3. 目标值 T 和操作次数 k 是唯一确定的设副对角线s上的格子数c_s原始元素和A_s那么c_s * T - A_s k 对每条副对角线 s当n,m ≥ 2时前两条副对角线长度不同直接解出唯一答案s2只有(1,1)长度 1 →T - a[1][1] ks3(1,2),(2,1)长度 2 →2T - (a[1][2]a[2][1]) k两式相减T a[1][2] a[2][1] - a[1][1] k T - a[1][1]先检查k ≥ 0T ≥ max(a)即所有b[i][j] ≥ 0只能加不能减每条副对角线都满足c_s * T - A_s k4. 这些条件还不够需要流量可行性b[i][j]表示「有多少条路径经过格子 (i,j)」。多堆路径要能拼起来格子之间的流量必须守恒。5. 流量模型把每个格子当顶点只能向右R或向下D走R[i][j] 从 (i,j) 到 (i,j1) 的流量 D[i][j] 从 (i,j) 到 (i1,j) 的流量流量守恒对每个格子进入 (i,j) 的流量 b[i][j] 从 (i,j) 出去的流量写成R[i][j-1] D[i-1][j] b[i][j] R[i][j] D[i][j]其中越界的项都当 0。如果能找到非负整数R, D满足守恒那么标准结论是DAG 里任意整数流都能分解成若干条从 (1,1) 到 (n,m) 的路径所以可行。6. 消元只用 D 的递推式把R消掉。因为R[i][j] b[i][j] - D[i][j]代入(i,j1)的守恒式R[i][j] D[i-1][j1] b[i][j1] ⇒ b[i][j] - D[i][j] D[i-1][j1] b[i][j1] ⇒ D[i][j] D[i-1][j1] b[i][j] - b[i][j1]这就是核心递推式。边界条件D[0][j] 0 第 0 行上方没有流量 D[i][m] b[i][m] 最后一列只能往下走i n D[n][j] 0 最底行不能再往下走算法逐行从上到下对 i 1..n-1 对 j m-1 到 1 D[i][j] D[i-1][j1] b[i][j] - b[i][j1] 同时检查 D[i][j] ≥ 0 R[i][j] b[i][j] - D[i][j] ≥ 0 最后一列 D[i][m] b[i][m] 最后一行检查 D[n-1][j1] b[n][j] - b[n][j1] 0 要求 D[n][j]0只要有一个检查失败 →-1全部通过 → 输出k。code#includebits/stdc.husingnamespacestd;usinglllonglong;intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);intT;cinT;while(T--){intn,m;cinnm;vectorvectorlla(n,vectorll(m));for(inti0;in;i)for(intj0;jm;j)cina[i][j];// 单行/单列路径唯一所有数必须已经相等if(n1||m1){booloktrue;for(inti0;in;i)for(intj0;jm;j)if(a[i][j]!a[0][0])okfalse;cout(ok?0:-1)\n;continue;}// 目标值由前两条副对角线唯一确定ll targeta[0][1]a[1][0]-a[0][0];ll ktarget-a[0][0];if(k0){cout-1\n;continue;}// 副对角线求和 最大值vectorlldiagSum(nm-1,0);ll maxAa[0][0];for(inti0;in;i)for(intj0;jm;j){diagSum[ij]a[i][j];maxAmax(maxA,a[i][j]);}if(targetmaxA){cout-1\n;continue;}// 每条副对角线的增量必须都等于 kbooloktrue;for(ints0;snm-1ok;s){intlenmin({s1,n,m,nm-1-s});if(len*target-diagSum[s]!k)okfalse;}if(!ok){cout-1\n;continue;}// 流量检查// down[i][j] 从 (i,j) 向下走到 (i1,j) 的路径数// right[i][j] 从 (i,j) 向右走到 (i,j1) 的路径数// right[i][j] b[i][j] - down[i][j]// 递推down[i][j] down[i-1][j1] b[i][j] - b[i][j1]vectorlldownPrev(m,0);// 上一行的 downfor(inti0;i1nok;i){vectorlldown(m);// 当前行的 downfor(intjm-1;j0;--j){ll btarget-a[i][j];// 必须经过 (i,j) 的路径数if(jm-1){down[j]b;// 最后一列只能向下走}else{down[j]downPrev[j1]b-(target-a[i][j1]);}// down 0且 right b - down 0if(down[j]0||(j1mb-down[j]0))okfalse;}downPrev.swap(down);}// 最底行不能再向下要求 down 全为 0for(intj0;j1mok;j)if(downPrev[j1](target-a[n-1][j])-(target-a[n-1][j1])!0)okfalse;cout(ok?k:-1)\n;}return0;}