/ tabris /

记录详情

Time Exceeded


  
# 状态 耗时 内存占用
#1 Time Exceeded ≥10015ms ≥1.469 MiB
#2 Time Exceeded ≥10009ms ≥1.5 MiB
#3 Wrong Answer 198ms 1.492 MiB
#4 Wrong Answer 200ms 1.375 MiB
#5 Wrong Answer 199ms 1.473 MiB

代码

#include<bits/stdc++.h>
const int maxn = 2e2+5;
const int mod = 1e9+7;
using namespace std;
typedef long long ll;
typedef struct
{
    int s[maxn][maxn];
}matrix;
int n,k,a[maxn];
ll m;
matrix mul(matrix A,matrix B)
{      matrix ans;
     memset(ans.s,0,sizeof(ans.s));
      for(int i = 0 ;i < n;i++)
       for(int j =0;j < n;j++)
       {

            for(int k = 0; k < n;k++)
           	{
			   ans.s[i][k] = (ans.s[i][k]+(ll)A.s[i][j]*B.s[j][k] % mod)%mod;
			   if(ans.s[i][k] < 0) ans.s[i][k] += mod;
         	}
	   }
	   return ans;
}
matrix quickpow(matrix A,ll x)
{
	 matrix E;
     for(int i = 0;i < n;i++)
       for(int j = 0;j < n;j++)
       {  if(i == j)
           E.s[i][j] = 1;
           else
           E.s[i][j] = 0;
	   }//初始化,数初始化为1,矩阵应该初始化为单位矩阵;
	 while(x){
	 	 if(x&1)
	 	  {
		   E=mul(E,A);
	      }
	 	 A=mul(A,A);
	 	 x /= 2;
	 }
	 return E;
}
int main()
{
    int _;
    cin >> _;
    while(_--)
    {
        scanf("%d %lld %d",&n,&m,&k);
        for(int i = 0;i < n;++i)
        scanf("%d",&a[i]);
        matrix mid ;
        memset(mid.s,0,sizeof mid.s);
        for(int i =0;i < n;++i)
        {
            for(int j = 0;j < n;++j)
            {
                if(i == j) mid.s[i][j] = 0;
                else
                    mid.s[i][j] = k-min(abs((j-i+n)%n),abs((i-j+n)%n));
            }
        } 
        mid = quickpow(mid,m);
        matrix ans;
        memset(ans.s,0,sizeof ans.s);
        for(int i = 0;i < n;++i)
            ans.s[0][i] = a[i];
        ans = mul(ans,mid);
        for(int i = 0;i < n;++i)
            printf("%d%c",ans.s[0][i],i == n - 1?'\n':' ');
    }
    return 0;
}

信息

递交者
类型
递交
题目
tabris is SirBat 2
语言
C++
递交时间
2017-11-26 18:14:00
评测时间
2017-11-26 18:14:00
评测机
分数
0
总耗时
≥20623ms
峰值内存
≥1.5 MiB