题解
好难啊呜呜,怎么想的到。
三次方,那就相当于枚举可重复的三个相同的子序列的答案。
于是我们记 $f_{i,j,k}$ 表示第一个子序列最后一位为原序列中的第 $i$ 个,第二个子序列为 $j$ ,第三个为 $k$ 的方案数。因此只有当 $a_i=a_j=a_k$ 才有值。
转移为 $f_{i,j,k}=\Sigma f_{i',j',k'}$ ,其中 $i'<i,j'<j,k'<k$ ,且 $M_{a_{i'},a_{i}}=1$ ,这样是 $O(n^6)$ 。
我们考虑前缀和优化,记 $s_{j,k}=\Sigma f_{i',j',k'}$ ,并且 $M_{a_{i'},a_{j}}=1$ ,这样 $s$ 和 $f$ 就可以互相转移。
效率: $O(n^3)$ 。
代码
#include <bits/stdc++.h> using namespace std; const int N=202,P=1e9+7;; int n,a[N],ans,f[N][N],s[N][N],T; char m[N][N]; void work(){ scanf("%d",&n);ans=0; for (int i=1;i<=n;i++) scanf("%d",&a[i]); for (int i=1;i<=n;i++) scanf("%s",m[i]+1); for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) f[i][j]=s[i][j]=0; for (int i=1;i<=n;i++){ for (int j=1;j<=n;j++) for (int k=1;k<=n;k++) (f[j][k]+=((f[j-1][k]+f[j][k-1])%P+(P-f[j-1][k-1])%P)%P)%=P; for (int j=1;j<=n;j++) for (int k=1;k<=n;k++) if (m[a[i-1]][a[j]]=='1') (s[j][k]+=f[j-1][k-1])%=P; for (int j=1;j<=n;j++) for (int k=1;k<=n;k++){ if (a[i]==a[j] && a[i]==a[k]) f[j][k]=s[j][k]+1; else f[j][k]=0; (ans+=f[j][k])%=P; } } printf("%d\n",ans); } int main(){ for (scanf("%d",&T);T--;work()); return 0; }