【日常小测】图片加密

题目大意

给定两个数字串$A,B$,长度分别为$n,m(m \le n \le 250000)$
串中的元素为$<512$的自然数,你可以花费一个单位的代价改变一个元素在二进制下的最低位
询问能否通过修改操作使得$B$在$A$中出现
如果可以,请输出最小的花费和在花费最小的前提下最左边的匹配位置

解题报告

我们发现高位不可改,于是我们用$KMP$统计一下高位的合法位置
至于低位,我们可以拆成两次$FFT$
于是搞一搞就可以了

至于为什么我写的是$SA$?
因为考场上忘掉$KMP$怎么写了 QwQ

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]; 
  
inline int read() {
    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 Read() {
    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() {
    n = read(); m = read();
    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];
     
    //output the answer
    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

题目大意

给定排列的长度$n(n\le10^5)$和常数$k(k\le10^5)$
对于单个排列$A$中的每$i$位:我们连一条从$i$出发,到其右边第一个比它大的位,如果没有就不连
定义$A$的花费为 $\sum$其中每一个连通块的大小$^k$
询问所有长度为$n$的排列的花费和$(\bmod 998244353)$

解题报告

设$f_i$为排列长度为$i$的答案,假设我们已经求出了$f_{i-1}$
我们考虑枚举$i$放在哪里,那么$i$之前的数全部连向$i$,之后的数是递归一个子问题
于是我们可以写出暴力的$DP$:${f_i} = \sum\limits_{j = 1}^i {{j^k}(j – 1)!C_{i – 1}^{j – 1}{f_{i – j}}} $
我们化一化式子可以得到$\frac{f_i}{(i-1)!}=\sum\limits_{j=1}^{i}{j^k \cdot \frac{f_{i-j}}{(i-j)!}}$
这显然是一个卷积的形式,于是可以用$NTT$优化

另外,对于$f_i$来讲,$f_{1 \sim i-1}$都会对它有贡献
那么这有是一个典型的$CDQ$分治的模型,于是我们还需要套上一个$CDQ$分治

在另外的话,我们回顾一下推出暴力$DP$的过程
不难发现我们是以最大值的插入作为突破口
那么这种题目与最大值相关的问题,这应该算是套路之一吧!
例如:HDU 5575

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

【日常小测】生日礼物

相关链接

题目传送门:http://oi.cyo.ng/wp-content/uploads/2017/03/4237864728368.png
斯特林数相关:https://en.wikipedia.org/wiki/Stirling_number

解题报告

答案显然就是两个序列卷积起来
而其中一个序列就是一个组合数一样的东西
另一个序列则需要处理出第二类斯特林数
众所周知,预处理特殊的第二类斯特林数可以用$NTT$优化
于是就搞两次$NTT$就可以了,时间复杂度$O(n \log n)$

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];
 
inline int read() {
    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();
    for (int T=read();T;T--) {
        n1 = read(); n2 = read(); 
        m = read(); update();
        solve(n1 + n2, f, g);
        for (int q=read();q;q--) 
            printf("%d\n",(f[read()]+MOD)%MOD);
    }
    return 0;
}

【BZOJ 3992】[SDOI2015] 序列统计

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3992
Latex题面:http://paste.ubuntu.com/23997878/
数据生成器:http://paste.ubuntu.com/24006205/
神犇题解:http://www.cnblogs.com/gromah/p/4431016.html
NTT相关:http://blog.miskcoo.com/2015/04/polynomial-multiplication-and-fast-fourier-transform#i-13

解题报告

这题$O(m^3logn)$的基于矩阵快速幂的算法大家都会吧?
然而只能通过 $60\% $ 的数据 QwQ

然后就需要一点黑科技了
考虑模数这么奇怪,于是可能是用元根来搞一搞
然后我们发现,我们可以用元根的幂次来表示 $0 \sim m – 1$ 的每一个数
于是我们就可以把乘法换成幂次的加法,于是就可以搞NTT了!
于是用NTT来搞生成函数,复杂度:$O(nmlogm)$
然后再套上一开始讲的快速幂,那么就是$O(mlogmlogn)$的复杂度啦!

Code

话说这似乎是第一次撸$NTT$呢!
还有一点小激动啊!
不过这一份代码封装太多了,好慢啊 QwQ

#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];

inline int read() {
	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() {
	l = read(); m = read();
	x = read() % m; n = read();
	int PRT = Get_Primitive_Root(m);
	for (int cur=1,i=0;i<m-1;i++,cur=cur*PRT%m) pos[cur] = i;
	for (int i=0,t;i<n;i++) t=read(), t?arr.a[pos[t%m]]++:0;
	int len = 1; while (len < m) len <<= 1;
	arr.len = len << 1; arr.pow(l); 
	printf("%d\n",(arr.a[pos[x]]+MOD)%MOD);
	return 0;
}