T1 gem

Sol
只会30分的记搜。以前做过一样的，这次写的DP，记录当前用了几枚红/蓝宝石，目前最多红-蓝/蓝-红后缀是多少。转移方程很显然。

T2 sale

Sol
看完题很快就想到矩阵快速幂，然后发现是原题。
原题CF514E Darth Vader and Tree比这个甚至还多套了一层掩饰。
线性DP很好想，就是枚举种优惠券把去掉后的方案数+1。即\(dp_j=\sum_{i=1}^n dp_{j-d_i}\)。
发现\(n\)比较大而\(d_i\)比较小，所以可以用一个桶记录每种\(d_i\)的值出现次数。即\(dp_j=\sum_{i=1}^{100}t_i*dp_{j-i}\)
这是一个非常标准的线性DP方程，考虑通过矩阵加速快速求解。
Code

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int p=1000000007;
namespace io
{
	inline int read()
	{
		int x=0,f=1;char c=getchar();
		while(c<'0'||c>'9'){if(c=='-')f=0;c=getchar();}
		while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c&15),c=getchar();
		return f?x:-x;
	}
	inline void print(int x)
	{
		static int s[40],slen;slen=0;
		if(x==0){putchar('0');return;}
		if(x<0)x=-x,putchar('-');
		while(x){s[++slen]=x%10;x/=10;}
		for(int i=slen;i;i--)putchar('0'+s[i]);
		return;
	}
}
using namespace io;
struct matrix
{
    int n,m;
    int a[110][110];
}matans,matx;
int n,t[110],k;
inline matrix mul(matrix &a,matrix &b)
{
    matrix c;c.n=a.n;c.m=b.m;
    for(int i=1;i<=101;i++)for(int j=1;j<=101;j++)c.a[i][j]=0;
    for(int i=1;i<=a.n;i++)
    {
        for(int k=1;k<=a.m;k++)
        {
            if(a.a[i][k]==0)continue;
            for(int j=1;j<=b.m;j++)
            {
                c.a[i][j]+=(a.a[i][k]*b.a[k][j])%p;
                if(c.a[i][j]>=p)c.a[i][j]-=p;
            }
        }
    }
    return c;
}
inline matrix ksm(matrix a,int mi)
{
    matrix matmp;matmp.n=a.n;matmp.m=a.m;
    for(int i=1;i<=101;i++)for(int j=1;j<=101;j++)matmp.a[i][j]=0;
    for(int i=1;i<=a.n;i++)matmp.a[i][i]=1;
    while(mi)
    {
        if(mi&1)matmp=mul(matmp,a);
        a=mul(a,a);mi>>=1;
    }
    return matmp;
}
signed main()
{
    freopen("sale.in","r",stdin);
    freopen("sale.out","w",stdout);
    n=read();k=read();
    for(int i=1;i<=n;i++)t[read()]++;
    matx.a[1][1]=1;matans.n=101;matans.m=1;
    matx.n=matx.m=101;
    for(int i=2;i<=101;i++)matx.a[1][i]=matx.a[2][i]=t[i-1];
    for(int i=3;i<=101;i++)matx.a[i][i-1]=1;
    matans.a[1][1]=matans.a[2][1]=1;
    matx=ksm(matx,k);
    matans=mul(matx,matans);
    print(matans.a[1][1]);putchar('\n');
    return 0;
}

T3 （记不到名字了）

Sol
写在前面：这个题的交互完全不懂有什么意义。
又一道原题，不过卡掉了原题的解法。
P7670 [JOI2018] Snake Escaping
先想两种暴力：
第一种每次查询直接暴力匹配。时间复杂度\(\mathcal{O}(q*2^n)\)
第二种预处理所有答案，先搜确定0和1的，然后2的就是前两者之和。时间复杂度\(\mathcal{O}(3^n)\)
于是经过我也不知道怎么会这样的思考，发现两者结合就过了。
取一个参数\(K\)，假设前\(K\)位用暴力一，后面的暴力二预处理，那么时间复杂度就是\(\mathcal{O}(q*2^K+3^{n-K})\)，luogu上的题目亲测\(K\)取8的时候最优秀而且预处理不卡常。但是UKE实在无奈。
Code(不是交互)

#include<bits/stdc++.h>
using namespace std;
namespace io
{
	inline int read()
	{
		int x=0,f=1;char c=getchar();
		while(c<'0'||c>'9'){if(c=='-')f=0;c=getchar();}
		while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c&15),c=getchar();
		return f?x:-x;
	}
	inline void print(int x)
	{
		static int s[40],slen;slen=0;
		if(x==0){putchar('0');return;}
		if(x<0)x=-x,putchar('-');
		while(x){s[++slen]=x%10;x/=10;}
		for(int i=slen;i;i--)putchar('0'+s[i]);
		return;
	}
}
using namespace io;
const int maxn=30,maxm=1000010,K=8,L=12,F=(1<<K)-1;
int n,q,o,oo;
int mi3[maxn],mi32[maxn],ans[maxm],a[(1<<20)+10];
int d[maxm],hf[maxm],hb[maxm];
int ansf[531451],lb[531451],ts[531451],td[(1<<20)+10];
char s[21];
inline int dfs(int x)
{
	int now=x-o;int &rst=ansf[now];
	if(~rst)return rst;
	if(lb[now]==-1)return rst=a[ts[now]+oo];
	rst=dfs(x-mi3[lb[now]])+dfs(x-mi3[lb[now]]*2);
	return rst;
}
int main()
{
	n=read();q=read();
	for(int i=0;i<(1<<n);i++)a[i]=getchar()-'0';
	mi3[0]=1;
	for(int i=1;i<=maxn;i++)mi3[i]=mi3[i-1]*3,mi32[i]=mi3[i]<<1;
	memset(lb,-1,sizeof(lb));
	for(int i=0;i<531451;i++)
	{
		if(i%3==2)lb[i]=0;
		else if(~lb[i/3])lb[i]=lb[i/3]+1;
		else lb[i]=lb[i/3];
	}
	for(int i=0;i<531451;i++)
	{
		ts[i]=ts[i/3]<<1|i%3;td[ts[i]]=i;
	}
	if(n<=L)
	{
		memset(ansf,-1,sizeof(ansf));
		for(int i=0;i<mi3[n];i++)dfs(i);
		for(int i=1;i<=q;i++)
		{
			scanf("%s",s+1);
			int now=0;
			for(int j=1;j<=n;j++)
			{
				if(s[j]=='?')now=now*3+2;
				else now=now*3+s[j]-'0';
			}
			print(ansf[now]);putchar('\n');
		}
		return 0;
	}
	for(int i=1;i<=q;i++)
	{
		scanf("%s",s+1);
		hf[i]=F;
		for(int j=1;j<=K;j++)
		{
			int now=s[j]=='0'?0:1;
			d[i]=(d[i]<<1)+now;
			if(s[j]=='?')hf[i]=hf[i]^(1<<(K-j));
		}
		for(int j=K+1;j<=n;j++)
		{
			int now;
			if(s[j]=='?')now=2;
			else now=s[j]-'0';
			hb[i]=hb[i]*3+now;
		}
	}
	int lim=1<<K;
	for(int i=0;i<lim;i++)
	{
		oo=i<<(n-K),o=td[i]*mi3[n-K];
		memset(ansf,-1,sizeof(ansf));
		for(int j=0;j<mi3[n-K];j++)dfs(j+o);
		for(int j=1;j<=q;j++)
		{
			if(((d[j]^i)&hf[j])==0)ans[j]+=ansf[hb[j]];
		}
	}
	for(int i=1;i<=q;i++)print(ans[i]),putchar('\n');
	return 0;
}

T4

不会。