CF 256E Lucky Arrarys 线段树+DP
在w数组中为1。数组初始为0,问有多少种排列方式使数组是Lucky的。并且每次更新之后都要给出总的方案数。
动态规划可以求相邻两个区间合并之后的结果
f(i, j)表示当前区间以i开头,以j结尾的总方案数。那么配合更新操作,我们就可以用线段树来维护。树中每个节点上面都有一个f数组记录当前区间的方案数。对于每次更新后的询问,只需对根节点求和即可。
状态转移见代码。
#include <cstdio> #include <cstring> #include <algorithm> #include <iostream> #include <cmath> using namespace std; #define N 80000 #define Mod 777777777 #define For(i, s, t) for(int i=s; i<=t; i++) typedef long long ll; ll f[N<<2][4][4]; int n, m, w[4][4]; void Up(int rt) { For(i, 1, 3) For(j, 1, 3) { f[rt][i][j] = 0; For(p, 1, 3) For(q, 1, 3) f[rt][i][j] += w[p][q] ? f[rt<<1][i][p]*f[rt<<1|1][q][j] : 0; f[rt][i][j] %= Mod; } } void build(int L, int R, int rt) { if (L == R) { For(i, 1, 3) For(j, 1, 3) f[rt][i][j] = (i==j)?1:0; return ; } int Mid = (L + R) >> 1; build(L, Mid, rt<<1); build(Mid+1, R, rt<<1|1); Up(rt); } void update(int v, int t, int L, int R, int rt) { if (L == R) { if (t == 0) { For(i, 1, 3) For(j, 1, 3) f[rt][i][j] = (i==j)?1:0; } else { For(i, 1, 3) f[rt][i][i] = (i==t)?1:0; } return ; } int Mid = (L + R) >> 1; if (v <= Mid) update(v, t, L, Mid, rt<<1); else update(v, t, Mid+1, R, rt<<1|1); Up(rt); } int main() { scanf("%d%d", &n, &m); For(i, 1, 3) For(j, 1, 3) scanf("%d", &w[i][j]); build(1, n, 1); int v, t; ll ans = 0; while(m--) { scanf("%d%d", &v, &t); update(v, t, 1, n, 1); ans = 0; For(i, 1, 3) For(j, 1, 3) ans += f[1][i][j]; cout << ans % Mod << endl; } return 0; }
补充:软件开发 , C++ ,