## 【TopCoder SRM713】CoinsQuery

### 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] 魔法咒语

### 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];

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;

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);
}
};

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() {
if (L <= 100) {
} else {
}
return 0;
}


## 【日常小测】迷宫

### 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;

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);
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】数论小测验

### Code

#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];

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() {
if (type == 1) {
GetMu();
for (int t=1,vout;vout=0,t<=T;t++) {
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++) {
for (int w=l;w<=r;w++) vout = (vout + solve(w)) % MOD;
printf("%d\n",vout);
}
}
return 0;
}


## 【日常小测】排列

### 解题报告

GEOTCBRL就是用这个A的，太强大了_(:з」∠)_

### Code

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

const int MOD = 1000000007;

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] 序列统计

### Code

#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];

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() {
int PRT = Get_Primitive_Root(m);
for (int cur=1,i=0;i<m-1;i++,cur=cur*PRT%m) pos[cur] = i;
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

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

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

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(){
for (int i=1;i<=n;i++) {
}
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++) {
if (ty == 1) {
} else {
printf("%d\n",SEG::query(a,b));
}
}
return 0;
}


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

#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;

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(){
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…

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

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

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];
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 —–

—————————— UPD 2017.2.1 ——————————