## 【BZOJ 4197】[NOI2015] 寿司晚宴

### Code

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

const int N = 509;
const int M = 6561;

int pri[] = {2, 3, 5, 7, 11, 13, 17, 19};
int n, gpri[N], spri[N], sta1[M], sta2[M], tt[M][N][3];
LL MOD, *f, *g, *h, arr1[M], arr2[M], arr3[M], ori[M];
vector<int> sta[N];

inline void relax(LL &a, LL b) {
a = (a + b) % MOD;
}

inline int num(int x, int t) {
for (; t; x /= 3, t--);
return x % 3;
}

inline int SET(int w, int t, int v) {
static int buf[] = {1, 3, 9, 27, 81, 243, 729, 2187};
int ret = 0;
for (int i = 0; i < 8; i++, w /= 3, t >>= 1) {
if (t & 1) {
ret += buf[i] * v;
} else {
ret += buf[i] * (w % 3);
}
}
return ret;
}

int main() {
freopen("dinner.in", "r", stdin);
freopen("dinner.out", "w", stdout);
cin>>n>>MOD;
for (int i = 0; i < M; i++) {
for (int j = 0; j < 8; j++) {
int t = num(i, j);
if (t == 1) {
sta1[i] |= 1 << j;
} else if (t == 2) {
sta2[i] |= 1 << j;
}
}
}
for (int i = 0; i < M; i++) {
for (int j = 0; j < (1 << 8); j++) {
for (int k = 1; k <= 2; k++) {
tt[i][j][k] = SET(i, j, k);
}
}
}
for (int i = 2; i <= n; i++) {
gpri[i] = i;
for (int j = 0; j < 8; j++) {
if (gpri[i] % pri[j] == 0) {
spri[i] |= (1 << j);
while (gpri[i] % pri[j] == 0) {
gpri[i] /= pri[j];
}
}
}
}
f = arr1, g = arr2, h = arr3;
g[0] = f[0] = 1;
for (int i = 2; i <= n; i++) {
if (gpri[i] == 1) {
for (int j = M - 1; ~j; j--) {
if (g[j]) {
int sta = 0;
for (int k = 0; k < 8; k++) {
if (spri[i] >> k & 1) {
sta |= num(j, k);
}
}
if (sta == 0) {
relax(f[tt[j][spri[i]][1]], g[j]);
relax(f[tt[j][spri[i]][2]], g[j]);
} else if (sta < 3) {
relax(f[tt[j][spri[i]][sta]], g[j]);
}
}
}
memcpy(g, f, sizeof(arr1));
swap(f, g);
} else {
sta[gpri[i]].push_back(spri[i]);
}
}
for (int i = 2; i <= n; i++) {
if (!sta[i].empty()) {
memcpy(h, g, sizeof(arr1));
memcpy(ori, g, sizeof(arr1));
for (int j = 0; j < (int)sta[i].size(); j++) {
int vv = sta[i][j];
for (int k = M - 1; ~k; k--) {
if (g[k]) {
int s1 = vv & sta1[k];
if (!s1) {
relax(f[tt[k][vv][2]], g[k]);
}
}
}
memcpy(g, f, sizeof(arr1));
swap(f, g);
}
memcpy(f, h, sizeof(arr1));
for (int j = 0; j < (int)sta[i].size(); j++) {
int vv = sta[i][j];
for (int k = M - 1; ~k; k--) {
if (h[k]) {
int s2 = vv & sta2[k];
if (!s2) {
relax(f[tt[k][vv][1]], h[k]);
}
}
}
memcpy(h, f, sizeof(arr1));
swap(f, h);
}
for (int k = 0; k < M; k++) {
f[k] = g[k] = (f[k] + g[k] - ori[k]) % MOD + MOD;
}
}
}
LL ans = 0;
for (int i = 0; i < M; i++) {
relax(ans, f[i]);
}
printf("%lld\n", ans);
return 0;
}

## 【Codeforces 815C】Karen and Supermarket

### Code

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

const int N = 5009;
const LL INF = 1e14;

int n, head[N], nxt[N], to[N], sz[N];
LL b, f[N][N], g[N][N], c[N], d[N], t1[N], t2[N];

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 void AddEdge(int u, int v) {
static int E = 1;
}

inline void relax(LL &a, LL b) {
a = a > b? b: a;
}

inline void DFS(int w) {
f[w][0] = g[w][0] = 0;
for (int i = head[w]; i; i = nxt[i]) {
DFS(to[i]);
memcpy(t1, f[w], sizeof(t1));
memcpy(t2, g[w], sizeof(t2));
for (int j = 0; j <= sz[w]; j++) {
for (int k = 0; k <= sz[to[i]]; k++) {
relax(f[w][j + k], t1[j] + f[to[i]][k]);
relax(g[w][j + k], t2[j] + g[to[i]][k]);
}
}
sz[w] += sz[to[i]];
}
sz[w]++;
for (int i = sz[w] - 1; ~i; i--) {
g[w][i + 1] = g[w][i] + c[w] - d[w];
relax(f[w][i + 1], f[w][i] + c[w]);
relax(g[w][i + 1], f[w][i + 1]);
}
g[w][0] = 0;
}

int main() {
for (int i = 2; i <= n; i++) {
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
f[i][j] = g[i][j] = INF;
}
}
DFS(1);
for (int i = n; ~i; i--) {
if (g[1][i] <= b) {
printf("%d\n", i);
exit(0);
}
}
return 0;
}

## 【Codeforces 736C】Ostap and Tree

### Code

#include<bits/stdc++.h>
#define LL long long
#define relax(a, b, c) (a = (a + (LL)b * c) % MOD)
using namespace std;

const int N = 300;
const int MOD = 1000000007;
const int BAS = 120;

int n, K, head[N], nxt[N], to[N];
int *f[N], arr_back[N][N];

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

inline void AddEdge(int u, int v) {
static int E = 1;
}

inline void DFS(int w, int fa) {
static int arr1_back[N], *tmp = arr1_back + BAS;
f[w][-1] = f[w][K] = 1;
for (int i = head[w], t; i; i = nxt[i]) {
if ((t = to[i]) != fa) {
DFS(t, w);
for (int j = -K; j <= K; j++) {
tmp[j] = f[w][j];
f[w][j] = 0;
}
for (int j = -K; j <= K; j++) {
for (int k = -K - 1; k < K; k++) {
if (j >= 0 && k >= 0) {
relax(f[w][max(j, k)], tmp[j], f[t][k + 1]);
} else if ((j < 0 && k >= 0) || (j >= 0 && k < 0)) {
int ge = max(j, k), le = min(j, k);
if (ge + 1 >= -le) {
relax(f[w][ge], tmp[j], f[t][k + 1]);
} else {
relax(f[w][le], tmp[j], f[t][k + 1]);
}
} else {
relax(f[w][min(j, k)], tmp[j], f[t][k + 1]);
}
}
}
}
}
}

int main() {
for (int i = 1; i < n; i++) {
}
for (int i = 1; i <= n; i++) {
f[i] = arr_back[i] + BAS;
}
DFS(1, 1);
int ans = 0;
for (int i = 0; i <= K; i++) {
ans = (ans + f[1][i]) % MOD;
}
printf("%d\n", ans);
return 0;
}

## 【Codeforces 814E】An unavoidable detour for home

### Code

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

const int N = 52;
const int MOD = 1000000007;
const int REV2 = 500000004;

int n, f[N][N], s2[N], s3[N], buf[N][N][N], C[N][N], prm[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;
}

int main() {
for (int i = 2; i <= n; i++) {
s2[i] = s2[i - 1];
s3[i] = s3[i - 1];
s2[i]++;
} else {
s3[i]++;
}
}
C[0][0] = 1;
for (int i = 1; i <= n; i++) {
C[i][0] = 1;
for (int j = 1; j <= i; j++) {
C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % MOD;
}
}
prm[2] = 1;
for (int i = 3; i <= n; i++) {
prm[i] = REV2;
for (int j = 2; j < i; j++) {
prm[i] = (LL)prm[i] * j % MOD;
}
}
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= n; j++) {
for (int k = 0; k <= n; k++) {
if (i == 0 && j == 0 && k == 0) {
buf[i][j][k] = 1;
} else if (i == 0 && j == 0) {
for (int l = 2; l < k; l++) {
(buf[i][j][k] += ((LL)buf[i][j][k - 1 - l] * C[k - 1][l] % MOD) * prm[l + 1] % MOD) %= MOD;
}
} else if (i == 0) {
buf[i][j][k] = j > 1? (LL)(j - 1) * buf[i][j - 2][k] % MOD: 0;
(buf[i][j][k] += k? (LL)k * buf[i][j][k - 1] % MOD: 0) %= MOD;
} else {
buf[i][j][k] = j? (LL)j * buf[i - 1][j - 1][k] % MOD: 0;
(buf[i][j][k] += k? (LL)k * buf[i - 1][j + 1][k - 1] % MOD: 0) % MOD;
}
}
}
}
for (int i = 1; i <= n; i++) {
for (int j = 0; j < i; j++) {
if (f[i][j]) {
int t2 = s2[i] - s2[j];
int t3 = s3[i] - s3[j];
for (int k = i + 1; k <= n; k++) {
f[k][i] = (f[k][i] + (LL)f[i][j] * buf[k - i][t2][t3]) % MOD;
}
}
}
}
int ans = 0;
for (int i = 1; i <= n; i++) {
ans = (ans + (LL)f[n][i] * buf[0][s2[n] - s2[i]][s3[n] - s3[i]]) % MOD;
}
cout<<ans<<endl;
return 0;
}

## 【Codeforces 799D】Field expansion

### Code

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

const int N = 100009;
const int INF = 1e9;

int n,v[N],f[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 bool cmp(int a, int b) {
return a > b;
}

inline int solve(int a, int b, int h, int w) {
memset(f, 0, sizeof(f));
f[min(h, a)] = min(b, w);
int ans = 1;
for (int j=1;j<=n;j++,ans++) {
for (int i=a;i;i--) {
if (f[i]) {
int tt = min((LL)a, (LL)i * v[j]);
f[tt] = max(f[tt], f[i]);
if (tt == a && f[i] == b) {
return ans;
}
tt = min((LL)b, (LL)f[i] * v[j]);
f[i] = tt;
if (i == a && tt == b) {
return ans;
}
}
}
}
return INF;
}

int main() {
for (int i=1;i<=n;i++) {
}
sort(v+1, v+1+n, cmp);
n = min(n, 34);
if ((h >= a && w >= b) || (h >= b && w >= a)) {
puts("0");
exit(0);
}
int ans1 = solve(a, b, h, w);
int ans2 = solve(a, b, w, h);
if (ans1 >= INF && ans2 >= INF) {
puts("-1");
} else {
printf("%d\n",min(ans1, ans2));
}
return 0;
}

## 【BZOJ 4828】[HNOI2017] 大佬

### Code

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

const int N = 109;
const int M = 930000;

int n,m,mc,tot,MX,ispri[N],w[N],a[N],f[N][N];
pair<int,int> itm[M];

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 t, LL sum) {
if (t > MX) return;
else {
DFS(t + 1, sum);
if (ispri[t]) {
for (;sum*=t,sum<=1e8;) {
itm[++tot].first = sum;
DFS(t + 1, sum);
}
}
}
}

inline int cal(int x) {
int ret = x + 1;
for (int i=min(MX,x-1),cnt,tmp;i;i--) {
if (x % i) continue;
cnt = i + 1; tmp = x;
for (int j=i;j>1&&tmp>1;j--) {
while (tmp % j == 0) {
tmp /= j;
++cnt;
}
}
if (tmp == 1) {
ret = min(ret, cnt);
} else {
break;
}
}
return ret;
}

int main() {
for (int i=1;i<=n;i++) {
}
for (int j=1;j<=n;j++) {
}
//DP最多空出来的天数
memset(f, -1, sizeof(f));
f[1][mc] = 0;
for (int i=1;i<=n;i++) {
for (int j=a[i];j<=mc;j++) {
if (f[i][j] == -1) continue;
int t1 = min(j - a[i] + w[i], mc), t2 = j - a[i];
if (t1 >= 0) {
f[i + 1][t1] = max(f[i + 1][t1], f[i][j]);
}
if (t2 >= 0) {
f[i + 1][t2] = max(f[i + 1][t2], f[i][j] + 1);
}
}
}
MX = -1;
for (int j=2;j<=n+1;j++) {
for (int i=0;i<=mc;i++) {
MX = max(MX, f[j][i]);
}
}
//搞出每一个物品的最小花费
for (int j=2;j<=100;j++) {
ispri[j] = 1;
for (int i=2;i*i<=j;i++) {
if (j % i == 0) {
ispri[j] = 0;
}
}
}
DFS(1, 1);
for (int i=1;i<=tot;i++) {
itm[i].second = cal(itm[i].first);
}
itm[++tot] = make_pair(0, 0);
sort(itm+1, itm+1+tot);
//对于每个询问用一个双端队列
for (int tt=1;tt<=m;tt++) {
int C = read(), ans = 0;
for (int i=tot,pfx=1,cur=-1e9;i;i--) {
while (pfx <= tot && itm[pfx].first <= C - itm[i].first) {
cur = max(cur, itm[pfx].first - itm[pfx].second);
pfx++;
}
if (cur + itm[i].first - itm[i].second >= C - MX) {
ans = 1;
break;
}
}
printf("%d\n",ans);
}
return 0;
}

## 【TopCoder SRM713】DFSCount

### Code

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

int n,id[15];
bool g[15][15],vis[15];
LL f[15][17000],pw[15],pol[15];

class DFSCount {
public:
long long count(vector<string> G) {
pw[0] = 1;
for (int i=1;i<=14;i++) {
pw[i] = pw[i-1] * i;
}
n = G.size();
for (int i=0;i<n;i++) {
for (int j=0;j<n;j++) {
if (G[i][j] == 'Y') g[i][j] = 1;
else g[i][j] = 0;
}
}
memset(f, 0, sizeof(f));
for (int i=0;i<n;i++) {
f[i][(1<<n)-1] = 1;
}
for (int sta=(1<<n)-2;sta>0;sta--) {
for (int i=0;i<n;i++) {
if (!(sta&(1<<i))) continue;
for (int j=0;j<n;j++) {
vis[j] = (sta & (1 << j));
}
int cnt = 0;
for (int j=0;j<n;j++) {
if (g[i][j] && !(sta&(1<<j))) {
if (!vis[j]) {
DFS(j, ++cnt);
pol[cnt] = 0;
}
pol[id[j]] += f[j][(1<<j)|sta];
}
}
f[i][sta] = pw[cnt];
for (int j=1;j<=cnt;j++) {
f[i][sta] *= pol[j];
}
}
}
LL ret = 0;
for (int i=0;i<n;i++) {
ret += f[i][1<<i];
}
return ret;
}
private:
void DFS(int w, int ID) {
vis[w] = 1;
id[w] = ID;
for (int i=0;i<n;i++) {
if (g[w][i] && !vis[i]) {
DFS(i, ID);
}
}
}
};

## 【HDU 4626】Jinkeloid

### Code

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

const int N = 3000000;
const int M = 100009;
const int UNIVERSE = (1 << 20) - 1;
const int SGZ = 20;

char pat[M];
int n,m,sta;
LL a[N],f[N],zero;

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 void FWT(LL *arr, int len, int ty) {
for (int d=1;d<len;d<<=1) {
for (int i=0;i<=len;i+=d*2) {
for (int j=0;j<d;j++) {
LL t1 = arr[i+j], t2 = arr[i+j+d];
arr[i+j] = t1 + t2;
arr[i+j+d] = t1 - t2;
if (ty == -1) {
arr[i+j] /= 2;
arr[i+j+d] /= 2;
}
}
}
}
}

int main() {
memset(a, 0, sizeof(a));
scanf("%s",pat);
n = strlen(pat);
a[0]++; sta = zero = 0;
for (int i=0;i<n;i++) {
sta ^= 1 << pat[i] - 'a';
zero += a[sta]++;
}
FWT(a, UNIVERSE, 1);
for (int i=0;i<=UNIVERSE;i++) {
a[i] = a[i] * a[i];
}
FWT(a, UNIVERSE, -1);
a[0] = zero;
for (int i=1;i<=UNIVERSE;i++) {
a[i] /= 2;
}
for (int i=0;i<=UNIVERSE;i++) {
if ((i ^ UNIVERSE) < i) {
swap(a[i], a[i^UNIVERSE]);
}
}
for (int j=0;j<SGZ;j++) {
for (int i=0;i<=UNIVERSE;i++) {
if (i & (1<<j)) {
a[i^(1<<j)] += a[i];
}
}
}
for (int tt=1;tt<=m;tt++) {
int k = read(), sta = 0;
for (int i=1;i<=k;i++) {
scanf("%s",pat);
sta |= 1 << pat[0] - 'a';
}
printf("%lld\n",a[sta]);
}
}
return 0;
}

## 【HDU 4623】Crime

### Code

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

const int N = 3000000;
const int M = 16;

int n,mx,MX,MOD,f[N][M],cnt[M],bit[M],cur[M],sym[M],suf[M],leg[M][M];
int ty[]={0,1,2,3,2,4,5,6,2,3,7,8,5,9,10,11,2,1,5,1,7,12,13,1,5,4,14,3,10};

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

int gcd(int a, int b) {
return b? gcd(b, a%b): a;
}

inline void decode(int w, int *arr) {
for (int i=mx;i;i--) {
arr[i] = w % bit[i];
w /= bit[i];
}
}

inline int solve() {
memset(cnt,0,sizeof(cnt));
mx = MX = 0;
for (int i=1;i<=n;i++) {
cnt[ty[i]]++;
mx = max(mx, ty[i]);
}
for (int i=1;i<=mx;i++) {
bit[i] = cnt[i] + 1;
MX = MX * bit[i] + cnt[i];
}
suf[mx] = 1;
for (int i=mx-1;i;i--) {
suf[i] = suf[i+1] * bit[i+1];
}
memset(f,0,sizeof(f));
f[0][0] = 1;
for (int i=0;i<MX;i++) {
decode(i, cur);
for (int j=0;j<=mx;j++) {
if (!f[i][j]) continue;
for (int k=1;k<=mx;k++) {
if ((leg[k][j] || !j) && cur[k] < cnt[k]) {
int to = i + suf[k];
f[to][k] = (f[to][k] + (LL)f[i][j] * (cnt[k] - cur[k])) % MOD;
}
}
}
}
int ret = 0;
for (int i=1;i<=mx;i++) {
ret = (ret + f[MX][i]) % MOD;
}
return ret;
}

int main() {
for (int i=1;i<=28;i++) {
if (sym[ty[i]]) continue;
sym[ty[i]] = i;
}
for (int i=1;i<=14;i++) {
for (int j=1;j<=14;j++) {
if (gcd(sym[i], sym[j]) == 1) {
leg[i][j] = 1;
}
}
}
printf("%d\n",solve());
}
return 0;
}

## 【HDU 4628】Pieces

### Code

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

char s[20];
int n,f[1<<17];

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 bool judge(int x) {
int tot=0; char tmp[20];
for (int i=1;i<=n;i++,x>>=1) {
if (x&1) {
tmp[++tot] = s[i];
}
}
for (int i=1,j=tot;i<j;i++,j--) {
if (tmp[i] != tmp[j]) {
return 0;
}
}
return 1;
}

int main() {
memset(f,60,sizeof(f));
scanf("%s",s+1);
n = strlen(s+1);
for (int i=1,MX=1<<n;i<MX;i++) {
if (judge(i)) {
f[i] = 1;
} else {
for (int j=i;j;j=(j-1)&i) {
f[i] = min(f[i], f[j] + f[i^j]);
}
}
}
printf("%d\n",f[(1<<n)-1]);
}
return 0;
}

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

## 【TopCoder SRM712】AverageVarianceSubtree

### Code

long double 最后一个点被卡精度了，只能用__float128

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

const int N = 59;
const int M = N << 1;

class AverageVarianceSubtree {
__float128 ans,tot,val[N],s1[N][N],s2[N][N],s3[N][N],cnt[N][N];
public:
double average(vector<int> p, vector<int> weight) {
memset(s1,0,sizeof(s1)); memset(s2,0,sizeof(s2));
memset(s3,0,sizeof(s3)); memset(cnt,0,sizeof(cnt));

n = weight.size();
for (int i=1;i<=n;i++) val[i] = weight[i - 1];
for (int i=0;i<n-1;i++) AddEdge(i + 2, p[i] + 1);
DFS(1, 1);
for (int i=1;i<=n;i++) {
for (int j=1;j<=n;j++) {
ans += (s2[i][j] - s3[i][j] / j) / j;
tot += cnt[i][j];
}
}
return ans / tot;
}
private:
inline void AddEdge(int u, int v) {
}
void DFS(int w, int f) {
cnt[w][0] = cnt[w][1] = 1;
s1[w][1] = val[w];
s2[w][1] = s3[w][1] = val[w] * val[w];
if (to[i] != f) {
DFS(to[i], w);
for (int t=n;t;t--) {
for (int a=1,b;b=t-a,a<t;a++) {
s3[w][t] += s3[w][a] * cnt[to[i]][b] + s3[to[i]][b] * cnt[w][a] + 2 * s1[w][a] * s1[to[i]][b];
s1[w][t] += s1[w][a] * cnt[to[i]][b] + s1[to[i]][b] * cnt[w][a];
s2[w][t] += s2[w][a] * cnt[to[i]][b] + s2[to[i]][b] * cnt[w][a];
cnt[w][t] += cnt[w][a] * cnt[to[i]][b];
}
}
}
}
}
};

## 【日常小测】迷宫

### 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 3612】[HEOI2014] 平衡

### Code

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

const int N = 100009;
const int M = 11;

int n,K,MOD,f[N][M];

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

int main() {
memset(f,0,sizeof(f)); f[0][0] = 1;
for (int i=1,lim=n*K;i<=lim;i++) {
for (int k=1,LIM=min(i,K);k<=LIM;k++) {
f[i][k] = (f[i-k][k] + f[i-k][k-1]) % MOD;
if (i > n) f[i][k] = (f[i][k] - f[i-(n+1)][k-1]) % MOD;
}
}
for (int i=0,lim=n*K;i<=lim;i++) {
for (int k=0;k<K;k++) {
ans = (ans + (LL)f[i][k] * f[i][K-k]) % MOD;
ans = (ans + (LL)f[i][k] * f[i][K-k-1]) % MOD;
}
}
printf("%d\n",(ans+MOD)%MOD);
}
return 0;
}

## 【Codeforces 797F】Mice and Holes

### Code

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

const int N = 5009;
const LL INF = 1e15;

int n,m,sum,x[N];
LL f[N],tmp,cost[N];
pair<int,int> mdy[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;
}

int main() {
for (int i=1;i<=n;i++) x[i] = read(), f[i] = INF;
if (sum < n) puts("-1"), exit(0);
sort(x+1, x+1+n); sort(mdy+1, mdy+1+m);
for (int j=1,tot,pos;tot=mdy[j].second,pos=mdy[j].first,j<=m;j++) {
for (int i=1;i<=n;i++) cost[i] = abs(x[i] - pos) + cost[i-1];
for (int len=1;len=min(len,tot),tot>0;tot-=len,len<<=1) {
for (int l=n-len+1,r=n;l>0;--l,--r) {
f[r] = min(f[r], cost[r] - cost[l-1] + f[l-1]);
}
}
}
printf("%lld\n",f[n]);
return 0;
}