## 【日常小测】三明治

### Code

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

const int N = 500;
const int INF = 1e7;

char mp[N][N];
int n, m, ans[N];
bool up[N][N], dw[N][N], InStack[N][N], vis[N][N];

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

inline int F(int x, int y, int t) {
InStack[y][x] = 1;
int nx = x + (t == 1? 1: -1), ny = y, nt = t, ret = 1;
ret += vis[ny][nx]? 0: (InStack[ny][nx]? INF: F(nx, y, t));
nx = x; ny = up[y][x] == t? y - 1: y + 1; nt = up[y][x] == t? up[ny][nx]: dw[ny][nx];
ret += vis[ny][nx] || ret >= INF? 0: (InStack[ny][nx]? INF: F(nx, ny, nt));
vis[y][x] = 1;
InStack[y][x] = 0;
return ret > INF? INF: ret;
}

inline void init() {
memset(vis, 0, sizeof(vis));
for (int j = 1; j <= m; j++) {
vis[j][0] = 1;
vis[j][n + 1] = 1;
}
for (int i = 1; i <= n; i++) {
vis[0][i] = 1;
vis[m + 1][i] = 1;
}
}

int main() {
for (int j = 1; j <= m; j++) {
scanf("%s", mp[j] + 1);
for (int i = 1; i <= n; i++) {
up[j][i] = 1;
dw[j][i] = 0;
if (mp[j][i] == 'Z') {
swap(up[j][i], dw[j][i]);
}
}
}
for (int j = 1; j <= m; j++) {
init();
for (int i = n; i; i--) {
ans[i] = ans[i + 1] < INF? F(i, j, 1) + ans[i + 1]: INF;
}
init();
for (int i = 1; i <= n; i++) {
ans[i] = min(ans[i], ans[i - 1] < INF? F(i, j, 0) + ans[i - 1]: INF);
printf("%d ", ans[i] >= INF? -1: ans[i] << 1);
}
putchar('\n');
}
return 0;
}


## 【BZOJ 2471】Count

### Code

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

const int N = 16;
const int M = 10;
const int SGZ = 10;
const int MOD = 1000000007;

int n, m, nxt[M];
char s[M];
struct Transfer{
LL pos, cnt;
inline Transfer() {
}
inline Transfer(LL a, LL b):pos(a), cnt(b) {
}
inline Transfer operator + (const Transfer &T) {
return Transfer(T.pos, cnt + T.cnt);
}
}t[M][SGZ];
map<int, Transfer> f[N][M];
struct MatchStatus{
int HashVal;
Transfer t[M];
inline void GetHashVal() {
const static int MOD = 1000000007;
const static int SEED1 = 13, SEED2 = 131;
HashVal = 0;
for (int i = 0; i < m; i++) {
HashVal = (HashVal + (LL)t[i].pos * SEED2 + t[i].cnt) * SEED1 % MOD;
}
}
inline bool operator < (const MatchStatus &MS) const {
return HashVal < MS.HashVal;
}
};

inline Transfer DFS(int w, int p, const MatchStatus &cur) {
if (w <= 0) {
return cur.t[p];
} else if (f[w][p].count(cur.HashVal)) {
return f[w][p][cur.HashVal];
} else {
Transfer ret(p, 0);
for (int i = 0; i < SGZ; i++) {
MatchStatus nw = cur;
for (int j = 0; j < m; j++) {
nw.t[j] = nw.t[j] + t[nw.t[j].pos][i];
}
nw.GetHashVal();
ret = ret + DFS(w - 1, ret.pos, nw);
}
return f[w][p][cur.HashVal] = ret;
}
}

int main() {
while (~scanf("%d %s", &n, s + 1) && n) {
m = strlen(s + 1);
for (int i = 1; i <= m; i++) {
s[i] -= '0';
}
nxt[1] = 0;
for (int i = 2, j = 0; i <= m; nxt[i++] = j) {
for (; j && s[j + 1] != s[i]; j = nxt[j]);
j += s[j + 1] == s[i];
}
for (int i = 0; i < m; i++) {
for (int j = 0; j < SGZ; j++) {
int k = i;
for (; k && s[k + 1] != j; k = nxt[k]);
k += s[k + 1] == j;
t[i][j] = k == m? Transfer(nxt[k], 1): Transfer(k, 0);
}
}
for (int i = 1; i <= n; i++) {
for (int j = 0; j < m; j++) {
f[i][j].clear();
}
}
Transfer ans(0, 0);
for (int i = 1; i <= n; i++) {
for (int j = 1; j < SGZ; j++) {
MatchStatus cur;
for (int k = 0; k < m; k++) {
cur.t[k] = t[k][j];
}
cur.GetHashVal();
ans = ans + DFS(i - 1, ans.pos, cur);
}
}
printf("%lld\n", ans.cnt);
}
return 0;
}


## 【AtCoder】[Regular Contest 075 F] Mirrored

### Code

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

int *mth, *spj, a2[100], a1[100];

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

LL DFS(LL res, LL l, LL r) {
if (l <= r) {
if (res == 0) {
return l == r? 10: 1;
} else {
return 0;
}
} else {
LL ret = 0, cur = l - r;
l /= 10; r *= 10;
for (int i = -9; i <= 9; i++) {
if (abs(res - i * cur) < l * 11) {
ret += mth[i] * DFS(res - i * cur, l, r);
}
}
return ret;
}
}

int main() {
mth = a1 + 50;
spj = a2 + 50;
for (int i = 0; i <= 9; i++) {
for (int j = -9; j <= 0; j++) {
mth[i + j]++;
}
}
for (int i = 1; i <= 9; i++) {
for (int j = -9; j <= 0; j++) {
spj[i + j]++;
}
}
LL ans = 0, D = -read();
for (LL mx = 1e18; mx >= 10; mx /= 10) {
LL delta = mx - 1;
for (int i = -8; i <= 9; i++) {
ans += spj[i] * DFS(D - i * delta, mx / 10, 10);
}
}
cout<<ans<<endl;
return 0;
}


## 【BZOJ 4801】打牌

### Code

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

int a[5][5],cur[3][3];

char s[5]; scanf("%s",s);
if (s[0] == 'A') return 14;
if (s[0] == 'K') return 13;
if (s[0] == 'Q') return 12;
if (s[0] == 'J') return 11;
if (s[0] == 'T') return 10;
return s[0] - '0';
}

inline int val(int x) {
if (x == 14) return 1;
else return x;
}

int solve(int t) {
if (t == 1) {
cur[0][0] = a[0][0]; cur[0][1] = a[0][1];
int s1 = solve(2);
swap(cur[0][0], cur[0][1]);
int s2 = solve(2);
return max(s1, s2);
} else if (t == 2) {
cur[1][0] = a[1][0]; cur[1][1] = a[1][1];
int s1 = solve(3);
swap(cur[1][0], cur[1][1]);
int s2 = solve(3);
return min(s1, s2);
} else {
if (cur[0][0] >= cur[1][0]) {
if (cur[0][1] >= cur[1][1]) {
return val(cur[0][0]) + val(cur[0][1]);
} else {
return val(cur[0][0]) - val(cur[1][1]);
}
} else {
if (cur[0][1] > cur[1][1]) {
return -val(cur[1][0]) + val(cur[0][1]);
} else {
return -val(cur[1][0]) - val(cur[1][1]) ;
}
}
}
}

int main() {
int t; cin>>t;
for (;t;t--) {
printf("%d\n",solve(1));
}
return 0;
}


## 【Codeforces 797E】Array Queries

### Code

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

const int N = 100009;

struct Query{int p,k,id;}q[N];
int n,m,stp[N],a[N],ans[N];
queue<int> vis;

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(const Query &A, const Query &B) {
return A.k < B.k;
}

inline void init() {
for (;!vis.empty();vis.pop()) {
stp[vis.front()] = 0;
}
}

int DFS(int w, int k) {
if (w > n) return 0;
else if (stp[w] > 0) return stp[w];
else return vis.push(w), stp[w] = DFS(w + a[w] + k, k) + 1;
}

int main() {
sort(q+1, q+1+m, cmp);
for (int i=1;i<=m;i++) {
if (i > 1 && q[i].k != q[i-1].k) init();
ans[q[i].id] = DFS(q[i].p, q[i].k);
}
for (int i=1;i<=m;i++) printf("%d\n",ans[i]);
return 0;
}


## 【BZOJ 4294】[PA2015] Fibonacci

### 解题报告

Fibonacci数列在$\bmod 10^n$的时候，循环节为$6 \times 10^n$

## 【Codeforces 747F】Igor and Interesting Numbers

### Code

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

int k,t,C[21][21],res[21];
char ori[]={'0','1','2','3','4','5','6','7','8','9','a','b','c','d','e','f'};

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 LL solve(int len, bool ty) {
static LL f[2][20]; bool w,p;
memset(f,0,sizeof(f));
f[p=0][ty] = 1; w = 1;
for (int i=0;i<16;i++,w^=1,p^=1) {
memset(f[w],0,sizeof(f[w]));
for (int j=len;~j;j--)
for (int k=min(len-j,res[i]-(ty&(i==0)));~k;k--)
f[w][j+k] += f[p][j] * C[k][len-j];
}
return f[p][len];
}

int main() {
for (int i=0;i<=20;i++) {
C[0][i] = C[i][i] = 1;
for (int j=1;j<i;j++)
C[j][i] = C[j-1][i-1] + C[j][i-1];
}
for (int i=0;i<=15;i++)
res[i] = t;
LL tmp; int len=1;
while ((tmp = solve(len,0) - solve(len,1)) < k)
k -= tmp, len++;
for (int i=len,ret=1;i;ret=0,i--) {
res[ret]--;
while ((tmp = solve(i-1,0)) < k)
res[ret++]++, res[ret]--, k -= tmp;
printf("%c",ori[ret]);
}
return 0;
}


## 【BZOJ 1053】[HAOI2007] 反素数ant

### 题解

1.质因数是连续的，也就是说我们只用考虑37及之前的质因数
2.较大的质因数个数一定少于较小的质因数的个数

### Code

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

const int SZ = 12;

int n,num,vout,pri[]={0,2,3,5,7,11,13,17,19,23,29,31,37};

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 DFS(int t, int last, int w, int v) {
if (t == 13) {
if (v == num) {
vout = min(vout, w);
} else if (v > num) {
vout = w;
num = v;
}
} else {
for (int i=0,cur=1;i<=last;i++,cur*=pri[t]) {
if ((LL)cur * w > n) break;
else {
DFS(t+1, i, w*cur, v*(i+1));
}
}
}
}

int main(){
puts("1");
} else {
DFS(1,30,1,1);
printf("%d\n",vout);
}
return 0;
}


## 【BZOJ 1024】[SCOI2009] 生日快乐

#include<bits/stdc++.h>
#define LL long long
#define abs(x) ((x)<0?-(x):(x))
using namespace std;

const double INF = 1e9;
const double EPS = 1e-3;

struct Data{
double x,y,val;
inline Data() {}
inline Data(double x, double y, double val):x(x),y(y),val(val) {
if (x < y) swap(x, y);
}
inline bool operator < (const Data &tmp) const {
if (abs(tmp.x - x) < EPS && abs(tmp.y - y) < EPS) return 0;
else if (tmp.x - x > EPS) return 1;
else if (x - tmp.x > EPS) return 0;
else if (tmp.y - y > EPS) return 1;
else return 0;
}
};
set<Data> S;
set<Data>::iterator itr;

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

double DFS(double x, double y, int n) {
if (n == 1) {
if (x < y) swap(x, y);
return x / y;
} else {
itr = S.find(Data(x,y,0));
if (itr != S.end()) return itr->val;
else {
double ret = INF;
for (int i=1;i*2<=n;i++) {
ret = min(ret, max(DFS(x*i/n,y,i), DFS(x*(n-i)/n,y,n-i)));
ret = min(ret, max(DFS(x,y*i/n,i), DFS(x,y*(n-i)/n,n-i)));
}
S.insert(Data(x,y,ret));
return ret;
}
}
}

int main(){
printf("%.6lf\n",DFS(x,y,n));
return 0;
}


## 【日常小测】subset

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

const int N = 300;
const int MX = 256;

int f[N][N],n;
char pat[10];

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 modify(int w, int delta) {
for (int i=0;i<MX;i++) {
if ((i&w)==(w&255)) {
f[i][w>>8] += delta;
}
}
}

inline int query(int w) {
int ret = 0;
for (int i=0,sta=w>>8;i<MX;i++) {
if ((i&sta)==i) {
ret += f[w&255][i];
}
}
return ret;
}

int main(){
freopen("subset.in","r",stdin);
freopen("subset.out","w",stdout);
for (int i=1;i<=n;i++) {
scanf("%s",pat+1);
}
return 0;
}