【TopCoder SRM713】CoinsQuery

相关链接

题目传送门:https://community.topcoder.com/stat?c=problem_statement&pm=14572&rd=16882

题目大意

给$n(n \le 100)$类物品,第$i$类物品重量为$w_i(w_i \le 100)$,价值为$v_i(v_i \le 10^9)$,数量无限
给定$m(m \le 100)$个询问,第$i$询问请你回答总重量恰好为$q_i(q_i \le 10^9)$的物品,价值和最大为多少
你还需要求出使价值最大的方案数是多少(同类物品视作一样,摆放顺序不同算不同)

解题报告

规定每个物品重量不超过$100$那么我们就可以矩乘
但有一个问题:我们不仅要让价值最大,还要求方案数

但类比倍增Floyd:在一定条件,矩乘重载运算符之后仍然满足结合律
比如说这个题,我们可以:

重载加法为:两种方案取最优
重载乘法为:将两种方案拼起来(方案数相乘,价值相加)

然后直接做是$O(m n^3 \log n)$的,会在第$21$个点$TLE$
于是我们预处理转移矩阵的幂次,然后对于每个询问就是向量与矩阵相乘,单次复杂度是$O(n^2)$的
于是总的时间复杂度优化到:$O(m n^2 \log n + n^3 \log n)$

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int MOD = 1000000007;
const int N = 101;

struct Data{
	LL val,chs;
	inline Data() {val = chs = -1;}
	inline Data(LL a, LL b):val(a),chs(b) {}
	inline Data operator + (const Data &D) {
		if (chs == -1 || D.chs == -1) {
			return chs != -1? *this: D;
		} else {
			Data ret(max(val, D.val), 0);
			(ret.chs += (val == ret.val? chs: 0)) %= MOD;
			(ret.chs += (D.val == ret.val? D.chs: 0)) %= MOD;
			return ret;
		}
	}
	inline Data operator * (const Data &D) {
		if (!~chs || !~D.chs) return Data(-1, -1);
		return Data(val + D.val, chs * D.chs % MOD);
	}
}e(0,1);
struct Matrix{
	Data a[N][N]; int x,y;
	inline Matrix() {x = y = 0;}
	inline Matrix(int X, int Y):x(X),y(Y) {}
	inline Matrix operator * (const Matrix &M) {
		Matrix ret(M.x, y);
		for (int i=1;i<=M.x;i++) {
			for (int k=1;k<=x;k++) {
				for (int j=1;j<=y;j++) {
					ret.a[i][j] = ret.a[i][j] + (a[k][j] * M.a[i][k]);
				}
			}
		}
		return ret;
	}
}tra[32];

class CoinsQuery {
    public:
    	vector<LL> query(vector<int> w, vector<int> v, vector<int> query) {
    	    int m = query.size(), n = w.size();
			tra[0].x = tra[0].y = 100;
    	    for (int i=0;i<n;i++) {
				tra[0].a[w[i]][1] = tra[0].a[w[i]][1] + Data(v[i], 1);
			}
			for (int i=2;i<=100;i++) {
				tra[0].a[i-1][i] = e;
			}
			for (int i=1;i<=30;i++) {
				tra[i] = tra[i-1] * tra[i-1];
			}
    	    
			vector<LL> ret;
    	    for (int tt=0;tt<m;tt++) {
				Matrix ans(100, 1);
				ans.a[1][1] = e;
				int cur = query[tt];
				for (int i=0;cur;cur>>=1,++i) {
					if (cur & 1) {
						ans = ans * tra[i];
					}
				}
				ret.push_back(ans.a[1][1].val);
				ret.push_back(ans.a[1][1].chs);
			}
    	    return ret;
   		}
   	private:
};

【BZOJ 4861】[BeiJing2017] 魔法咒语

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4861

解题报告

对于$L \le 100$的情况,我们定义$f_{i,j}$表示长度为$i$,在$ac$自动机上匹配到点$j$的答案
然后暴力转移就可以了,时间复杂度:$O(10^4L)$

对于其他的点,我们构造转移矩阵,用矩阵快速幂来优化
至于如何把长度为$2$的和为$1$的给统一起来?我们可以加一个点缓存一下
时间复杂度:$O(200^3 \log L)$

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int MOD = 1000000007;

int n,m,L,len[109];
char s1[109][109],s2[109][109];

inline int read() {
	char c=getchar(); int f=1,ret=0;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret * f;
}

class AC_Automaton{
	int cnt,ch[109][26],vis[109],fail[109];
	vector<int> G[109];
	queue<int> que;
	public:
		inline AC_Automaton() {
			cnt=1;
		}
		inline void insert(char *s) {
			int l = strlen(s + 1), w = 1;
			for (int i=1;i<=l;i++) {
				int c = s[i] - 'a';
				if (!ch[w]) ch[w] = ++cnt;
				w = ch[w];
			}
			vis[w] = 1;
		}
		inline void build() {
			for (int i=0;i<26;i++) {
				if (!ch[1][i]) ch[1][i] = 1;
				else fail[ch[1][i]] = 1, que.push(ch[1][i]);
			}
			while (!que.empty()) { 
				int w = que.front(); que.pop(); 
				G[fail[w]].push_back(w);
				for (int i=0;i<26;i++) {
					if (ch[w][i] && ch[w][i] != 1) {
						que.push(ch[w][i]);
						fail[ch[w][i]] = ch[fail[w]][i];
					} else {
						ch[w][i] = ch[fail[w]][i];
					}
				}
			} 
			DFS(1, 0);
		}
		inline int size() {
			return cnt;
		}
		inline int MOVE(int w, int j) {
			if (vis[j]) return -1;
			for (int i=1;i<=len[w];i++) {
				j = ch[j][s1[w][i]-'a'];
				if (vis[j]) return -1;
			}
			return j;
		}
	private:
		void DFS(int w, int t) {
			t |= vis[w];
			if (t) vis[w] = 1; 
			for (int i=G[w].size()-1;~i;i--) {
				if (G[w][i] != i) { 
					DFS(G[w][i], t);
				}
			}
		}
}ac;

namespace SUBTASK_ONE{
	int f[109][109],tot,ans;
	int tra[109][109];
	
	inline void solve() {
		for (int i=1;i<=n;i++) {
			scanf("%s",s1[i]+1);
			len[i] = strlen(s1[i]+1);
		}
		for (int i=1;i<=m;i++) {
			scanf("%s",s2[i]+1);
			ac.insert(s2[i]);
		}
		ac.build(); 
		for (int i=1;i<=n;i++) {
			for (int j=1;j<=ac.size();j++) {
				int tmp = ac.MOVE(i, j);
				if (tmp != -1) tra[j][i] = tmp; 
			}
		}
		f[0][1] = 1;
		for (int i=0;i<L;i++) {
			for (int j=1;j<=ac.size();j++) {
				if (f[i][j]) {
					for (int k=1,t1,t2;k<=n;k++) {
						if ((t1=tra[j][k]) != -1 && (t2=i + len[k]) <= L) {
							f[t2][t1] = (f[t2][t1] + f[i][j]) % MOD; 
						}
					}
				}
			}
		}
		for (int i=1;i<=ac.size();i++) {
			ans = (ans + f[L][i]) % MOD;
		}
		printf("%d\n",ans);
	} 
};

namespace SUBTASK_TWO{
	int sz,tot,tra[109][109*109+109];
	struct Matrix{
		int a[209][209];
		inline Matrix() {
			memset(a,0,sizeof(a));
		}
		inline Matrix(int x) {
			memset(a,0,sizeof(a));
			for (int i=1;i<=sz;i++) a[i][i] = x;
		}
		inline Matrix operator * (const Matrix &M) {
			Matrix ret;
			for (int i=1;i<=sz;i++) {
				for (int j=1;j<=sz;j++) {
					for (int k=1;k<=sz;k++) {
						ret.a[i][j] = (ret.a[i][j] + (LL)a[k][j] * M.a[i][k]) % MOD;	
					}
				}
			}
			return ret;
		}
		inline Matrix operator ^ (int t) {
			Matrix ret(1),tmp;
			for (int i=1;i<=sz;i++) {
				memcpy(tmp.a[i],a[i],sizeof(a[i]));
			}
			for (;t;t>>=1,tmp=tmp*tmp) {
				if (t&1) ret = ret * tmp;
			}
			return ret;
		}
		inline void init() {
			memset(a,0,sizeof(a));
		}
	}ans,trans;
	
	inline void solve() {
		for (int i=1;i<=n;i++) {
			scanf("%s",s1[i]+1);
			len[i] = strlen(s1[i]+1);
		}
		for (int i=1;i<=m;i++) {
			scanf("%s",s2[i]+1);
			ac.insert(s2[i]);
		}
		ac.build(); sz = ac.size();
		for (int i=1;i<=n;i++) {
			for (int j=1;j<=sz;j++) {
				int tmp = ac.MOVE(i, j);
				if (tmp != -1) tra[j][i] = tmp; 
			}
		}
		ans.a[1][1] = 1; int ori = sz; 
		for (int i=1;i<=ori;i++) trans.a[i][++sz]++;
		for (int i=1;i<=ori;i++) {
			for (int j=1;j<=n;j++) {
				if (!tra[i][j]) continue;
				if (len[j] == 1) ++trans.a[tra[i][j]][i];
				else trans.a[tra[i][j]+ori][i]++;
			}
		}
		trans = trans ^ L;
		ans = ans * trans;
		int vout = 0;
		for (int i=1;i<=ori;i++) vout = (vout + ans.a[i][1]) % MOD;
		cout<<vout<<endl;
	}
};

int main() {
	n = read(); m = read(); L = read();
	if (L <= 100) {
		SUBTASK_ONE::solve();
	} else {
		SUBTASK_TWO::solve();
	}
	return 0;
}

【日常小测】迷宫

题目大意

给定一个$n \times 6(n \le 10^9)$的方格纸,你需要在每一个方格中填上一个$[1,6]$之间的数
要求任意一个数与它↙,←,↖,↗,→,↘这六个方向的数既不能相同,也不能和为7
并且规定左上角必须为$1$,且按照先从上往下逐行再从左往右的顺序,第一个$2$必须要出现在$5$之前,第一个$3$必须要出现在$4$之前
问有多少种合法的填色方案,输出对$1004535809$取模

解题报告

先不考虑最后题解的关于出现顺序的限制。这样的话,显然可以矩阵快速幂
但直接压状态的的话,矩阵大概长成$10^4 \times 10^4$,单次矩阵乘法都无法满足
不过我们仔细观察即可发现,对于其实1,6是等价的,同理2,53,4
于是我们每一个格子的状态就只有三种了,最后有效的状态一行只有96
这样就可以直接矩阵快速幂了

现在考虑最后的那个限制,我们可以容斥一下
我们可以先排除掉不包含2,5这一对的方案数,然后除以二
同理3,4也一样处理

于是最后就是一个状压DP用矩阵快速幂优化
最后再容斥一下,时间复杂度:$O(96 ^ 3 \log n)$

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int MOD = 1004535809;

int n,tot,vout,sta[100][7],cur[7];
struct Matrix{
	int f[100][100];
	inline Matrix() {memset(f,0,sizeof(f));}
	inline Matrix(int x) {memset(f,0,sizeof(f));for(int i=1;i<=tot;i++)f[i][i]=x;}
	inline Matrix(const Matrix &M) {for(int i=1;i<=tot;i++)for(int j=1;j<=tot;j++)f[i][j]=M.f[i][j];}
	inline Matrix operator * (const Matrix &M) {
		Matrix ret;
		for (int i=1;i<=tot;i++) for (int j=1;j<=tot;j++) for (int k=1;k<=tot;k++) 
			ret.f[i][k] = (ret.f[i][k] + (LL)f[j][k] * M.f[i][j]) % MOD;
		return ret;
	}
	inline Matrix operator ^ (int t) {
		Matrix ret(1),tmp(*this);
		for (;t;t>>=1,tmp=tmp*tmp)
			if (t&1) ret=ret*tmp;
		return ret;
	}
	inline void out() {
		for (int i=1;i<=tot;i++) {
			for (int j=1;j<=tot;j++) {
				printf("%d ",f[j][i]);
			} cout<<endl;
		}
	}
}ans,trans;

inline int read() {
	char c=getchar(); int f=1,ret=0;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret * f;
}

void DFS(int w, int v) {
	if (w == 7) {
		memcpy(sta[++tot],cur,sizeof(cur));
	} else {
		for (int i=1;i<=3;i++) if (i != v) 
			cur[w] = i, DFS(w+1, i);
	}
}

inline int Pow(int w, LL t) {
	int ret = 1;
	for (;t;t>>=1,w=(LL)w*w%MOD)
		if (t&1) ret=(LL)ret*w%MOD;
	return ret;
}

inline bool check(int a, int b) {
	for (int i=1;i<=6;i++) {
		if (i > 1 && sta[a][i-1] == sta[b][i]) return 0;
		if (i < tot && sta[a][i+1] == sta[b][i]) return 0;
	} return 1;
}

int main() {
	freopen("board.in","r",stdin);
	freopen("board.out","w",stdout);
	n = read(); DFS(1, -1);
	for (int i=1;i<=tot;i++) for (int j=1;j<=tot;j++)
		if (check(i, j)) trans.f[j][i] = 1 << 6;
	for (int i=1;i<=tot;i++) if (sta[i][1] == 1) ans.f[i][1] = 1 << 5;
	trans = trans ^ (n - 1); ans = ans * trans;
	for (int i=1;i<=tot;i++) vout = (vout + ans.f[i][1]) % MOD; 
	vout = (vout - 2ll * Pow(2, n * 6ll - 1)) % MOD; 
	vout = (LL)vout * Pow(4, MOD-2) % MOD;
	vout = (vout + Pow(2, n * 6ll - 1)) % MOD; 
	printf("%d\n",(vout+MOD)%MOD);
	return 0;
}

【BZOJ 4635】数论小测验

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4635
数据生成器:http://paste.ubuntu.com/24360378/
神犇题解:http://www.cnblogs.com/clrs97/p/5625508.html

解题报告

对于第一问,显然可以用莫比乌斯反演做到$O(Tm)$

对于第二问,考虑枚举$k$,然后$10^3$以内的数最多有$4$种不同的质因数
于是搞一个状压$DP$,用矩阵快速幂优化
单词询问时间复杂度:$O(32m^2 + 32^3 log (n))$
看起来蛮有希望过的,但卡了一下午常也没有卡过 QwQ

正解的话,我们可以学习Claris用容斥
具体来讲枚举$k$,然后枚举$k$的每一个质因数是否满足条件
然后配合一点预处理之类的,就可以做到$O(m^2 + m \log m)$了

Code

这份代码在BZOJ被卡常了 QwQ

#include<bits/stdc++.h>
#define LL long long
using namespace std; 
 
const int MOD = 1000000007;
const int N = 10000009;
const int M = 32;
 
int n,m,SZ,s1[N],hc[N],to[1001];
int tot,pri[N>>3],mu[N]; bool vis[N];
 
inline int read() {
    char c=getchar(); int f=1,ret=0;
    while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
    while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
    return ret * f;
}
 
inline int Pow(int w, int t) {
    int ret = 1;
    for (;t;t>>=1,w=(LL)w*w%MOD) 
        if (t&1) ret=(LL)ret*w%MOD;
    return ret;
}
 
inline void GetMu() {
    mu[1] = 1;
    for (int i=2;i<N;i++) {
        if (!vis[i]) mu[i] = -1, pri[++tot] = i;
        for (int j=1;j<=tot&&pri[j]*i<N;j++) {
            vis[i*pri[j]] = 1;
            if (i%pri[j]) mu[i*pri[j]] = -mu[i];
            else {mu[i*pri[j]] = 0; break;}
        } 
        mu[i] = mu[i-1] + mu[i];
    } 
}
 
inline int cal(int mx) {
    int ret = 0;
    for (int l=1,r,tmp;l<=mx;l=r+1) {
        r = mx / (mx / l);
        tmp = (LL)(mu[r] - mu[l-1]) * hc[mx/l] % MOD;
        ret = (ret + tmp) % MOD;
    }
    return (ret + MOD) % MOD;
}
 
struct Matrix{
    int a[M][M];
    inline Matrix() {memset(a,0,sizeof(a));}
    inline Matrix(const Matrix *A) {
        for (int i=0;i<M;i++) for (int j=0;j<M;j++) a[i][j] = A->a[i][j];
	}
    inline Matrix(int x) {
        memset(a,0,sizeof(a)); 
        for (int i=0;i<SZ;i++) a[i][i] = x;
    } 
    inline void operator *= (const Matrix &A) {
        Matrix ret; 
        for (int i=0,*t1,*t3;i<SZ;i++) {
        	t1 = ret.a[i]; const int *t2 = A.a[i];
			for (int j=0;j<SZ;j++) {
				t3 = a[j];
				for (int k=0;k<SZ;k+=4) { 
					t1[k] = (t1[k] + (LL)t3[k] * t2[j]) % MOD; 
					t1[k+1] = (t1[k+1] + (LL)t3[k+1] * t2[j]) % MOD; 
					t1[k+2] = (t1[k+2] + (LL)t3[k+2] * t2[j]) % MOD;
					t1[k+3] = (t1[k+3] + (LL)t3[k+3] * t2[j]) % MOD;
				}
			}
		}
        for (int i=0;i<SZ;i++) for (int j=0;j<SZ;j++) a[i][j] = ret.a[i][j];
    }
    inline Matrix operator ^ (int t) {
        Matrix ret(1),w(this);
        for (;t;t>>=1,w*=w) if (t&1) ret*=w;
        return ret;
    }
}ans,trans;
 
inline int solve(int w) {
    tot = 0; 
    for (int i=2,tmp=w;i<=tmp;i++) {
        if (tmp % i == 0) {
            pri[++tot] = i; tmp /= i;
            while (tmp % i == 0) pri[tot] *= i, tmp /= i;
        }
    } 
    ans = Matrix(); trans = Matrix(); 
    ans.a[0][0] = 1; SZ = 1 << tot;
    memset(to,0,sizeof(to));
    for (int i=1,t=1,ww;ww=pri[i],i<=tot;i++,t<<=1) 
		for (int j=ww;j<=m;j+=ww) to[j] |= t;
    for (int i=1,tt;tt=to[i],i<=m;i++) {
        for (int p=0,ww;ww=p,p<SZ;p++) 
            ++trans.a[p|tt][p];
    }
    trans = trans ^ n;
    ans *= trans;
    return ans.a[SZ-1][0];
}
 
int main() {
    int T = read(), type = read();
    if (type == 1) {
        GetMu(); 
        for (int t=1,vout;vout=0,t<=T;t++) {
            n = read(); m = read(); 
            int L = read(), R = read();
            for (int l=1,r;l<=m;l=r+1) {
                r = m / (m / l);
                hc[m / l] = Pow(m / l, n);
            }
            for (int l=L,r,tmp;l<=R;l=r+1) {
                r = m / (m / l); tmp = cal(m / l);
                vout = (vout + (min(r,R)-max(L,l)+1ll) * tmp) % MOD;
            }           
            printf("%d\n",vout);
        }
    } else if (type == 2) {
        for (int t=1,vout,l,r;vout=0,t<=T;t++) {
            n = read(); m = read(); l = read(), r = read();
            for (int w=l;w<=r;w++) vout = (vout + solve(w)) % MOD;
            printf("%d\n",vout);
        }
    }
    return 0;
}

【日常小测】排列

题目大意

给定$n(n \le 10^9),k(k \le 4)$,定义$p_i$为排列中第$i$个数
询问长度为$n$且$|p_i-i| \le k$的排列的个数$\pmod {1e9+7}$

解题报告

不难发现$k$很小,于是我们可以状压DP
进一步观察,有用的状态只有70个
于是我们可以$O(70^3 \log n)$的复杂度用矩阵快速幂解决

不过这题还可以用线性$K$阶递推式的那个解法
用特征多项式做到一个比较优的复杂度
GEOTCBRL就是用这个A的,太强大了_(:з」∠)_

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;
 
const int MOD = 1000000007;
 
inline int read() {
    char c=getchar(); int ret=0,f=1;
    while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
    while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
    return ret*f;
}
 
int n,K,t,tot,itr[1000],num[1000];
struct Matrix{
    int a[70][70];
    inline Matrix() {memset(a,0,sizeof(a));}
    inline Matrix(Matrix *tmp) {memcpy(a,tmp->a,sizeof(a));}
    inline Matrix(int v) {memset(a,0,sizeof(a));for(int i=0;i<tot;i++)a[i][i]=v;}
    inline void reset() {memset(a,0,sizeof(a));}
    inline Matrix operator * (const Matrix &B) {
        Matrix ret;
        for (int i=0;i<tot;i++) for (int j=0;j<tot;j++) for (int k=0;k<tot;k++) 
            ret.a[i][j] = (ret.a[i][j] + (LL)a[k][j] * B.a[i][k]) % MOD;
        return ret;
    }
    inline Matrix operator ^ (int t) {
        Matrix ret(1),w(this); 
        for (;t;t>>=1,w=w*w)
            if (t&1) ret=ret*w;
        return ret;
    }
}ans,tra;
 
int main() {
    for (;~scanf("%d%d",&n,&t);tot=0) {
        t <<= 1; K = 1 << t;
        ans.reset(); tra.reset();
        for (int i=0;i<K;i++) {
            if (__builtin_popcount(i) != t/2) continue;
            else itr[i] = tot, num[tot++] = i;
        }
        for (int h=0,cur,i;i=num[h],h<tot;h++) {
            for (int j=0;j<=t;j++) {
                if (i&(1<<j)) continue;
                cur = i | (1 << j);
                if (!(cur&1)) continue;
                tra.a[h][itr[cur>>1]] = 1;
            }
        } 
        t = itr[(1<<(t/2))-1]; ans.a[t][0] = 1; 
        tra = tra ^ n; ans = ans * tra;  
        printf("%d\n",ans.a[t][0]);
    }
    return 0;
}

【BZOJ 3992】[SDOI2015] 序列统计

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3992
Latex题面:http://paste.ubuntu.com/23997878/
数据生成器:http://paste.ubuntu.com/24006205/
神犇题解:http://www.cnblogs.com/gromah/p/4431016.html
NTT相关:http://blog.miskcoo.com/2015/04/polynomial-multiplication-and-fast-fourier-transform#i-13

解题报告

这题$O(m^3logn)$的基于矩阵快速幂的算法大家都会吧?
然而只能通过 $60\% $ 的数据 QwQ

然后就需要一点黑科技了
考虑模数这么奇怪,于是可能是用元根来搞一搞
然后我们发现,我们可以用元根的幂次来表示 $0 \sim m – 1$ 的每一个数
于是我们就可以把乘法换成幂次的加法,于是就可以搞NTT了!
于是用NTT来搞生成函数,复杂度:$O(nmlogm)$
然后再套上一开始讲的快速幂,那么就是$O(mlogmlogn)$的复杂度啦!

Code

话说这似乎是第一次撸$NTT$呢!
还有一点小激动啊!
不过这一份代码封装太多了,好慢啊 QwQ

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 9000;
const int M = N << 2;
const int MOD = 1004535809;

int l,n,m,x,pos[N];

inline int read() {
	char c=getchar(); int f=1,ret=0;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret * f;
}

inline int Pow(int w, int t, int mod) {
	int ret = 1;
	for (;t;t>>=1,w=(LL)w*w%mod)
		if (t & 1) ret = (LL)ret * w % mod;
	return ret;
}

inline int Get_Primitive_Root(int w) {
	vector<int> pri; int cur = w - 1;
	for (int i=2,lim=ceil(sqrt(w));i<=cur&&i<=lim;i++) {
		if (cur % i == 0) {
			pri.push_back(i);
			while (cur % i == 0) cur /= i;
		}
	}
	if (cur > 1) pri.push_back(cur);
	if (pri.empty()) return 2;  
	for (int i=2;;i++) {
		for (int j=pri.size()-1;j>=0;j--) {
			if (Pow(i, w/pri[j], w) == 1) break;
			if (!j) return i;
		}
	}
}

struct Sequence{
	int a[M],POS[M],len;
	inline Sequence() {}
	inline Sequence(int l) {
		memset(a,0,sizeof(a));
		len = l; a[0] = 1;
	}
	inline Sequence(Sequence &B) {
		memcpy(this, &B, sizeof(B));
		len=B.len;
	}
	inline void NTT(int f) {
		static const int G = Get_Primitive_Root(MOD);
		int l = -1; for (int i=len;i;i>>=1) l++;
		if (!POS[1]) {
			for (int i=1;i<len;i++) { 
				POS[i] = POS[i>>1]>>1;
				if (i & 1) POS[i] |= 1 << l-1;
			} 
		}
		for (int i=0;i<len;i++) if (POS[i] > i) 
			swap(a[i], a[POS[i]]);
		for (int seg=2;seg<=len;seg<<=1) {
			int wn = Pow(G, MOD/seg, MOD);
			if (f == -1) wn = Pow(wn, MOD-2, MOD);
			for (int i=0;i<len;i+=seg) {
				for (int k=i,w=1;k<i+seg/2;k++,w=(LL)w*wn%MOD) {
					int tmp = (LL)w * a[k+seg/2] % MOD;
					a[k+seg/2] = ((a[k] - tmp) % MOD + MOD) % MOD;
					a[k] = (a[k] + tmp) % MOD;
				}
			}
		}
		if (f == -1) { 
			for (int i=0,rev=Pow(len,MOD-2,MOD);i<len;i++) 
				a[i] = (LL)a[i] * rev % MOD;
		}
	}
	inline void Multiply(Sequence B) {
		NTT(1); B.NTT(1);
		for (int i=0;i<len;i++)
			a[i] = (LL)a[i] * B.a[i] % MOD;
		NTT(-1); 
		for (int i=m-1;i<len;i++) 
			(a[i-m+1] += a[i]) %= MOD, a[i] = 0;
	} 
	inline void pow(int t) {
		Sequence ret(len),w(*this);
		for (;t;t>>=1,w.Multiply(w)) 
			if (t & 1) ret.Multiply(w);
		memcpy(this, &ret, sizeof(ret));
	}
}arr;

int main() {
	l = read(); m = read();
	x = read() % m; n = read();
	int PRT = Get_Primitive_Root(m);
	for (int cur=1,i=0;i<m-1;i++,cur=cur*PRT%m) pos[cur] = i;
	for (int i=0,t;i<n;i++) t=read(), t?arr.a[pos[t%m]]++:0;
	int len = 1; while (len < m) len <<= 1;
	arr.len = len << 1; arr.pow(l); 
	printf("%d\n",(arr.a[pos[x]]+MOD)%MOD);
	return 0;
}

【Codeforces 718C】Sasha and Array

题目传送门:http://codeforces.com/contest/718/problem/C
数据生成器:http://paste.ubuntu.com/23296960/
官方题解:http://codeforces.com/blog/entry/47314

斐波那契数列的话,转移可以用快速幂
于是用线段树来维护转移矩阵就可以辣!

值得一提的是:我之前一直以为斐波那契数列的通项公式没有用
然而鏼爷讲了二次剩余之后,发现其实拿货是可以出成题目考的QAQ

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 200000+9;
const int MOD = 1000000007;

inline int read(){
	char c=getchar(); int ret=0,f=1;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret*f;
}

int n,m,arr[N];
struct Matrix{
	int a[3][3];
	inline Matrix() {}
	inline Matrix(int w) {
		memset(a,0,sizeof(a));
		a[1][1] = a[2][2] = w;
	}
	inline Matrix(const Matrix &B) {
		memcpy(this,&B,sizeof(B));
	}
	inline Matrix operator * (const Matrix &B) {
		Matrix ret(0);
		for (int i=1;i<=2;i++) {
			for (int j=1;j<=2;j++) {
				for (int k=1;k<=2;k++) {
					ret.a[i][j] += (LL)a[k][j] * B.a[i][k] % MOD;
					ret.a[i][j] %= MOD;
				}
			}
		}
		return ret;
	}
	inline Matrix operator ^ (LL t) {
		Matrix ret(1),w(*this);
		while (t) {
			if (t & 1) ret = ret * w;
			w = w * w; t >>= 1;
		}
		return ret;
	}
}trans,cur_trans,ori(1);

namespace Segment_Tree{
	#define SEG Segment_Tree
	int ch[N][2],cnt,root,L,R,ans_tmp;
	Matrix mat[N],tag[N];
	
	inline void maintain(int w){
		for (int i=1;i<=2;i++) {
			for (int j=1;j<=2;j++) {
				mat[w].a[i][j] = mat[ch[w][0]].a[i][j] + mat[ch[w][1]].a[i][j];
				mat[w].a[i][j] %= MOD;
			}
		}
	}
	
	inline void push_down(int w) {
		for (int i=0;i<2;i++) {
			tag[ch[w][i]] = tag[ch[w][i]] * tag[w];
			mat[ch[w][i]] = mat[ch[w][i]] * tag[w];
		}
		tag[w] = Matrix(1);
	}
	 
	void Build(int &w, int l, int r) {
		w = ++cnt;
		tag[w] = Matrix(1);
		if (l == r) {
			mat[w].a[1][1] = mat[w].a[2][1] = 1;
			mat[w] = mat[w] * (trans^(arr[l]-1));
		} else {
			int mid = l + r + 1 >> 1;
			Build(ch[w][0],l,mid-1);
			Build(ch[w][1],mid,r);
			maintain(w);
		}  
	}
	
	void Modify(int w, int l, int r) {
		if (L <= l && r <= R) {
			tag[w] = tag[w] * cur_trans;
			mat[w] = mat[w] * cur_trans;
		} else {
			push_down(w);
			int mid = l + r + 1 >> 1;
			if (L < mid) Modify(ch[w][0],l,mid-1);
			if (mid <= R) Modify(ch[w][1],mid,r);
			maintain(w);
		}
	}
	
	inline void modify(int l, int r, int delta) {
		L = l; R = r; 
		cur_trans = trans ^ delta;
		Modify(root,1,n);
	}
	
	void query(int w, int l, int r) {
		if (L <= l && r <= R) {
			ans_tmp += mat[w].a[1][1];
			ans_tmp %= MOD;
		} else {
			push_down(w); 
			int mid = l + r + 1 >> 1;
			if (L < mid) query(ch[w][0],l,mid-1);
			if (mid <= R) query(ch[w][1],mid,r);
			maintain(w); 
		}
	}
	
	inline int query(int l, int r){
		L = l; R = r; ans_tmp = 0;
		query(root,1,n);
		return ans_tmp;
	}
};

int main(){
	n = read(); m = read(); 
	for (int i=1;i<=n;i++) {
		arr[i] = read();
	}
	trans.a[1][2] = trans.a[2][1] = trans.a[2][2] = 1;
	SEG::Build(SEG::root,1,n);
	for (int i=1,ty,a,b,c;i<=m;i++) {
		ty = read(); a = read(); b = read();
		if (ty == 1) {
			SEG::modify(a,b,read());
		} else {
			printf("%d\n",SEG::query(a,b));
		}
	}
	return 0;
}

【NOIP十连测】[D3T2] 涂色游戏

题目传送门:https://oi.qizy.tech/wp-content/uploads/2016/10/test3_problem.pdf
官方题解:https://oi.qizy.tech/wp-content/uploads/2016/10/solution.pdf

这题做起来还是感觉很有意思的!
然而这™是NOIP模拟题! (╯‵□′)╯︵┻━┻

详细的看题解吧!
题解的式子枚举的是并集的大小,我枚举的是交集的大小
反正都一样,式子搞出来都差不多!

另外下一次如果组合数表较小的话还是先预处理出来吧
这一份代码是现场算的,超级蛋疼!

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 100+9;
const int MOD = 998244353;

int n,m,p,q,POW[N],REV[N],g[N][N];
struct Matrix{
	int a[N][N];
	inline Matrix() {}
	inline Matrix(const Matrix &B) {
		memcpy(this,&B,sizeof(*this));
	} 
	inline Matrix(int x) {
		memset(a,0,sizeof(a));
		for (int i=1;i<=n;i++) {
			a[i][i] = x;
		}
	}
	inline Matrix operator * (const Matrix &B) {
		Matrix ret(0);
		for (int j=1;j<=n;j++) {
			for (int i=1;i<=n;i++) {
				for (int k=1;k<=n;k++) {
					ret.a[i][j] += (LL)a[k][j] * B.a[i][k] % MOD;
					ret.a[i][j] %= MOD;
				}
			}
		}
		return ret;
	}
	inline Matrix operator ^ (int t) {
		Matrix ret(1),tmp(*this);
		while (t) {
			if (t & 1) ret = ret * tmp;
			tmp = tmp * tmp; t >>= 1;
		}
		return ret;
	}
}trans,ans; 

inline int read(){
	char c=getchar(); int ret=0,f=1;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret*f;
}

inline int pow(int w, int t) {
	int ret = 1;
	while (t) {
		if (t&1) ret = (LL)ret * w % MOD;
		w = (LL)w * w % MOD; t >>= 1;
	}
	return ret;
}

inline int alph(int a, int b, int x) {
	if (x > a || x > b || p-a-b+x < 0) return 0;
	int ret = (LL)POW[a] * POW[p-a] % MOD;
	ret = (LL)ret * REV[x] % MOD;
	ret = (LL)ret * REV[a-x] % MOD;
	ret = (LL)ret * REV[b-x] % MOD;
	ret = (LL)ret * REV[p-a-b+x] % MOD;
	return ret;
}

int main(){
	n = read(); m = read();
	p = read(); q = read();
	POW[0] = REV[0] = 1;
	for (int i=1;i<=max(n,p);i++) {
		POW[i] = (LL)POW[i-1] * i % MOD;
	}
	REV[max(n,p)] = pow(POW[max(n,p)],MOD-2);
	for (int i=max(n,p)-1;i;i--) {
		REV[i] = (LL)REV[i+1] * (i+1) % MOD;
	}
	g[1][1] = p;
	for (int i=2;i<=n;i++) {
		for (int j=1;j<=p;j++) {
			g[i][j] = (LL)g[i-1][j-1] * (p - j + 1) % MOD + (LL)g[i-1][j] * j % MOD;
			g[i][j] %= MOD;
		}
	}
	for (int a=1;a<=n;a++) {
		for (int b=1;b<=n;b++) {
			if (a > p || b > p) continue;
			for (int x=0;x<=a+b-q;x++) {
				trans.a[b][a] += alph(a,b,x);
				trans.a[b][a] %= MOD;
			}
			trans.a[b][a] = ((LL)g[n][b]*REV[p]%MOD) * trans.a[b][a] % MOD;
			trans.a[b][a] = ((LL)POW[b]*POW[p-b]%MOD) * trans.a[b][a] % MOD;
		}
	}
	for (int i=1;i<=min(n,p);i++) {
		ans.a[i][1] = g[n][i];
	}
	trans = trans ^ (m-1);
	ans = ans * trans;
	int vout = 0;
	for (int i=1;i<=n;i++) {
		vout += ans.a[i][1];
		vout %= MOD;
	}
	printf("%d\n",vout);
	return 0;
}

【Codeforces 696D】Legen…

题目传送门:http://codeforces.com/contest/696/problem/D
官方题解:http://codeforces.com/blog/entry/46031

这个题目,看一眼数据范围就知道是AC自动机+矩阵快速幂
所以剩下的唯一问题就是,我们重定义矩阵运算之后为何其仍然满足结合律?

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 200+9;
const int SGZ = 27;
const int MX = 201;

inline int read(){
	char c=getchar(); int ret=0,f=1;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret*f;
}

struct Matrix{
	LL a[N][N];
	inline Matrix() {memset(a,-1,sizeof(a));}
	inline Matrix(Matrix &v) {memcpy(this,&v,sizeof(v));}
	inline Matrix(int bas, int v) {memset(a,bas,sizeof(a));for (int i=1;i<=MX;i++) a[i][i]=v;}
	inline Matrix operator * (const Matrix &B) {
		Matrix ret; 
		for (int i=1;i<=MX;i++) for (int j=1;j<=MX;j++) for (int k=1;k<=MX;k++) 
			if (~a[k][j] && ~B.a[i][k]) ret.a[i][j] = max(ret.a[i][j], a[k][j] + B.a[i][k]);
		return ret;
	}
	inline Matrix operator ^ (LL t) {
		Matrix ret(-1,0), tmp(*this); while (t) {
			if (t & 1) ret = ret * tmp;
			tmp = tmp * tmp; t >>= 1;
		} return ret; 
	} 
}tran,ans;

namespace AC_Automaton{
	#define ATM AC_Automaton
	int ch[N][SGZ],fail[N],val[N],cnt=1,vis[N];
	queue<int> que;
	
	inline void Add(char *s, int v){
		int w = 1, n = strlen(s+1);
		for (int i=1;i<=n;i++) {
			int c = s[i] - 'a' + 1;
			if (!ch[w]) ch[w] = ++cnt;
			w = ch[w];
		} val[w] += v;	
	}
	
	inline void Get_Fail(){
		que.push(1); fail[0] = fail[1] = 1; 
		for (int i=1;i<SGZ;i++) ch[1][i] = ch[1][i]?ch[1][i]:1;
		while (!que.empty()) {
			int w = que.front(); que.pop();
			val[w] += val[fail[w]]; vis[w] = 1;
			for (int c=1;c<SGZ;c++) if (ch[w]) {
				int nw = fail[w];
				while (nw > 1 && !ch[nw]) nw = fail[nw];
				fail[ch[w]] = nw!=w?ch[nw]:1; 
				if (!vis[ch[w]]) que.push(ch[w]);
			} else ch[w] = ch[fail[w]];
		}
	}
	
	inline void Build_Matrix(){
		ans.a[1][1] = 0;
		for (int i=1;i<=cnt;i++)
			for (int c=1;c<SGZ;c++) 
				tran.a[ch[i]][i] = val[ch[i]];	
	}
}; 

int main(){
	int n,val[N]; LL T; char pat[N]; cin>>n>>T;
	for (int i=1;i<=n;i++) cin>>val[i];
	for (int i=1;i<=n;i++) scanf("%s",pat+1), ATM::Add(pat,val[i]);
	ATM::Get_Fail(); ATM::Build_Matrix(); tran = tran^T; 
	ans = ans * tran; LL vout = 0; 
	for (int i=2;i<=MX;i++) vout = max(vout, ans.a[i][1]);
	printf("%I64d\n",vout);
 	return 0;
}

—– UPD 2016.10.2 —–
今天问了一下鏼爷,鏼爷给了一个非常简洁的证明:
最短路问题可以写成矩阵形式(比如倍增Floyd)
然后最短路显然满足结合律
然后这题对于矩乘的定义岂不是和最短路一样?

—————————— UPD 2017.2.1 ——————————
这题后来问了问YYY,结果YYY暴力展开矩乘
似乎这样就可以知道是否满足结合律了
不过如果在考场上,直接拍一拍吧
如果不出错,那就假装他满足结合律吧?