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


## 【日常小测】学外语

### Code

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

const int N = 1000009;
const int MOD = 1000000007;
const int INF = 2e9;

int n, E, ans, head[N], nxt[N], to[N];
int inv[N], pw[N], ipw[N], pw23[N], R1[N], R2[N];
int pre[N], dep[N], in[N], deg[N], vis[N];

char c = getchar();
int ret = 0, f = 1;
for (; c < '0' || c > '9'; c = getchar()) {
f = c == '-'? -1: 1;
}
for (; '0' <= c && c <= '9'; c = getchar()) {
ret = ret * 10 + c - '0';
}
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 AddEdge(int u, int v) {
in[v]++; deg[v]++; pre[u] = v;
}

inline void mrk(int w) {
vis[w] = 1;
if (--in[pre[w]] == 0) {
mrk(pre[w]);
}
}

inline int cal_node(int w) {
int ret = R2[deg[w]];
vector<int> arr;
for (int i = head[w]; i; i = nxt[i]) {
if (!in[to[i]]) {
dep[to[i]] = dep[w] + 1;
int tmp = cal_node(to[i]);
arr.push_back(tmp);
ret = (ret + (LL)R1[dep[w]] * tmp) % MOD;
}
}
sort(arr.begin(), arr.end());
for (int i = 0, j = 0; i < (int)arr.size(); i = j + 1) {
for (; j + 1 < (int)arr.size() && arr[i] == arr[j + 1]; ++j);
ans = (LL)ans * ipw[j - i + 1] % MOD;
}
return (LL)ret * ret % MOD;
}

inline int cal_cir(int w) {
vector<int> node, arr;
while (!vis[w]) {
vis[w] = 1;
node.push_back(w);
for (int i = head[w]; i; i = nxt[i]) {
if (in[to[i]]) {
w = to[i];
break;
}
}
}
for (int i = 0; i < (int)node.size(); i++) {
dep[node[i]] = 6;
arr.push_back(cal_node(node[i]));
}
int sta = 0, cnt = 1;
for (int i = 0; i < (int)node.size(); i++) {
sta = (sta + (LL)pw23[i] * arr[i]) % MOD;
}
int ret = (LL)sta * pw23[n] % MOD;
for (int i = 1, cur = sta; i < (int)node.size(); i++) {
cur = (cur + (LL)arr[i - 1] * (pw23[i - 1 + node.size()] - pw23[i - 1])) % MOD;
ret = min(ret, int((LL)cur * pw23[n - i] % MOD));
cnt += ((cur = (cur + MOD) % MOD) == (LL)sta * pw23[i] % MOD);
}
ans = (LL)ans * inv[cnt] % MOD;
return ret;
}

int main() {
srand(19991216);
inv[0] = pw[0] = ipw[0] = pw23[0] = 1;
R1[0] = rand(); R2[0] = rand();
for (int i = 1; i < N; i++) {
pw[i] = (LL)pw[i - 1] * i % MOD;
pw23[i] = pw23[i - 1] * 131ll % MOD;
inv[i] = Pow(i, MOD - 2);
ipw[i] = Pow(pw[i], MOD - 2);
R1[i] = rand(); R2[i] = rand();
}

for (int T = read(); T; T--) {
memset(deg, 0, sizeof(deg));
memset(vis, 0, sizeof(vis));
memset(in, 0, sizeof(in));
E = 0; ans = 1;

for (int i = 1; i <= n; i++) {
}
for (int i = 1; i <= n; i++) {
if (!in[i] && !vis[i]) {
mrk(i);
}
}
vector<int> arr;
for (int i = 1; i <= n; i++) {
if (in[i] && !vis[i]) {
arr.push_back(cal_cir(i));
}
}
sort(arr.begin(), arr.end());
for (int i = 0, j = 0; i < (int)arr.size(); i = j + 1) {
for (; j + 1 < (int)arr.size() && arr[i] == arr[j + 1]; ++j);
ans = (LL)ans * ipw[j - i + 1] % MOD;
}
ans = ((LL)ans * pw[n] - 1) % MOD;
printf("%d\n", (ans + MOD) % MOD);
}
return 0;
}


## 【TopCoder SRM713】PowerEquation

### Code

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

const int MOD = 1000000007;
const int N = 100000;

int gcd[100][100];
bool vis[N];

class PowerEquation {
public:
int count(int n) {
memset(vis, 0, sizeof(vis));
for (int i=1;i<=50;i++) {
for (int j=1;j<=50;j++) {
gcd[i][j] = GCD(i, j);
}
}

int ret = (LL)n * n % MOD, dec = 0;
for (int i=2;1;i++) {
if (i * i > n) {
ret = (ret + (n - i + 1ll - dec) * n) % MOD;
break;
} else {
if (vis[i]) continue;
for (LL j=i*i;j<=n;j*=i) {
if (j * j <= n) vis[j] = 1;
else ++dec;
}

int mx = 1, tmp = 0; LL cur = i;
while (cur * i <= n) cur *= i, ++mx;
for (int a=1;a<=mx;a++) {
for (int b=1;b<=mx;b++) {
int c = max(b,a) / gcd[a][b];
tmp = (tmp + n / c) % MOD;
}
}
ret = (ret + tmp) % MOD;
}
}
return ret;
}
private:
int GCD(int a, int b) {
return b? GCD(b, a%b): a;
}
};


## 【Codeforces 797D】Broken BST

### Code

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

const int N = 200009;

int n,rt,is_rt[N],val[N],ch[N][2],TOT[N];
int tot,_hash[N],cnt[N],dep[N],vout;
set<pair<int,int> > id[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;
}

void dfs(int w, int f) {
dep[w] = dep[f] + 1;
if (ch[w][1]) dfs(ch[w][1], w);
if (ch[w][0]) dfs(ch[w][0], w);
}

void add(int w, int sta) {
if (w <= 0) return;
id[val[w]].insert(make_pair(dep[w], w));
cnt[val[w]]++;
if (val[w] > sta) add(ch[w][0], sta);
}

void del(int w, int sta) {
if (w <= 0) return;
id[val[w]].erase(make_pair(dep[w], w));
cnt[val[w]]--;
if (val[w] > sta) del(ch[w][0], sta);
else del(ch[w][1], sta);
}

int main() {
for (int i=1,l,r;i<=n;i++) {
val[i] = read(); _hash[++tot] = val[i];
if ((l = read()) != -1) ch[i][0] = l, is_rt[l] = 1;
if ((r = read()) != -1) ch[i][1] = r, is_rt[r] = 1;
}
for (int i=1;i<=n;i++) if (!is_rt[i]) {rt = i; break;}
dfs(rt, rt);
sort(_hash+1, _hash+1+tot);
tot = unique(_hash+1, _hash+1+tot) - _hash - 1;
for (int i=1;i<=n;i++) val[i] = lower_bound(_hash+1, _hash+1+tot, val[i]) - _hash, TOT[val[i]]++;

if (!cnt[1]) vout += TOT[1];
for (int i=2,w;i<=tot;i++) {
if (id[i].size() > 0) {
auto tmp = id[i].begin();
w = tmp->second;
del(w, i-1);
}
if (cnt[i] == 0) vout += TOT[i];
}
printf("%d\n",vout);
return 0;
}


## 【CodeChef DINING】[January Cook-off 2014] Dining

### 解题报告

【BZOJ 3992】[SDOI2015] 序列统计

## 【BZOJ 3028】食物

### Code

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

const int MOD = 10007;
const int REV = 1668;

int main() {
int n=0; char pat[600]; cin>>pat+1;
for (int i=1;i<=strlen(pat+1);i++)
n = (n * 10 + pat[i] - '0') % MOD;
cout<<n*(n+1ll)*(n+2)*REV%MOD;
return 0;
}


## 【日常小测】cut

### Code

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

const int N = 109;
const int M = N * N << 1;
const int INF = 1e9;

struct Data{
int u,v,val;
inline Data() {}
inline Data(int a, int b, int c):u(a),v(b),val(c) {}
inline bool operator < (const Data &B) const {
return val > B.val;
}
}p[N*N*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, int c) {
static int E = 1; cost[E+1] = cost[E+2] = c;
}

int cal(int w, int f, int pur, int mn) {
if (w == pur) return mn;
if (to[i] != f) {
tmp = cal(to[i], w, pur, min(mn, cost[i]));
if (~tmp) return tmp;
}
} return -1;
}

int find(int x) {return x==fa[x]? x: fa[x]=find(fa[x]);}

int main() {
for (int i=1,v;i<=n;i++) {
fa[i] = i;
for (int j=1;j<=n;j++) {
p[++tot] = Data(i, j, v);
}
}
sort(p+1, p+1+tot);
for (int i=1;i<=tot;i++) {
int u=p[i].u, v=p[i].v, val=p[i].val;
if (find(u) == find(v)) {if(cal(u,u,v,INF)!=val)cout<<-1,exit(0);}
else fa[find(u)] = fa[v], AddEdge(u, v, val);
}
cout<<n-1<<endl;
for (int i=2;to[i];i+=2) printf("%d %d %d\n",to[i],to[i+1],cost[i]);
return 0;
}


## 【日常小测】计数

### 一句话题意

$n_1,n_2,n_3,n_4 \le 10^3$

[1]ABAB…A
[2]BABA…B
[3]ABAB…B
[4]BABA…A

### Code

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

const int MOD = 1000000007;
const int N = 2009;

int vout,f[N],g[N],C[N][N],PW2[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 int solve(int a, int b, int c) {
if (a < b) swap(a, b);
if (!a && b) return b == c;
int ret = 0;
for (int i=a-b,j,k;i<=c;++i) {
j = i - a + b; k = c - i - j;
if (j >= 0 && k >= 0 && a >= i + k ) {
(ret += (((LL)C[i] * C[j][c-i] % MOD) * PW2[k] % MOD) * C[c-1][a-i-k+c-1] % MOD) %= MOD;
}
}
return ret;
}

int main() {
PW2[0] = 1; for (int i=1;i<N;i++) PW2[i] = (PW2[i-1] << 1) % MOD;
C[0][0] = 1; for (int i=1;i<N;i++) {
C[0][i] = 1; for (int j=1;j<=i;j++) {
C[j][i] = (C[j-1][i-1] + C[j][i-1]) % MOD;
}
}
if (a + b == 0) f[1] = 1;
else for (int i=1;i<=a+b;i++) f[i] = solve(a, b, i);
if (c + d == 0) g[1] = 1;
else for (int i=1;i<=c+d;i++) g[i] = solve(c, d, i);
for (int i=1;i<=a+b;i++) (vout += f[i] * (g[i-1] + 2ll * g[i] + g[i+1]) % MOD) %= MOD;
printf("%d\n",vout);
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() {