网络赛使人自闭，目前为止还缺了好多知识点我哭了。

  • Matrix Power Series

VJ链接：https://vjudge.net/problem/POJ-3233
难点在于推出Sk,Ak的递推式，将答案转换为常数矩阵的幂次方形式，还有可以在矩阵中补零转换为方阵。
注释都在代码里拉，还有取余的时候注意不要出现负数的情况，可以(x+mod)%mod.(此题不存在这个坑) 
#include<bits/stdc++.h>
using namespace std;
#define endll printf("\n")
#define s1(a) scanf("%d",&a)
#define lowbit(x)  ((x)&(-x))
#define sl1(a) scanf("%lld",&a)
#define s2(a,b) scanf("%d%d",&a,&b)
#define mem(a,b) memset(a,b,sizeof(a))
#define sl2(a,b) scanf("%lld%lld",&a,&b)
#define s3(a,b,c) scanf("%d%d%d",&a,&b,&c)
int n,k,m;
//E为n*n的单位矩阵
//(E,A)*(Sk-1,0)=(Sk,0);
//(0,A)*(Ak-1,0)=(Ak,0);
//
struct IN
{
    int a[111][111];
    IN operator *(IN &b)
    {
        IN c;mem(c.a,0);
        for(int i=0;i<n;i++)
            for(int j=0;j<n;j++)
                for(int k=0;k<n;k++)
                    c.a[i][j]=(c.a[i][j]+a[i][k]*b.a[k][j])%m;
        return c;
    }
}st,ans,tmp;
void mtpow()
{
    while(k)
    {
        if(k&1) ans=ans*st;
        st=st*st;
        k>>=1;
    }
    //求出st的k-1次幂,与
    //(A,0)
    //(A,0)
    //相乘
    ans=ans*tmp;
    n>>=1;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
            printf("%d ",ans.a[i][j]);
        endll;
    }
}
int main()
{
    s3(n,k,m);
    //构造初始矩阵
    mem(st.a,0);
    //左上角
    for(int i=0;i<n;i++) st.a[i][i]=1;
    //右上和右下
    for(int i=0;i<n;i++)
        for(int j=n;j<n*2;j++)
        {
            s1(st.a[i][j]);
            st.a[i+n][j]=st.a[i][j];
            tmp.a[i][j-n]=tmp.a[i+n][j-n]=st.a[i][j];
        }
    //构造求该矩阵n次幂的矩阵
    mem(ans.a,0);
    n<<=1;k--;
    for(int i=0;i<n;i++) ans.a[i][i]=1;
    mtpow();
    return 0;
}

  • Kiki & Little Kiki 2（思维）

VJ链接：https://vjudge.net/problem/HDU-2276
题意：每秒钟灯的状态由本身和他左边的灯决定，左边的灯开着则将此灯反转，问m秒之后每个灯的状态
思路：难点在于把递推公式找出来，构造出常数矩阵。
先考虑第一个灯：影响它新状态的只有它左右的灯和它自己的状态，仔细想一下，1*n的转移中只有这两位置有用，那么
最后：
最后要注意的一点就是，计算f[n]的时候，把st初始化为常数矩阵1次幂形式，
之后可以把ans初始化为单位矩阵，算出常数矩阵的k次幂之后ans再与初始状态矩阵相乘。
也可以一开始就把ans初始化为初始状态矩阵（E*A=A嘛，先乘后乘都一样的），然后与st做k次幂乘。
要注意构造矩阵的行列关系，因为计算矩阵乘的时候为ans*st;
为保证状态矩阵中的状态与常数相乘，初始化时状态存在第0行而不是0列。 
#include<bits/stdc++.h>
using namespace std;
#define endll printf("\n")
#define s1(a) scanf("%d",&a)
#define mem(a,b) memset(a,b,sizeof(a))
int n,k;//灯的个数以及矩阵大小
char s[111];
struct IN
{
    int a[111][111];
    IN operator *(IN &b)
    {
        IN c;mem(c.a,0);
        for(int i=0;i<n;i++)
            for(int j=0;j<n;j++)
                for(int k=0;k<n;k++)
                    c.a[i][j]=(c.a[i][j]+(a[i][k]&b.a[k][j]))%2;
        return c;
    }
}st,ans;
void mtpow()
{
    while(k)
    {
        if(k&1) ans=ans*st;//注意这里的顺序，按行构造还是按列构造，因矩阵乘法不满***换律
        st=st*st;
        k>>=1;
    }
    for(int i=0;i<n;i++)
        printf("%d",ans.a[0][i]);
    endll;
}
int main()
{
    while(~s1(k))
    {
        scanf("%s",s);n=strlen(s);
        mem(st.a,0);mem(ans.a,0);
        for(int i=0;i<n;i++)
        {
            st.a[i][i]=st.a[(i-1+n)%n][i]=1;//错误示范a[((i-1+n)%n][i]...
            ans.a[0][i]=s[i]-'0';//错误示范ans.a[i][0]=s[i]-'0';
        }
        mtpow();
    }
    return 0;
}

  • 233 Matrix（待更）

VJ链接：https://vjudge.net/problem/HDU-5015
题意：给个矩阵，第0行是0，233，2333....，第0列是0，a1，a2...（输入n个数字）。求构造出的矩阵an,m。
思路：写过两个矩阵的题了所以！这个构造矩阵我居然自己写出来了（难道这题很简单。
借一下菊苣的图）

但刚开始直接拿ans表示常数矩阵，st表示第0行，求m幂次不对。。。
这个要先求完常数矩阵的m次幂再与st相乘，，，不知道为啥，，， 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define mod   10000007
#define endll printf("\n")
#define s1(a) scanf("%d",&a)
#define s2(a,b) scanf("%d %d",&a,&b)
#define mem(a,b) memset(a,b,sizeof(a))
int n,m;
struct IN
{
    ll a[13][13];
    IN operator *(IN &b)
    {
        IN c;mem(c.a,0);
        for(int i=0;i<13;i++)
            for(int j=0;j<13;j++)
                for(int k=0;k<13;k++)
                    c.a[i][j]=(c.a[i][j]+(a[i][k]*b.a[k][j]))%mod;//WAAAAAA..不能写+=呀
        return c;
    }
}st,ans,tmp;
void mtpow()
{
    mem(ans.a,0);
    for(int i=0;i<13;i++) ans.a[i][i]=1;
    while(m)
    {
        if(m&1) ans=ans*tmp;
        tmp=tmp*tmp;
        m>>=1;
    }
    ans=ans*st;
    printf("%lld\n",ans.a[n][0]);
}
int main()
{
    while(~s2(n,m))
    {
        mem(st.a,0);mem(tmp.a,0);
        for(int i=1;i<=n;i++) s1(st.a[i][0]);
        st.a[n+1][0]=3;st.a[0][0]=23;
        for(int i=0;i<=n;i++)
        {
            tmp.a[i][0]=10;
            tmp.a[i][n+1]=1;
            for(int j=1;j<=i;j++)
                tmp.a[i][j]=1;
        }
        tmp.a[n+1][n+1]=1;
        mtpow();
    }
    return 0;
}