USACO 好难啊
# 题面
$n$ 个点之间有若干条有向边连接,保证边 $u\to v$ 不超过一条,但可能同时有 $u\to v,v\to u$,也可以有自环。
你有 $m$ 个按钮编号为 $1\sim m$,最初所有按钮都「可用」。当你按下按钮 $x$ 后,按钮 $x$ 会被「禁用」(你不能按当前被禁用的按钮),同时按钮 $1\sim x-1$ 全部恢复成可用。
给定 $Q$ 组询问,每组询问给出 $s,t,b_s,b_t$,表示:你从 $s$ 点出发,开始时强制按钮 $b_s$ 变为「禁用」;你需要按一个按钮,然后走一步;求有多少种方案,满足当你到达 $t$ 点时,你上一次按的按钮为 $b_t$。
数据规模:$n,m,q\le60$。
# 解析
暂时不管 $b_s,b_t$ 的限制。
根据规则,我们按下按钮 $i$ 后,小于 $i$ 的按钮都会重置,于是比较自然地想到计算子问题「只用小于等于 $i$ 的按钮」。
定义朴素 DP 状态:$f(i,s,t)$ 表示「只按小于等于 $i$ 的按钮,从 $s$ 跑到 t$ 有多少种方案」。记 $g(s,t)$ 表示是否存在边 $s\to t$,存在为 $1$,不存在为 $0$。
考虑 $f$ 的转移 —— 「只按小于等于 $i$ 的按钮」,意味着当我们按下 $i$ 后,$i$ 就永远禁用了,于是可以先分两类再拆三段:
- 不按按钮 $i$:$f(i,s,t)\gets f(i-1,s,t)$(“$\gets$” 在这里表示 “贡献”);
- 按按钮 $i$,可以拆成三段:
- 先在 $1\sim i-1$ 中瞎乱按:$f(i-1,s,x)$;
- 按按钮 $i$:$e(x,y)$;
- 再在 $1\sim i-1$ 中瞎乱按:$f(i-1,y,t)$。
记矩阵 $E$:$E_{ij}=e(i,j)$;$F^i$:$F^i_{st}=f(i,s,t)$。
矩阵编号写成下标太难受了 ::>_<::
于是 DP 的转移方程就可以写成:
可以 $\mathcal{O}(n^4)$ 处理出所有的 DP 值。
再考虑 $b_s,b_t$ 的限制。仍然分析「只按小于等于 $b_{mx}$ 的按钮」这样的子问题,不过这次要求一定要按 $b_{mx}$。
把方案从按下 $b_{mx}$ 这个位置分成两半计算,因为 $b_{mx}$ 既然是按的最大的按钮,肯定只能按一次。
定义 DP 状态 $p(i,x)$ 表示:$b_{mx}=i$ 时,从 $s$ 出发,按钮初始状态为“只有 $b_s$ 禁用”,每走一步按一次按钮(这样方便理解一些),走到 $x$ 时按下 $b_{mx}$ 的方案数。
根据定义,DP 初值为 $p(b_s,s)=1$。一种方案可以看成两部分:
- 只在小于等于 $j$ 的按钮中乱按,从 $s$ 跑到 $y$,且最后按下按钮 $j$(此时小于等于 $j-1$ 的按钮重置);
- 在小于等于 $j-1$ 的按钮中乱按,从 $y$ 跑到 $z$;
- 按下 $i$,从 $z$ 跑到 $x$,结束。
同样,写成矩阵的形式,一个一行 $n$ 列的矩阵。$P^i$:$P^i_{1j}=p(i,j)$。
注意到 $P$ 是 $1\times n$ 的,上述转移可以 $\mathcal{O}(n^3)$ 计算出所有的 $p(i,x)$。
再推导后一半:按下按钮 $b_{mx}$ 最后按 $b_t$。记 $q(i,x)$ 表示 $b_{mx}=i$ 时,从 $x$ 出发,按钮初始状态为“只有 $b_{mx}$ 为禁用”,按一次按钮走一步,走到 $t$ 且最后一次按 $b_t$ 的方案数。
答案则为
注意到 $q$ 和 $p$ 在某种程度上是高度对称的,我们可以较为简单地得到 $q$ 的转移 —— 基本上就是把整个过程倒过来想。
- 最后在小于等于 $j-1$ 的按钮中乱按,从 $z$ 跑到了 $t$;
- 之前在小于等于 $j$ 的按钮中乱按,最后一次按了按钮 $j$,从 $y$ 跑到了 $z$;
- 最开始按了按钮 $i$,从 $x$ 跑到了 $y$。
同理可以 $\mathcal{O}(n^3)$ 求解。
所以总复杂度为 $\mathcal{O}(n^4+Qn^3)$,写成矩阵可以让代码略微好看一些……
# 源代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94
| #include<cstdio> #include<cstring> #include<algorithm> using namespace std;
inline int rin(int &r){ int b=1,c=getchar();r=0; while(c<'0' || '9'<c) b=c=='-'?-1:b,c=getchar(); while('0'<=c && c<='9') r=(r<<1)+(r<<3)+(c^'0'),c=getchar(); return r*=b; } const int N=65,MOD=1e9+7; #define con(type) const type & inline int add(con(int)a,con(int)b){return a+b>=MOD?a+b-MOD:a+b;} inline int sub(con(int)a,con(int)b){return a-b<0?a-b+MOD:a-b;} inline int mul(con(int)a,con(int)b){return int(1ll*a*b%MOD);} inline int ina_pow(con(int)a,con(int)b){return b?mul(ina_pow(mul(a,a),b>>1),(b&1)?a:1):1;} inline void upd(int &a,con(int)b){a=add(a,b);}
int n,m,nq; char str[N];
struct Matrix{ int mat[N][N]; Matrix(){memset(mat,0,sizeof mat);} inline int* operator [](con(int)i){return mat[i];} Matrix operator *(con(Matrix)b)const{ Matrix c; for(int i=1;i<=n;i++) for(int k=1;k<=n;k++) for(int j=1;j<=n;j++) upd(c.mat[i][j],mul(mat[i][k],b.mat[k][j])); return c; } void operator +=(con(Matrix)b){ for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) upd(mat[i][j],b.mat[i][j]); } }m_tra,m_def[N];
int vs[N][N],vt[N][N],tmp[N],tmp2[N];
int main(){ rin(n),rin(m),rin(nq); for(int u=1;u<=n;u++){ scanf("%s",str+1); for(int v=1;v<=n;v++) m_tra[u][v]=str[v]=='1'; } for(int i=1;i<=n;i++) m_def[0][i][i]=1; for(int i=1;i<=m;i++){ m_def[i]=m_def[i-1]; m_def[i]+=m_def[i-1]*m_tra*m_def[i-1]; } for(int mq=1,bs,bt,s,t;mq<=nq;mq++){ rin(bs),rin(s),rin(bt),rin(t); memset(vs,0,sizeof vs); memset(vt,0,sizeof vt); vs[bs][s]=1; for(int i=1;i<=n;i++) tmp[i]=m_def[bs-1][s][i]; for(int i=bs+1;i<=m;i++){ for(int p=1;p<=n;p++) for(int q=1;q<=n;q++) upd(vs[i][q],mul(tmp[p],m_tra[p][q])); for(int p=1;p<=n;p++) for(int q=1;q<=n;q++) upd(tmp2[q],mul(vs[i][p],m_def[i-1][p][q])); for(int p=1;p<=n;p++) upd(tmp[p],tmp2[p]),tmp2[p]=0; } vt[bt][t]=1; for(int i=1;i<=n;i++) tmp[i]=m_def[bt-1][i][t]; for(int i=bt+1;i<=m;i++){ for(int p=1;p<=n;p++) for(int q=1;q<=n;q++) upd(vt[i][q],mul(tmp[p],m_tra[q][p])); for(int p=1;p<=n;p++) for(int q=1;q<=n;q++) upd(tmp2[q],mul(vt[i][p],m_def[i-1][q][p])); for(int p=1;p<=n;p++) upd(tmp[p],tmp2[p]),tmp2[p]=0; } int ans=0; for(int i=1;i<=m;i++) for(int j=1;j<=n;j++) upd(ans,mul(vs[i][j],vt[i][j])); printf("%d\n",ans); } return 0; }
|
THE END
Thanks for reading!
是灵台菩提的初萌
是神游蝶茧的悸动
是万物的方生方死
鱼跃方成龙
是弹指白驹的飞纵
是刹那朝菌的临终
待天地封冻 可曾怨西风
——《万象霜天》By 赤羽
> Link 万象霜天-Bilibili