[原创]各种乱七八糟的模板【不定期补充】[C++语言描述]

2016-07-17 16:12:39 Tabris_ 阅读数：405

博客爬取于2020-06-14 22:39:17
以下为正文

版权声明：本文为Tabris原创文章，未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/51932828

矩阵快速幂

struct Matrix
{
   // int r,c;   //C行R列
    LL m[66][66];
};

Matrix operator * (Matrix a,Matrix b)
{
    Matrix c;
    for(int i=0; i<M; i++) //初始化矩阵
        for(int j=0; j<M; j++)
            c.m[i][j]= 0;

    for(int k=0; k<M; k++)
        for(int i=0; i<M; i++) //实现矩阵乘法
        {
            if(a.m[i][k] <= 0)  continue;  //剪枝
            for(int j=0; j<M; j++)
            {
               // if(b.m[k][j] <= 0)    continue;  //剪枝
                c.m[i][j]=(c.m[i][j]+a.m[i][k]*b.m[k][j]+MOD)%MOD;
            }
        }
    return c;
}

Matrix operator ^ (Matrix a,LL b)
{
    Matrix c;
    for(int i=0; i<n; i++) //初始化单位矩阵
        for(int j=0; j<n; j++)
            c.m[i][j] = c.m[i+n][j+n] =  ( i == j );

    while(b)
    {
        if(b&1) c= c * a ;
        b >>= 1;
        a = a * a ;
    }

    return c;
}

Matrix operator + (Matrix a,Matrix b)
{
    for(int i=0; i<M; i++)
        for(int j=0; j<M; j++)
            a.m[i][j]=(a.m[i][j]+b.m[i][j]+MOD)%MOD;

    return a;
}

博弈SG函数

（一）记忆化搜索dfs版

# include<stdio.h>
# include<string.h>
# include<algorithm>
using namespace std;
//注意 S数组要按从小到大排序 SG函数要初始化为-1 对于每个集合只需初始化1边
//不需要每求一个数的SG就初始化一边
int SG[10100],n,m,s[102],k;//k是集合s的大小 S[i]是定义的特殊取法规则的数组
int dfs(int x)//求SG[x]模板
{
    if(SG[x]!=-1) return SG[x];
    bool vis[110];
    memset(vis,0,sizeof(vis));

    for(int i=0;i<k;i++)
    {
        if(x>=s[i])
        {
           dfs(x-s[i]);
           vis[SG[x-s[i]]]=1;
         }
    }
    int e;
    for(int i=0;;i++)
      if(!vis[i])
      {
        e=i;
        break;
      }
    return SG[x]=e;
}
int main()
{
    int cas,i;
    while(scanf("%d",&k)!=EOF)
    {
        if(!k) break;
        memset(SG,-1,sizeof(SG));
        for(i=0;i<k;i++) scanf("%d",&s[i]);
        sort(s,s+k);
        scanf("%d",&cas);
        while(cas--)
        {
            int t,sum=0;
            scanf("%d",&t);
            while(t--)
            {
                int num;
                scanf("%d",&num);
                sum^=dfs(num);
               // printf("SG[%d]=%d\n",num,SG[num]);
            }
            if(sum==0) printf("L");
            else printf("W");
        }
        printf("\n");
    }
    return 0;
}

（二）预处理打表版

# include<stdio.h>
# include<string.h>
# include <string>
# include <iostream>
using namespace std;

const int N = 10008;
int s[108],t;
int sg[N];
bool has[N];
void sg_solve(int *s,int t,int N)   //N求解范围 S[]数组是可以每次取的值，t是s的长度。
{
    int i,j;
    memset(sg,0,sizeof(sg));
    for(i=1;i<=N;i++)
    {
        memset(has,0,sizeof(has));
        for(j=0;j<t;j++)
            if(i - s[j] >= 0)
                has[sg[i-s[j]]] = 1;
        for(j=0;j<=N;j++)
            if(!has[j])
                break;
        sg[i] = j;
    }
    return ;
}

int main()
{
    int i,j,n,m,h;
    while(scanf("%d",&t),t)
    {
        string ans="";
        for(i=0;i<t;i++)
            scanf("%d",&s[i]);
        sg_solve(s,t,N);
        scanf("%d",&n);
        for(i=0;i<n;i++)
        {
            scanf("%d",&m);
            int res = 0;
            for(j=0;j<m;j++)
            {
                scanf("%d",&h);
                res ^= sg[h];
            }
            ans+=res?'W':'L';
        }
        cout<<endl;
    }
    return 0;
}

矩阵快速幂

博弈SG函数

（一） 记忆化搜索dfs版

（二） 预处理打表版

（一）记忆化搜索dfs版

（二）预处理打表版