2021 Xinjiang Provincial Collegiate Programming Contest(A,B)

• A. chino with string
• B. cocktail with hearthstone

题意：
有 m ( 1 ≤ m ≤ 200 ) m(1leq mleq 200) m(1≤m≤200)个长度和不超过 200 200 200的字符串，第 i i i个字符串的贡献为 v i v_i vi​，求长度为 n ( 1 ≤ n ≤ 1 0 9 ) n(1leq nleq 10^9) n(1≤n≤109)的字符串，所有子串能够组成的最大贡献是多少。
思路：
经典的 A C AC AC自动机题目
类比 [JSOI2007]文本生成器，快速可以写出动态规划

但是由于 n n n的数据范围过大，时间复杂度无法实现
所以需要用到矩阵快速幂
这里先介绍矩阵的一种变形，正常的矩阵运算是 ( A B ) i j = ∑ k = 0 p − 1 a i , k ∗ b k , j (AB)_{ij}=sum_{k=0}^{p-1}a_{i,k}*b_{k,j} (AB)ij​=∑k=0p−1​ai,k​∗bk,j​，也就是前行乘后列，是一种内层乘法外层加法的复合运算。
已知矩阵乘法具有结合率，所以矩阵可以进行快速幂加速
如果我们定义一种全新的矩阵运算 ( A B ) i j = △ k = 0 p − 1 a i , k □ b k , j (AB)_{ij}=△_{k=0}^{p-1}a_{i,k} square b_{k,j} (AB)ij​=△k=0p−1​ai,k​□bk,j​
只要可以：
1、 □ square □运算满足交换律，结合律。
2、 △ triangle △运算满足交换律，结合律。
3、 □ square □对 △ triangle △的分配率。
该新矩阵运算法则就可以使用快速幂。
所以 D P { i , j } = M A X t r i e [ p ] [ c h ] = = j D P { i − 1 , p } + v a l p DP{i,j}=MAX_{trie[p][ch]==j}DP{i-1,p} + val_p DP{i,j}=MAXtrie[p][ch]==j​DP{i−1,p}+valp​也可以
正常的矩阵乘法：
[ 1 1 1 0 ] ∗ [ f [ n ] f [ n − 1 ] ] = [ f [ n + 1 ] f [ n ] ] begin{bmatrix}1 quad 1\1quad 0end{bmatrix}*begin{bmatrix}f[n] \ f[n-1]end{bmatrix}=begin{bmatrix}f[n+1] \ f[n]end{bmatrix} [1110​]∗[f[n]f[n−1]​]=[f[n+1]f[n]​]
本题我们定义的矩阵乘法：
[ 1 1 1 0 ] ∗ [ f [ n ] f [ n − 1 ] ] = [ m a x { f [ n ] + 1 , f [ n − 1 ] + 1 } m a x { f [ n − 1 ] + 1 , f [ n ] + 1 , f [ n − 1 ] + 0 } ] begin{bmatrix}1 quad 1\1quad 0end{bmatrix}*begin{bmatrix}f[n] \ f[n-1]end{bmatrix}=begin{bmatrix}max{f[n]+1,f[n-1]+1} \ max{f[n-1]+1,f[n]+1,f[n-1]+0}end{bmatrix} [1110​]∗[f[n]f[n−1]​]=[max{f[n]+1,f[n−1]+1}max{f[n−1]+1,f[n]+1,f[n−1]+0}​]
这样的矩阵计算似乎叫做 f l o y e d floyed floyed矩阵
于是，一个本来需要连续 n n n次的转移过程，就可以通过矩阵的加速快速求出
第一次见到这样的写法，似乎可以优化见到的大多数 D P DP DP

#include
#define int long long
#define inf 1e18
using namespace std;
typedef long long ll;
const int maxn=205;
char s[maxn];
int cnt,fail[maxn],son[maxn],trie[maxn][30];
int f[205][205];
int val[205];
void insert(char s[],int x)
{
	int p=0,l=strlen(s);
	for(int i=0;i
		int u=s[i]-'a';
		if(!trie[p][u])
		{
			trie[p][u]=++cnt;
		}
		p=trie[p][u];		
	}
	son[p]+=val[x];
}
void make_fail()
{
	queueq;
	for(int i=0;i<26;i++)
		if(trie[0][i])
			q.push(trie[0][i]);
	while(!q.empty())
	{
		int t=q.front();
		q.pop();
		for(int i=0;i<26;i++)
		{
			int p=trie[t][i];
			if(!p) trie[t][i]=trie[fail[t]][i];
			else
			{
				fail[p]=trie[fail[t]][i];
				son[p]+=son[fail[p]];
				q.push(p);
			}
		}
	}
}
struct Mat
{
    ll a[maxn][maxn];
    Mat()
    {
        for(int i=0;i
    Mat mat;
    for(int i=0;i<=cnt;i++)
        for(int j=0;j<=cnt;j++)
            for(int k=0;k<=cnt;k++)
                mat.a[i][k]=max(mat.a[i][k],p.a[i][j]+q.a[j][k]);
    return mat;
}
Mat b,ans;
signed main()
{
	int n,m;
	scanf("%lld%lld",&n,&m);
	for(int i=1;i<=m;i++)
	{
		scanf("%s",s);
		scanf("%lld",&val[i]);
		insert(s,i);
	}
	make_fail();
	for(int i=0;i
			b.a[i][trie[i][j]]=son[trie[i][j]];
		} 
	for(int i=0;i
		ans.a[0][i]=-inf;
	}
	\答案矩阵中的数字就是当前为字符串第i为字符时，原DP数组中各项的结果
	\由于dp[0][0]=0，其他状态无意义，所以初始矩阵仅有a[0][0]=0
    ans.a[0][0]=0;
    while(n)
    {
        if(n%2)
        ans=mul(ans,b);
        b=mul(b,b);
        n/=2;
    }
    ll tmp=-inf;
    for(int i=0;i<=cnt;i++)
        tmp=max(tmp,ans.a[0][i]);
    printf("%lld",tmp);
    return 0;
}

题意：
一个计数器 ( a , b ) (a,b) (a,b)记录的是进行了 a + b a+b a+b局游戏，胜了 a a a场，负了 b b b场，每次游戏开始会匹配两个胜负场次完全相同的玩家游戏，玩家数量 2 n + m ( 1 ≤ m < n ≤ 2 × 1 0 5 ) 2^{n+m}(1≤m 思路：
整个游戏过程如下：
( 0 , 0 ) ( 1 , 0 ) ( 0 , 1 ) ( 2 , 0 ) ( 1 , 1 ) ( 1 , 1 ) ( 0 , 2 ) . . . . . . (0,0) \(1,0) qquad(0,1) \(2,0) qquad(1,1) qquad(1,1) qquad(0,2) \...... (0,0)(1,0)(0,1)(2,0)(1,1)(1,1)(0,2)......
各个数字在同一行的比例为
1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 . . . . . . 1 \1qquad 1 \1qquad2qquad1 \1qquad3qquad3qquad1 \1qquad4qquad6qquad4qquad1 \1qquad5qquad10qquad10qquad5qquad1 \...... 11112113311464115101051......
观察到比例为杨辉三角
已知杨辉三角第 i i i行第 j j j列的数字为 C i − 1 j − 1 C_{i-1}^{j-1} Ci−1j−1​，第 i i i行的总数为 2 i − 1 2^{i-1} 2i−1，那么 ( a , b ) (a,b) (a,b)占总人数的 C a + b a 2 a + b frac{C_{a+b}^{a}}{2^{a+b}} 2a+bCa+ba​​
但是这些并非完整的答案，如果 a = n a=n a=n,有一些玩家在 ( a , b − 1 ) , ( a , b − 2 ) . . . (a,b-1),(a,b-2)... (a,b−1),(a,b−2)...状态下就已经退游戏了，所以应该减去这些位置的贡献，这样一来，能够转化为 ( a , b ) (a,b) (a,b)的有效状态只有 ( a − 1 , b ) (a-1,b) (a−1,b)，且状态会有一半的人变为 ( a − 1 , b + 1 ) (a-1,b+1) (a−1,b+1)，所以答案为 C a + b − 1 a − 1 2 a + b − 1 ∗ 2 frac{C_{a+b-1}^{a-1}}{2^{a+b-1}*2} 2a+b−1∗2Ca+b−1a−1​​

#include
#define int long long
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
const int maxn=4e5+7;
const int mod=1e9+7;
ll fac[maxn],inv[maxn],finv[maxn];
ll ksm(ll b,ll p){ll r=1;while(p>0){if(p&1){r=(r%mod*(b%mod))%mod;}p>>=1;b=(b%mod*(b%mod))%mod;}return r;}
void binom_init(int x) 
{
    fac[0]=fac[1]=1;
    inv[1]=1;
    finv[0]=finv[1] = 1;
    for(int i=2; i
        fac[i]=fac[i-1]*i%mod;
        inv[i]=mod-mod/i*inv[mod%i]%mod;
        finv[i]=finv[i-1]*inv[i]%mod;
    }
}
ll binom(ll n, ll r)
{
    if(n
	return ksm(x,mod-2);
}
signed main()
{
	
	ll n,m,q;
	scanf("%lld%lld%lld",&n,&m,&q);
	binom_init(n+m);
	ll p=ksm(2,n+m),ans;
	while(q--)
	{
		int a,b;
		scanf("%lld%lld",&a,&b);
		if(a==n)
		{
			ans=(p%mod*_inv(ksm(2,a+b-1))%mod*binom(a+b-1,a-1)%mod*_inv(2)%mod)%mod;
		}
		else
		{
			ans=(p%mod*_inv(ksm(2,a+b-1))%mod*binom(a+b-1,b-1)%mod*_inv(2)%mod)%mod;
		}
		printf("%lldn",ans%mod);
	}
}