## 【日常小测】图片加密

### Code

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

const int N = 550000;
const int M = N << 1;
const int INF = 1e9;
const int MOD = 1004535809;

int n,m,L,a1[M],a2[N],o1[N],o2[N],leg[N],ans[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;
}

static char pat[20]; scanf("%s",pat+1); int ret = 0;
for (int i=8,w=1;i;i--,w<<=1) ret += (pat[i]-'0') * w;
return ret;
}

class Suffix_Array{
int len,tot,*rak,*que,bot[N],sa[M],arr1[M],arr2[M],height[N];
public:
inline void build() {
rak = arr1; que = arr2; len = n + m + 1;
a1[0] = -1; a1[len+1] = -2;
for (int i=1;i<=len;i++) ++bot[a1[i]];
for (int i=1;i<=100000;i++) bot[i] += bot[i-1];
for (int i=1;i<=len;i++) sa[bot[a1[i]]--] = i;
rak[sa[1]] = tot = 1;
for (int i=2;i<=len;i++) rak[sa[i]] = (a1[sa[i]]==a1[sa[i-1]])? tot: ++tot;
for (int l=1,cnt;cnt=0,l<=len;l<<=1) {
for (int i=len-l+1;i<=len;i++) que[++cnt] = i;
for (int i=1;i<=len;i++) if (sa[i]>l) que[++cnt] = sa[i] - l;
for (int i=0;i<=tot;i++) bot[i] = 0;
for (int i=1;i<=len;i++) bot[rak[i]]++;
for (int i=1;i<=tot;i++) bot[i] += bot[i-1];
for (int i=len;i;i--) sa[bot[rak[que[i]]]--] = que[i];
swap(que, rak); rak[sa[1]] = tot = 1;
for (int i=2;i<=len;i++)
if (que[sa[i]]==que[sa[i-1]]&&que[sa[i]+l]==que[sa[i-1]+l]) rak[sa[i]] = tot;
else rak[sa[i]] = ++tot;
if (tot >= len) break;
}
GetHeight();
}
inline void solve() {
for (int i=rak[n+2];height[i]>=m;i--) if (sa[i] <= n) leg[sa[i]] = 1;
for (int i=rak[n+2]+1;height[i]>=m;i++) if (sa[i] <= n) leg[sa[i]] = 1;
}
private:
inline void GetHeight() {
for (int i=1;i<=len;i++) {
int len = max(0, height[rak[i-1]] - 1);
int p1 = i + len, p2 = sa[rak[i]-1] + len;
while (a1[p1++] == a1[p2++]) len++;
height[rak[i]] = len;
}
}
}SA;

class Number_Theoretic_Transform{
int pos[M],REV,G;
public:
inline void init() {
for (L=1;L<n+m;L<<=1); G = 3;
int len = 1,tt=-1; while (len < L) len<<=1, ++tt; REV = Pow(L, MOD-2);
for (int i=1;i<len;i++) pos[i] = (pos[i>>1]>>1)|((1<<tt)*(i&1));
}
inline void trans(int *a, int t=1) {
for (int i=0;i<L;i++) if (pos[i] < i) swap(a[pos[i]], a[i]);
for (int l=2;l<=L;l<<=1) {
int wn = Pow(G, MOD/l); if (t == -1) wn = Pow(wn, MOD-2);
for (int i=0;i<L;i+=l) {
for (int j=0,w=1;j<l/2;j++,w=(LL)w*wn%MOD) {
int tmp = (LL)w * a[i+l/2+j] % MOD;
a[i+l/2+j] = (a[i+j] - tmp) % MOD;
a[i+j] = (a[i+j] + tmp) % MOD;
}
}
}
if (t == -1) for (int i=0,rev=Pow(L,MOD-2);i<L;i++) a[i] = (LL)a[i] * rev % MOD;
for (int i=0;i<L;i++) a[i] = a[i]<0? a[i] + MOD: a[i];
}
private:
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;
}
}NTT;

int main() {
for (int i=1;i<=n;i++) a1[i] = o1[i] = Read();
for (int i=1;i<=m;i++) a2[i] = o2[i] = Read();

//find out legal positions
for (int i=1;i<=m;i++) a1[n+i+1] = a2[i];
for (int i=1;i<=n+m+1;i++) a1[i] >>= 1, a1[i]++;
a1[n+1] = 0; SA.build();
SA.solve();

//calculate the cost
NTT.init();
memset(a1,0,sizeof(a1)); memset(a2,0,sizeof(a2));
for (int i=0;i<n;i++) a1[i] = o1[i+1] & 1;
for (int i=0;i<m;i++) a2[i] = (o2[m-i] & 1) ^ 1;
NTT.trans(a1); NTT.trans(a2);
for (int i=0;i<L;i++) a1[i] = (LL)a1[i] * a2[i] % MOD;
NTT.trans(a1, -1);
for (int i=1;i<=n;i++) ans[i] = a1[i+m-2];
memset(a1,0,sizeof(a1)); memset(a2,0,sizeof(a2));
for (int i=0;i<n;i++) a1[i] = (o1[i+1] & 1) ^ 1;
for (int i=0;i<m;i++) a2[i] = o2[m-i] & 1;
NTT.trans(a1); NTT.trans(a2);
for (int i=0;i<L;i++) a1[i] = (LL)a1[i] * a2[i] % MOD;
NTT.trans(a1, -1);
for (int i=1;i<=n;i++) ans[i] += a1[i+m-2];

int pos=-1, cost=INF;
for (int i=1;i<=n;i++) if (leg[i] && ans[i] < cost) cost = ans[i], pos = i;
if (!~pos) puts("No");
else printf("Yes\n%d %d\n",cost,pos);
return 0;
}


## 【日常小测】Hope

### 解题报告

—————————— UPD 2017.3.17 ——————————
Claris说这题在OEIS上能找到$O(n)$的递推式 QwQ
Claris太强啦！ _(:з」∠)_

## 【日常小测】生日礼物

### Code

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

const int N = 600009;
const int MOD = 786433;
const int RT = 13;

int g[N],f[N],POW[N],REV[N],pos[N];
int n1,n2,m,q,vis[N],a[N],b[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 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 int C(int a, int b) {
if (a > b) return 0;
return ((LL)POW[b] * REV[a] % MOD) * REV[b-a] % MOD;
}

inline void prework() {
for (int i=2;i<N;i++) {
for (int j=i*2;j<N;j+=i) {
vis[j] = 1;
}
} vis[1] = 1;
POW[0] = REV[0] = 1;
for (int i=1;i<N;i++) POW[i] = (LL)POW[i-1] * i % MOD;
REV[N-1] = Pow(POW[N-1], MOD-2);
for (int i=N-2;i;i--) REV[i] = REV[i+1] * (i+1ll) % MOD;
}

inline void ntt(int *a, int len, int rev = 0) {
for (int i=0;i<len;i++) if (pos[i]<i) swap(a[i], a[pos[i]]);
for (int l=2;l<=len;l<<=1) {
int wn = Pow(RT, MOD / l);
if (rev) wn = Pow(wn, MOD-2);
for (int i=0,w=1,tmp;i<len;i+=l,w=1) {
for (int j=0;j<(l>>1);j++,w=(LL)w*wn%MOD) {
tmp = (LL)w * a[i+j+(l>>1)] % MOD;
a[i+j+(l>>1)] = (a[i+j] - tmp) % MOD;
a[i+j] = (a[i+j] + tmp) % MOD;
}
}
}
if (rev) for (int i=1,Rev=Pow(len,MOD-2);i<=len;i++)
a[i] = ((LL)a[i] * Rev % MOD + MOD) % MOD;
}

inline void solve(int l, int *a, int *b) {
int t = -1, len = 1;
while (len < (l+1)) len <<= 1, t++;
for (int i=0;i<len;i++) {
pos[i] = pos[i>>1]>>1;
if (i&1) pos[i] |= 1<<t;
}
ntt(a, len); ntt(b, len);
for (int i=0;i<len;i++) a[i] = (LL)a[i] * b[i] % MOD;
ntt(a, len, 1);
}

inline void update() {
memset(f,0,sizeof(f)); memset(g,0,sizeof(g));
memset(a,0,sizeof(a)); memset(b,0,sizeof(b));
for (int i=1;i<=n2;i++)
g[i] = (LL)C(i-1, n2-1) * C(i, m) % MOD;
for (int i=0;i<=n1;i++) {
a[i] = (i&1)? MOD-REV[i]: REV[i];
b[i] = (LL)Pow(i, n1) * REV[i] % MOD;
}
solve(n1 << 1, a, b);
for (int i=1;i<=n1;i++) {
if (vis[i]) f[i] = i==n1? 1: C(i-1, n1);
else f[i] = a[i];
}
}

int main() {
prework();
solve(n1 + n2, f, g);
}
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() {