## 【AtCoder】[Grand Contest 015 F] Kenus the Ancient Greek

### Code

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

const int MOD = 1000000007;
const int LOG = 100;

vector<pair<LL, LL> > num[LOG];

char c = getchar(); LL 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 void solve(LL A, LL B) {
if (A < num[2][0].first || B < num[2][0].second) {
printf("1 %d\n", A * B % MOD);
return;
}
for (int i = 2; i < LOG; i++) {
if (A < num[i + 1][0].first || B < num[i + 1][0].second) {
int cnt = 0;
for (int j = 0; j < (int)num[i].size(); j++) {
LL a = num[i][j].first, b = num[i][j].second;
cnt = (cnt + (a <= A && b <= B? (B - b) / a + 1: 0)) % MOD;
cnt = (cnt + (b <= A && a <= B? (A - b) / a + 1: 0)) % MOD;
}
printf("%d %d\n", i, cnt);
return;
}
}
}

inline void prework() {
num[0] = vector<pair<LL,LL> >{make_pair(1, 1)};
for (int i = 1; i < LOG; i++) {
for (int j = 0; j < (int)num[i - 1].size(); ++j) {
LL a = num[i - 1][j].first, b = num[i - 1][j].second;
num[i].push_back(make_pair(b, a + b));
}
LL a = num[i - 1][0].first, b = num[i - 1][0].second;
num[i].push_back(make_pair(a + b, 2 * a + b));
}
}

int main() {
prework();
for (int T = read(); T; T--) {
solve(min(A, B), max(A, B));
}
return 0;
}


## 【Codeforces 212B】Polycarpus is Looking for Good Substrings

### Code

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

const int N = 1000009;
const int SGZ = 26;
const int M = 10009;

int n, m, nxt[N][SGZ], crt[N][SGZ], q[M], ans[M];
vector<int> val;
char s[N], qy[SGZ];

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 int index(int x) {
for (int l = 0, r = val.size() - 1, mid; l <= r; ) {
mid = l + r >> 1;
if (val[mid] == x) {
return mid;
} else if (val[mid] < x) {
l = mid + 1;
} else {
r = mid - 1;
}
}
return -1;
}

int main() {
scanf("%s", s);
n = strlen(s);
for (int i = 1; i <= m; i++) {
scanf("%s", qy);
int len = strlen(qy);
for (int j = 0; j < len; j++) {
q[i] |= 1 << qy[j] - 'a';
}
val.push_back(q[i]);
}
sort(val.begin(), val.end());
val.resize(unique(val.begin(), val.end()) - val.begin());
int last_position[SGZ];
fill(last_position, last_position + SGZ, n);
for (int i = n - 1; ~i; i--) {
last_position[s[i] - 'a'] = i;
for (int j = 0; j < SGZ; j++) {
nxt[i][j] = last_position[j];
}
}
memset(crt, -1, sizeof(crt));
for (int i = 0; i < n; i++) {
for (int j = 0, p = i, sta = 0; j < 26 && p < n; j++) {
int np = n, c = -1;
for (int k = 0; k < 26; k++) {
if ((sta >> k & 1) == 0) {
if (np > nxt[p][k]) {
c = k;
np = nxt[p][k];
}
}
}
if (~c) {
sta |= 1 << c;
p = np;
crt[i][j] = sta;
if (!i || crt[i - 1][j] != sta) {
int idx = index(sta);
if (~idx) {
ans[idx]++;
}
}
}
}
}
for (int i = 1; i <= m; i++) {
printf("%d\n", ans[index(q[i])]);
}
return 0;
}


## 【BZOJ 4735】你的生命已如风中残烛

### Code

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

const int MOD = 998244353;

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() {
int n = read(), m = 0, ans = 1;
for (int i=1;i<=n;i++) m += read();
for (int i=2;i<=m;i++) ans = ((LL)ans * ((i!=m-n+1)?i :1)) % MOD;
cout<<ans;
return 0;
}


## 【BZOJ 4294】[PA2015] Fibonacci

### 解题报告

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

## 【日常小测】苹果和雪梨

### 解题报告

$O(n^2)$枚举最大值是哪一对

### Code

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

const int N = 3009;
const int M = N * N;

LL n,tot,vout,ans,mx,a[N],b[N],p[N],q[N];
struct Match{int x,y;LL val;}m[M];

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 main() {
for (int i=1;i<=n;i++) a[i] = read();
for (int j=1;j<=n;j++) b[j] = read();
sort(a+1, a+1+n); sort(b+1, b+1+n);
for (int i=1;i<=n;i++) {
for (int j=1;j<=n;j++) {
m[++tot].val = a[i] * b[j];
m[tot].x = i; m[tot].y = j;
}
}
static auto cmp = [](const Match &A, const Match &B) {return A.val < B.val || (A.val == B.val && A.x < B.x) || (A.val == B.val && A.x == B.x && A.y < B.y);};
sort(m+1, m+1+tot, cmp);
for (int i=1;i<=n;i++)
mx = max(mx, a[i] * b[n-i+1]);
for (int i=n;i;i--) {
for (int j=n;j;j--) {
if (!q[j] && a[i] * b[j] <= mx) {
q[j] = i; p[i] = j;
ans += a[i] * b[j];
break;
}
}
}
vout = ans - mx;
for (int i=1,x,y,nx,ny;i<=tot;i++) {
if (m[i].val <= mx) continue;
x = m[i].x; y = m[i].y; nx = p[x]; ny = q[y];
p[ny] = nx; q[nx] = ny; p[x] = y; q[y] = x;
ans += a[x] * b[y] + a[ny] * b[nx];
ans -= a[x] * b[nx] + a[ny] * b[y];
vout = max(vout, ans - m[i].val);
}
printf("%lld\n",vout);
return 0;
}


## 【BZOJ 2986】Non-Squarefree Numbers

### 解题报告

prefix_sum_of_mobius_function

## 【BZOJ 3997】[TJOI2015] 组合数学

### 解题报告

Dilworth定理：DAG的最小链覆盖=最大点独立集

### Code

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

const int N = 1000+9;

int n,m,val[N][N],f[N][N],g[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() {
memset(f,0,sizeof(f));
memset(g,0,sizeof(g));
for (int j=1;j<=m;j++) {
for (int i=1;i<=n;i++) {
}
}
for (int i=1;i<=n;i++) {
for (int j=m,cur=0;j;j--) {
f[i][j] = cur + val[i][j];
cur = max(cur, g[j]);
g[j] = max(g[j], f[i][j]);
}
}
int vout = 0;
for (int i=1;i<=m;i++)
vout = max(vout, g[i]);
printf("%d\n",vout);
}
return 0;
}


## 【BZOJ 3994】[SDOI2015] 约数个数和

### Code

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

const int N = 50000+9;

int n,m,tot,pri[N],mu[N],d[N],sum[N],f[N];
bool vis[N]; LL vout;

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 prework() {
mu[1] = 1;
for (int i=2;i<N;i++) {
if (!vis[i]) pri[++tot] = i, mu[i] = -1;
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;}
}
}
for (int i=1;i<N;i++)
for (int j=i;j<N;j+=i)
d[j]++;
for (int i=1;i<N;i++) {
f[i] = f[i-1] + d[i];
sum[i] = sum[i-1] + mu[i];
}
}

int main() {
prework();
if (m > n) swap(n, m);
for (int l=1,r;l<=m;l=r+1) {
r = min(n / (n / l), m / (m / l));
vout += (LL)(sum[r] - sum[l-1]) * f[n/l] * f[m/l];
}
printf("%lld\n",vout);
}
return 0;
}


## 【BZOJ 4722】由乃

### 解题报告

More Formally：次数会爆 $long long$

## 【Codeforces 711E】ZS and The Birthday Paradox

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

const LL MOD = 1000003;

char c=getchar(); LL 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 LL pow(LL w, LL t) {
LL ret = 1;
while (t) {
if (t & 1) ret = ret*w % MOD;
w = w*w % MOD; t >>= 1;
}
return ret;
}

inline bool judge(LL n, LL k) {
LL w = 1;
for (int i=1;i<=n;i++) {
w *= 2;
if (w >= k) return false;
} return true;
}

int main(){
if (judge(n,k)) cout<<1<<' '<<1;
else {
LL t1, t2, cnt = (k-1) - __builtin_popcountll(k-1), gcd = pow(pow(2,cnt),MOD-2);
if (k >= MOD) t1 = 0; else {t1 = 1; for (int i=1;i<k;i++) t1 = t1 * (tn - i) % MOD;}
t2 = pow(pow(2,n),k-1); t2 = t2 * gcd % MOD; t1 = t1 * gcd % MOD; t1 = ((t2 - t1)% MOD + MOD) % MOD;
cout<<t1<<' '<<t2;
}
return 0;
}


ps:如果不知道上面的那个定理，貌似自己推也是可以推出来的？

## 【BZOJ 1997】[Hnoi2010] Planar

1.圆内
2.圆外

Theorem 1. If v ≥ 3 then e ≤ 3v − 6;
Theorem 2. If v ≥ 3 and there are no cycles of length 3, then e ≤ 2v − 4.

#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<set>
#include<map>
using namespace std;

const int MAXN = 20000+9;
const int N = 200000;

vector<int> G[MAXN];
map<int,int> ins;

struct CMP{inline bool operator () (const int &A, const int &B) {return R[A] < R[B];}};
multiset<int,CMP>::iterator itr;
multiset<int,CMP> buf;

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

inline void init(){
for (int i=1;i<=n;i++) G[i].clear();
memset(mark,0,sizeof(mark));
}

inline void AddEdge(int a, int b) {
int ra=a*2+1, rb=b*2+1; a *= 2; b *= 2;
}

inline void build_map(){
buf.clear();
for (int i=1;i<=n;i++) {
while (buf.size() && R[*(buf.begin())] <= i) buf.erase(buf.begin());
for (int j=0,sz=G[i].size();j<sz;j++)
for (itr=buf.begin();itr!=buf.end() && R[*itr] < R[G[i][j]];itr++)
for (int j=0,sz=G[i].size();j<sz;j++) buf.insert(G[i][j]);
}
}

bool DFS(int w) {
if (mark[w]) return true;
if (mark[w^1]) return false;
mark[w] = 1; que[++cnt] = w;

if (!DFS(to[i])) return false;
return true;
}

inline bool judge(){
for (int i=2;i<=m*2+1;i+=2) if (!mark[i] && !mark[i+1]) {
cnt = 0; if (DFS(i)) continue;
for (int j=1;j<=cnt;j++) mark[que[j]] = 0;
cnt = 0; if (!DFS(i+1)) return false;
}
return true;
}

int main(){
int TT = read(); while (TT--) { init();
for (int i=1;i<=n;i++) que[i] = read(), ins[que[i]] = i;
for (int i=1;i<=m;i++) {
L[i] = ins[L[i]]; R[i] = ins[R[i]];
if (L[i] > R[i]) swap(L[i], R[i]);
G[L[i]].push_back(i);
}
if (m > 3*n-6) printf("NO\n");
else {
build_map();
if (judge()) printf("YES\n");
else printf("NO\n");
}
}
return 0;
}