Gcd 算是签到题吧，稍微想一下就好了。

判断整个数列的最大公约数 是否为1，是就输出N 不是输出 “No solution”

求和（本想多组数据，不过一想Acm，都一样……）

二分即可。 很惭愧的说一句，题目非原创，poj3233，代码也是模仿别人。

#include<cstdio>
#include<cstring>
using namespace std;
#define N 31
typedef struct{
    long long  m[N][N];
}Matrix;
Matrix a,per;
int n,M;
void init()
{
    int i,j;
    for(i=0;i<n;i++)
        for(j=0;j<n;j++)
    {
        scanf("%d",&a.m[i][j]);
        a.m[i][j]%=M;
        per.m[i][j]=(i==j);
    }
}
Matrix add(Matrix a,Matrix b)
{
    Matrix c;
    int i,j;
    for(i=0;i<n;i++)
        for(j=0;j<n;j++)
        c.m[i][j]=(a.m[i][j]+b.m[i][j])%M;
    return c;
}
Matrix multi(Matrix a,Matrix b){
    Matrix c;
    int i,j,k;
    for(i=0;i<n;i++)
        for(j=0;j<n;j++)
    {
        c.m[i][j]=0;
        for(k=0;k<n;k++) c.m[i][j]=(c.m[i][j]+a.m[i][k]*b.m[k][j]%M)%M;
    }
    return c;
}
Matrix power(int k)
{
    Matrix p,ans=per;
    p=a;
    while(k){
        if(k&1) ans=multi(ans,p);
        k>>=1;
        if(k) p=multi(p,p);
    }
    return ans;
}
Matrix MatrixSum(int k)
{
    if(k==1) return a;
    Matrix temp,b;
    temp=MatrixSum(k/2);
    if(k&1){        //k为奇数时sum(k)=(1+A^(k/2+1))*sum(k/2)+A^(k/2+1); 
        b=power(k/2+1);
        temp=add(temp,multi(temp,b));
        temp=add(temp,b);
    }
    else{
        b=power(k/2);            //k为偶数时sum(k)=(1+A^(k/2))*sum(k/2)  
        temp=add(temp,multi(temp,b));
    }
    return temp;
}
int main()
{
  //  freopen("sum.in","r",stdin); freopen("sum.out","w",stdout);
    int i,j,k,T;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d%d",&n,&k,&M);
        init();
        Matrix ans=MatrixSum(k);
        for(i=0;i<n;i++)
        {
            for(j=0;j<n;j++) printf("%d ",ans.m[i][j]);
            printf("\n");
        }
    }
    return 0;
}

当素数遇上斐波那契 N<=4时 特判，n>=5时 miller_rabin素数测试。这道题数据比较坑，特意加入了强伪素数。在此引用matrix67 大神的博客中的一段话：

“对于大数的素性判断，目前Miller-Rabin算法应用最广泛。一般底数仍然是随机选取，但当待测数不太大时，选择测试底数就有一些技巧了。比如，如果被测数小于4 759 123 141，那么只需要测试三个底数2, 7和61就足够了。当然，你测试的越多，正确的范围肯定也越大。如果你每次都用前7个素数(2, 3, 5, 7, 11, 13和17)进行测试，所有不超过341 550 071 728 320的数都是正确的。如果选用2, 3, 7, 61和24251作为底数，那么10^16内唯一的强伪素数为46 856 248 255 981。这样的一些结论使得Miller-Rabin算法在OI中非常实用。通常认为，Miller-Rabin素性测试的正确率可以令人接受，随机选取k个底数进行测试算法的失误率大概为4^(-k)。”

原文链接：http://www.matrix67.com/blog/archives/234

在这个题上W的大神们，勿怪。

#include<cstdlib>
#include<cstdio>
using namespace std;
#define LL long long
LL multi(LL a,LL b,LL p)
{
    LL ans=0;
    while(b){
        if(b&1) ans=(ans+a)%p;
        b>>=1;
        if(b) a=(a<<1)%p;
    }
    return ans;
}
LL mi(LL a,LL b,LL p){
    LL ans=1;
    while(b)
    {
        if(b&1) ans=multi(ans,a,p);
        b>>=1;
        if(b) a=multi(a,a,p);
    }
    return ans;
}
bool test(LL n,LL a,LL d)
{
    if(n==2||n==a) return true;
    if(!(n&1)) return false;
    while(!(d&1)) d>>=1;
    LL t=mi(a,d,n);
    while((d!=n-1)&&(t!=1)&&(t!=n-1)){
        t=multi(t,t,n);
        d<<=1;
    }
    return (t==n-1||(d&1)==1);
}
bool miller_rabin(LL n){
    if(n<2) return false;
    int  a[]={16231,233333,233};
    for(int i=0;i<3;i++) if(!test(n,a[i],n-1)) return false;
    return true;
}
int main(){
    freopen("sfib.in","r",stdin); freopen("sfib.out","w",stdout);
    int T;
    scanf("%d",&T);
    while(T--)
    {
        LL n;
        while(scanf("%lld",&n)!=EOF)
        {
            if(n<=2) puts("No");
            else if(n==3||n==4) puts("Yes");
            else if(miller_rabin(n)) puts("Yes"); else puts("No");
        }
    }
    return 0;
}

最后，第一次举办比赛，不足之处敬请谅解，题解暂时就这样吧，只是我自己的做法，大神勿喷，Orz各位虐bf的大神。 //欢迎各位参加round 2