很经典的矩阵快速幂题。
注意,如果裸写的话时间复杂度会是O(n^4*logm),显然不行。
所以,我写这篇题解(?明明就是一个tip一样的东西= =)就是想说:
1. 对称矩阵的乘积还是对称矩阵。(重点是下一个↓↓↓)
2. 这个类似于三对角矩阵一样的矩阵,它的每一行都可由前一行往右平移一位得到,所以只用存储一行就可以存储整个矩阵,并且也只用计算一行就可以得到整个矩阵。
然后,本题就优化完毕了= =
最终时间复杂度为O(n^3*logm)(还是好大有没有,但就是过了我也没办法= =)
#include <cstdio> #include <iostream> #include <cstring> #include <cmath> #include <vector> #include <set> #include <queue> #include <stack> #include <map> #include <algorithm> using namespace std; typedef long long ll; typedef unsigned long long llu; const int mod = 100; const int maxn = 210; const double eps = 1e-6; const double PI = acos(-1.0); int n,m,l,r; int cnt[maxn]; double a[maxn],b[maxn],c[maxn]; inline int read() { int ret=0; char ch=getchar(); while (ch<'0' || ch>'9') ch=getchar(); while (ch>='0' && ch<='9') { ret=ret*10+ch-48; ch=getchar(); } return ret; } int main() { while (scanf("%d%d%d%d",&n,&m,&l,&r)==4 && (n||m||l||r)) { memset(cnt,0,sizeof(cnt)); for (int i=1;i<=m;i++) { int w=read(); w%=n; w=min(w,n-w); cnt[w]++; } if (n==1) { puts("1.0000"); continue; } memset(a,0,sizeof(a)); a[0]=1; for (int w=1;w<=100;w++) { if (!cnt[w]) continue; for (int i=0;i<n;i++) b[i]=0; b[w%n]+=0.5; b[(n-w)%n]+=0.5; while (cnt[w]) { if (cnt[w]&1) { for (int i=0;i<n;i++) { c[i]=0; for (int j=0;j<n;j++) c[i]+=a[j]*b[(j+i)%n]; } for (int i=0;i<n;i++) a[i]=c[i]; } for (int i=0;i<n;i++) { c[i]=0; for (int j=0;j<n;j++) c[i]+=b[j]*b[(i+j)%n]; } for (int i=0;i<n;i++) b[i]=c[i]; cnt[w]>>=1; } } double ans=0; for (int i=l-1;i<r;i++) ans+=a[i]; printf("%.4lf\n",ans); } return 0; }
Robot