矩阵运算。
题意抽象出来，即是求A^k*x(mod m)，其中A是n*n的循环矩阵，x是n维列向量。
很直接的思路是O(n^3*lgk)，但这里n最大500，TLE的。如果利用A是循环矩阵的性质，那么其实每次只要计算第一行就可以了，其他行都可以由第一行移位得到。这样就可以O(n^2*lgk)，实现出来最快500ms。
|
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 |
#include<cstdio> #include<cstring> #define ll long long #define size n<<3 ll n,m,d,e,a[500],b[500],t[500],x[500],y[500]; void init() { ll i,j,k,l; for(i=0;i<n;i++) scanf("%lld",x+i); memset(a,0,size); memset(b,0,size); memset(y,0,size); b[0]=1; for(i=j=0,k=0;k<=d;k++) { a[i]=1; ++i; if(i==n) i=0; a[j]=1; --j; if(j==-1) j=n-1; } } void mul(ll b[],ll a[]) { ll i,j,k,l; memset(t,0,size); for(i=0;i<=n/2;i++) { for(j=0,k=i;j<n;j++) { t[i]+=b[j]*a[k]; ++k; if(k==n) k=0; } t[i]%=m; } for(i=1;i<=n/2;i++) t[n-i]=t[i]; memcpy(b,t,size); } void solve() { ll i,j,k,l; for(i=1;i<=e;i<<=1); for(i>>=1;i;i>>=1) { mul(b,b); if(i&e) mul(b,a); } for(i=0;i<n;i++) for(j=0;j<n;j++) y[i]=(y[i]+b[j]*x[(i+j)%n])%m; for(i=0;i<n-1;i++) printf("%lld ",y[i]); printf("%lld\n",y[n-1]); } int main() { while(~scanf("%lld%lld%lld%lld",&n,&m,&d,&e)) { init(); solve(); } return 0; } |
看评论还有一种O(n*lgn*lgk)的算法……但是想了一早上也没明白怎么弄，饿得不行吃饭先了……