CVBB ACM Team

到此差别页面的链接

--- 2020-2021:teams:legal_string:jxm2001:多项式_2 [2020/08/07 11:22]
jxm2001
+++ 2020-2021:teams:legal_string:jxm2001:多项式_2 [2021/05/02 17:40] (当前版本)
jxm2001 [理论基础]
@@ 行 39: / 行 39: @@
 考虑如何实现 $O(n\log n)$ 时间根据多项式系数点值法得到多项式系数表示法。
-记 $y_i=f(\omega_n^i)$。假设 $f(x)$ 系数表示法为 ${a_0,a_1\cdots a_{n-1}}$，点值表示法为 $\{(\omega_n^0,y_0),(\omega_n^1,y_1)\cdots (\omega_n^{n-1},y_{n-1})\}$。
+记 $y_i=f(\omega_n^i)$。
+假设 $f(x)$ 系数表示法为 ${a_0,a_1\cdots a_{n-1}}$，点值表示法为 $\{(\omega_n^0,y_0),(\omega_n^1,y_1)\cdots (\omega_n^{n-1},y_{n-1})\}$。
 构造多项式 $A(x)=\sum_{i=0}^{n-1}y_ix^i$，将 $x=\omega_n^{-k}(k=0,1\cdots n-1)$ 代入，有
@@ 行 348: / 行 350: @@
 === 习题二 ===
+[[https://www.luogu.com.cn/problem/P3338|洛谷p3338]]
+== 题意 ==
+给定 $a_0,a_1\cdots a_{n-1}$，求
+$$E_i=\sum_{j=0}^{i-1} \frac {a_j}{(i-j)^2}-\sum_{j=i+1}^{n-1} \frac {a_j}{(i-j)^2}(i=0,1\cdots n-1)$$
+== 题解 ==
+构造
+$$b_i=
+\begin{cases}
+\cfrac 1{i^2}, & n\gt 0\\
+, & n=0\\
+-\cfrac 1{i^2}, & n\lt 0\\
+\end{cases}
+$$
+于是有 $E_i=\sum_{j=0}^{n-1} a_jb_{i-j}$。同时为防止访问负数下标，令 $b_i$ 偏移 $n-1$ 位。
+最后套用 $\text{FFT}$ 计算即可，时间复杂度 $O(n\log n)$。
+<hidden 查看代码>
+<code cpp>
+const int MAXN=1e5+5;
+const double pi=acos(-1.0);
+struct complex{
+	double x,y;
+	complex(double x=0.0,double y=0.0):x(x),y(y){}
+	complex operator + (const complex &b){
+		return complex(x+b.x,y+b.y);
+	}
+	complex operator - (const complex &b){
+		return complex(x-b.x,y-b.y);
+	}
+	complex operator * (const complex &b){
+		return complex(x*b.x-y*b.y,x*b.y+y*b.x);
+	}
+};
+int rev[MAXN<<3];
+int build(int k){
+	int n,pos=0;
+	while((1<<pos)<=k)pos++;
+	n=1<<pos;
+	_for(i,0,n)rev[i]=(rev[i>>1]>>1)|((i&1)<<(pos-1));
+	return n;
+}
+void FFT(complex *f,int n,int type){
+	_for(i,0,n)if(i<rev[i])
+	swap(f[i],f[rev[i]]);
+	complex t1,t2;
+	for(int i=1;i<n;i<<=1){
+		complex w(cos(pi/i),type*sin(pi/i));
+		for(int j=0;j<n;j+=(i<<1)){
+			complex cur(1.0,0.0);
+			_for(k,j,j+i){
+				t1=f[k],t2=cur*f[k+i];
+				f[k]=t1+t2,f[k+i]=t1-t2;
+				cur=cur*w;
+			}
+		}
+	}
+	if(type==-1)_for(i,0,n)
+	f[i].x/=n;
+}
+complex f[MAXN<<3],g[MAXN<<3];
+int main()
+{
+	int n=read_int();
+	_for(i,0,n)
+	scanf("%lf",&f[i].x);
+	_for(i,1,n)
+	g[n-1+i].x=1.0/i/i,g[n-1-i].x=-1.0/i/i;
+	g[n-1].x=0;
+	int t=build(3*n);
+	FFT(f,t,1);FFT(g,t,1);
+	_for(i,0,t)
+	f[i]=f[i]*g[i];
+	FFT(f,t,-1);
+	_for(i,0,n)
+	printf("%.3lf\n",f[n-1+i].x);
+	return 0;
+}
+</code>
+</hidden>
+=== 习题三 ===
 [[https://www.luogu.com.cn/problem/P3723|洛谷p3723]]
@@ 行 440: / 行 532: @@
 </hidden>
-=== 习题三 ===
+=== 习题四 ===
 [[http://codeforces.com/gym/101234/problem/D|2020-2021 BUAA ICPC Team Supplementary Training 02 D]]
@@ 行 653: / 行 745: @@
   - 一个正整数 $n$ 具有原根的充要条件为 $n=2,4,p^\alpha,2p^\alpha$，其中 $p$ 为素数
   - 如果 $n$ 具有原根，则 $n$ 具有 $\varphi\left(\varphi(n)\right)$ 个原根
-  - 如果 $g$ 为 $n$ 的原根，则 $1,g^1,g^2\cdots g^{\varphi(n)}$ 构成 $n$ 的最简剩余系
+  - 如果 $g$ 为 $n$ 的原根，则 $1,g^1,g^2\cdots g^{\varphi(n)-1}$ 构成 $n$ 的最简剩余系
   - 设 $\varphi(n)=p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_k^{\alpha_k}$，且 $n\nmid a^{\frac {\varphi(n)}{p_i}}-1(i=1,2\cdots k)$，则 $a$ 为 $n$ 的原根
@@ 行 702: / 行 794: @@
 }
 </code>
+====  算法练习 ====
+[[https://www.luogu.com.cn/problem/P3321|洛谷p3321]]
+=== 题意 ===
+给定一个集合 $S$，问从集合 $S$ 中依次选出 $n$ 个数乘积模 $p$ 意义下恰好为 $x$ 的方案数。
+数据保证 $p\le 8000,n\le 10^9,1\le x\lt p$，且 $p$ 为素数，最后答案对 $1004535809$ 取模。
+=== 题解 ===
+先考虑将乘法转化为加法。素数 $p$ 一定有原根 $g$，考虑将 $S$ 中的每个数表示为 $p$ 的幂次，且 $x=g^y$。
+于是合法方案转化为幂次和模 $p-1$ 意义下恰好为 $y$ 的方案。
+令 $f_{i,j}$ 表示依次选择 $i$ 个数幂次和恰好为 $j$ 的方案，于是有递推式 $f_{i,j}=\sum_{k=0}^j f_{i-1,j-k}f_{1,k}$。
+考虑 $\text{NTT}$ 加速卷积过程。由于只关注模 $p-1$ 意义的和，于是可以将每次卷积后大于 $p-1$ 的项转移到取模后的结果中。
+于是得到一个暴力递推算法，时间复杂度为 $O(np\log p)$。
+考虑快速幂优化递推过程，于是时间复杂度降为 $O(p\log p\log n)$。
+<hidden 查看代码>
+<code cpp>
+const int MAXP=8005,Mod=1004535809,G=3,Inv_G=334845270;
+int quick_pow(int a,int b,int mod){
+	int ans=1;
+	while(b){
+		if(b&1)
+		ans=1LL*ans*a%mod;
+		a=1LL*a*a%mod;
+		b>>=1;
+	}
+	return ans;
+}
+int rev[MAXP<<2];
+int build(int k){
+	int n,pos=0;
+	while((1<<pos)<=k)pos++;
+	n=1<<pos;
+	_for(i,0,n)rev[i]=(rev[i>>1]>>1)|((i&1)<<(pos-1));
+	return n;
+}
+void NTT(int *f,int n,int type){
+	_for(i,0,n)if(i<rev[i])
+	swap(f[i],f[rev[i]]);
+	int t1,t2;
+	for(int i=1;i<n;i<<=1){
+		int w=quick_pow(type==1?G:Inv_G,(Mod-1)/(i<<1),Mod);
+		for(int j=0;j<n;j+=(i<<1)){
+			int cur=1;
+			_for(k,j,j+i){
+				t1=f[k],t2=1LL*cur*f[k+i]%Mod;
+				f[k]=(t1+t2)%Mod,f[k+i]=(t1-t2)%Mod;
+				cur=1LL*cur*w%Mod;
+			}
+		}
+	}
+	if(type==-1){
+		int div=quick_pow(n,Mod-2,Mod);
+		_for(i,0,n)
+		f[i]=(1LL*f[i]*div%Mod+Mod)%Mod;
+	}
+}
+int lg[MAXP];
+vector<int> ps;
+bool check(int x,int p){
+	_for(i,0,ps.size()){
+		if(quick_pow(x,(p-1)/ps[i],p)==1)
+		return false;
+	}
+	return true;
+}
+void get_log(int p){
+	int temp=p-1,g;
+	for(int i=2;i*i<=temp;i++){
+		if(temp%i==0){
+			ps.push_back(i);
+			while(temp%i==0)temp/=i;
+		}
+	}
+	if(temp!=1)ps.push_back(temp);
+	_for(i,2,p){
+		if(check(i,p)){
+			g=i;
+			break;
+		}
+	}
+	for(int i=0,j=1;i<p-1;i++,j=j*g%p)
+	lg[j]=i;
+}
+int temp[MAXP<<2];
+void quick_pow(int *f,int n,int k,int mod){
+	memcpy(temp,f,sizeof(temp));
+	f[0]=1;
+	_for(i,1,n)f[i]=0;
+	while(k){
+		NTT(temp,n,1);
+		if(k&1){
+			NTT(f,n,1);
+			_for(i,0,n)
+			f[i]=1LL*f[i]*temp[i]%Mod;
+			NTT(f,n,-1);
+		}
+		_for(i,0,n)
+		temp[i]=1LL*temp[i]*temp[i]%Mod;
+		NTT(temp,n,-1);
+		_for(i,mod,n){
+			f[i%mod]=(f[i%mod]+f[i])%Mod;
+			temp[i%mod]=(temp[i%mod]+temp[i])%Mod;
+			f[i]=temp[i]=0;
+		}
+		k>>=1;
+	}
+}
+int cnt[MAXP<<2];
+int main()
+{
+	int n=read_int(),p=read_int(),x=read_int(),s=read_int();
+	get_log(p);
+	while(s--){
+		int v=read_int();
+		if(!v)continue;
+		cnt[lg[v]]++;
+	}
+	int m=build(p<<1);
+	quick_pow(cnt,m,n,p-1);
+	enter(cnt[lg[x]]);
+	return 0;
+}
+</code>
+</hidden>
 ===== MTT =====
@@ 行 1011: / 行 1238: @@
 ==== 算法练习 ====
+=== 习题一 ===
 [[https://ac.nowcoder.com/acm/contest/5667/E|牛客暑期多校(第二场) E 题]]
-=== 题意 ===
+== 题意 ==
 给定 $n$ 个数 $a_1,a_2\cdots a_n(0\le a_i\lt 2^{18})$。
@@ 行 1020: / 行 1249: @@
 要求输出 $n$ 个数，第 $i$ 个数表示取 $i$ 个数(可以重复取)可以得到的最大值。
-=== 题解 ===
+== 题解 ==
 记 $f_{i,j}$ 表示选取 $i$ 个数能否取到数值 $j$，$ans_i$ 表示选取 $i$ 个数能取到的最大值，$\omega=18$。
@@ 行 1082: / 行 1311: @@
 	_rep(i,1,n)
 	space(ans[i]);
+	return 0;
+}
+</code>
+</hidden>
+=== 习题二 ===
+[[https://www.luogu.com.cn/problem/P6097|洛谷p6097]]
+== 题意 ==
+子集卷积模板题。
+给定两个序列 $a_0,a_1\cdots a_{2^n-1}$ 和 $b_0,b_1\cdots b_{2^n-1}$。
+求 $c_0,c_1\cdots c_{2^n-1}$，其中
+$$c_k=\sum_{i\And j=0,i|j=k}a_ib_j$$
+== 题解 ==
+对 $i|j=k,i\And j\neq 0$ 有 $|i|+|j|\gt |k|$。于是 $i\And j=0,i|j=k$ 等价于 $i|j=k,|i|+|j|=|k|$。
+$$
+a_{i,j} =
+\begin{cases}
+a_j, & i=|j|  \\
+, & i\neq |j|
+\end{cases}
+$$
+考虑将新得到的序列 $\{a_i\},\{b_j\}$ 间两两卷积，最终答案即为 $c_{|k|,k}$。
+时间复杂度 $O\left(n^22^n\right)$。
+<hidden 查看代码>
+<code cpp>
+const int MAXN=21,MAXM=1<<20,Mod=1e9+9;
+int a[MAXN][MAXM],b[MAXN][MAXM],c[MAXN][MAXM],cnt[MAXM];
+void FWT(int *f,int n,int type){
+	for(int i=1;i<n;i<<=1)
+	for(int j=0;j<n;j+=(i<<1))
+	_for(k,j,j+i)
+	f[k+i]=(f[k+i]+type*f[k])%Mod;
+}
+int main()
+{
+	int n=read_int(),m=1<<n;
+	_for(i,1,m)cnt[i]=cnt[i-(i&(-i))]+1;
+	_for(i,0,m)a[cnt[i]][i]=read_int();
+	_for(i,0,m)b[cnt[i]][i]=read_int();
+	_rep(i,0,n)FWT(a[i],m,1),FWT(b[i],m,1);
+	_rep(i,0,n)_rep(j,0,i)_for(k,0,m)
+	c[i][k]=(c[i][k]+1LL*a[j][k]*b[i-j][k])%Mod;
+	_rep(i,0,n)FWT(c[i],m,-1);
+	_for(i,0,m)space((c[cnt[i]][i]+Mod)%Mod);
 	return 0;
 }
 </code>
 </hidden>

CVBB ACM Team

用户工具

站点工具

页面工具