这个题目看网上好多题解都是直接O(n*m)卡过。我是这么做的。
对于m次操作，统计每个w的次数。然后对每个w做矩阵乘法。
这样直接做矩阵乘法是会TLE的。
又由于这里的矩阵很特殊，一次乘法可以降维成O(n^2)。
--------------------------
怎么降维的可以这样模拟下:
a b c a b c a*a+2bc c*c+2ab b*b+2ac
c a b * c a b = b*b+2ac a*a+2bc c*c+2ab
b c a b c a c*c+2ab b*b+2ac a*a+2bc
注意到原矩阵的每一行(除了第一行)都是上一行向右平移一个单位的结果，而相乘得到的矩阵也满足这个性质。
那么做一次矩阵乘法的时候，就只用算出结果矩阵的第一行，然后下面的每一行直接可由上一行得到。
复杂度降为了O(n^2)。
-------------------------
所以一个总的复杂度<O(n^2 * log1000000 * 100)=8千万.
不到2000msAC了^_^
#include<cstdio>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<string>
#include<vector>
#include<ctype.h>
#include<algorithm>
using namespace std;
typedef long long LL;
#define FF(i,x) for(i=1;i<=x;i++)
const int N = ; double cMat[N][N],retMat[N][N]; void matrixMul1(double A[][N],double B[][N],int a,int b)
{
double buff[N][N]={};
int i,j,k;
FF(i,a) FF(k,a) FF(j,b)
buff[i][j] = buff[i][j] + A[i][k]*B[k][j];
FF(i,a) FF(j,b) B[i][j]=buff[i][j];
} void matrixMul2(double A[][N],double B[][N],int a,int b)
{
double buff[N][N]={};
for(int j=;j<=a;j++)
{
for(int k=;k<=a;k++)
buff[][j]+=A[][k]*B[k][j];
}
for(int i=;i<=a;i++)
{
for(int j=;j<=a;j++) buff[i][j]=buff[i-][j-];
buff[i][]=buff[i-][a];
}
int i,j;
FF(i,a) FF(j,b) B[i][j]=buff[i][j];
} void matrixFastPow(int p,int n)
{
for(;p;p>>=)
{
if( p& ) matrixMul1(cMat,retMat,n,);
matrixMul2(cMat,cMat,n,n);
}
} int amount[]; int main()
{
int n,m,l,r;
int w; while( scanf("%d%d%d%d",&n,&m,&l,&r),n||m||l||r )
{
memset(amount,,sizeof(amount));
for(int i=;i<m;i++)
{
scanf("%d",&w);
amount[w]++;
}
for(int i=;i<=n;i++)
if( i<l || i>r ) retMat[i][]=0.0;
else retMat[i][]=1.0;
for(int i=;i<=;i++)
if( amount[i] )
{
for(int p=;p<=n;p++)
for(int q=;q<=n;q++)
cMat[p][q]=0.0;
for(int j=;j<=n;j++)
{
int a=(j-i);
while( a<= ) a+=n;
int b=(j+i);
while( b>n ) b-=n;
cMat[j][a]+=0.5;
cMat[j][b]+=0.5;
}
matrixFastPow(amount[i],n);
} printf("%.4f\n",retMat[][]);
}
return ;
}