2020-2021:teams:legal_string:jxm2001:多项式_2
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:legal_string:jxm2001:多项式_2 [2020/08/07 16:15] jxm2001 |
2020-2021:teams:legal_string:jxm2001:多项式_2 [2021/05/02 17:40] (当前版本) jxm2001 [理论基础] |
||
|---|---|---|---|
| 行 745: | 行 745: | ||
| - 一个正整数 $n$ 具有原根的充要条件为 $n=2,4,p^\alpha,2p^\alpha$，其中 $p$ 为素数 | - 一个正整数 $n$ 具有原根的充要条件为 $n=2,4,p^\alpha,2p^\alpha$，其中 $p$ 为素数 | ||
| - 如果 $n$ 具有原根，则 $n$ 具有 $\varphi\left(\varphi(n)\right)$ 个原根 | - 如果 $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$ 的原根 | - 设 $\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$ 的原根 | ||
| 行 1238: | 行 1238: | ||
| ==== 算法练习 ==== | ==== 算法练习 ==== | ||
| + | |||
| + | === 习题一 === | ||
| [[https://ac.nowcoder.com/acm/contest/5667/E|牛客暑期多校(第二场) E 题]] | [[https://ac.nowcoder.com/acm/contest/5667/E|牛客暑期多校(第二场) E 题]] | ||
| - | === 题意 === | + | == 题意 == |
| 给定 $n$ 个数 $a_1,a_2\cdots a_n(0\le a_i\lt 2^{18})$。 | 给定 $n$ 个数 $a_1,a_2\cdots a_n(0\le a_i\lt 2^{18})$。 | ||
| 行 1247: | 行 1249: | ||
| 要求输出 $n$ 个数，第 $i$ 个数表示取 $i$ 个数(可以重复取)可以得到的最大值。 | 要求输出 $n$ 个数，第 $i$ 个数表示取 $i$ 个数(可以重复取)可以得到的最大值。 | ||
| - | === 题解 === | + | == 题解 == |
| 记 $f_{i,j}$ 表示选取 $i$ 个数能否取到数值 $j$，$ans_i$ 表示选取 $i$ 个数能取到的最大值，$\omega=18$。 | 记 $f_{i,j}$ 表示选取 $i$ 个数能否取到数值 $j$，$ans_i$ 表示选取 $i$ 个数能取到的最大值，$\omega=18$。 | ||
| 行 1309: | 行 1311: | ||
| _rep(i,1,n) | _rep(i,1,n) | ||
| space(ans[i]); | 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| \\ | ||
| + | 0, & 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; | return 0; | ||
| } | } | ||
| </code> | </code> | ||
| </hidden> | </hidden> | ||
2020-2021/teams/legal_string/jxm2001/多项式_2.1596788131.txt.gz · 最后更改: 2020/08/07 16:15 由 jxm2001
