2020-2021:teams:legal_string:jxm2001:contest:牛客练习赛68
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:legal_string:jxm2001:contest:牛客练习赛68 [2020/08/29 10:44] jxm2001 创建 |
2020-2021:teams:legal_string:jxm2001:contest:牛客练习赛68 [2020/08/29 12:37] (当前版本) jxm2001 |
||
|---|---|---|---|
| 行 76: | 行 76: | ||
| </hidden> | </hidden> | ||
| + | ==== 题解 2 ==== | ||
| + | |||
| + | 循环矩阵快速幂，时间复杂度 $O(n^2\log k)$。 | ||
| + | |||
| + | $$ | ||
| + | \begin{pmatrix} | ||
| + | \text{ans}_0\\ | ||
| + | \text{ans}_1\\ | ||
| + | \vdots\\ | ||
| + | \text{ans}_{n-1} | ||
| + | \end{pmatrix}= | ||
| + | \begin{pmatrix} | ||
| + | c & b & 0 & \cdots & a \\ | ||
| + | a & c & b & \cdots & 0 \\ | ||
| + | \vdots & \vdots & \vdots & \ddots & \vdots \\ | ||
| + | b & 0 & 0 & \cdots & c | ||
| + | \end{pmatrix} | ||
| + | \begin{pmatrix} | ||
| + | x_0\\ | ||
| + | x_1\\ | ||
| + | \vdots\\ | ||
| + | x_{n-1} | ||
| + | \end{pmatrix}$$ | ||
| + | |||
| + | <hidden 查看代码> | ||
| + | <code cpp> | ||
| + | const int MAXN=505,mod=998244353; | ||
| + | int quick_pow(int a,LL b){ | ||
| + | int ans=1; | ||
| + | while(b){ | ||
| + | if(b&1)ans=1LL*ans*a%mod; | ||
| + | a=1LL*a*a%mod; | ||
| + | b>>=1; | ||
| + | } | ||
| + | return ans; | ||
| + | } | ||
| + | int n,x[MAXN],y[MAXN],z[MAXN],ans[MAXN],a,b,c,pos; | ||
| + | void Mul(int *a,int *b){ | ||
| + | static int temp[MAXN]; | ||
| + | mem(temp,0); | ||
| + | _for(i,0,n){ | ||
| + | _for(j,0,n) | ||
| + | temp[i]=(temp[i]+1LL*a[j]*b[(i-j+n)%n])%mod; | ||
| + | } | ||
| + | _for(i,0,n)a[i]=temp[i]; | ||
| + | } | ||
| + | int main() | ||
| + | { | ||
| + | n=read_int(); | ||
| + | LL k=read_LL(),t=k; | ||
| + | a=read_int(),b=read_int(),c=read_int(); | ||
| + | y[0]=1,z[0]=c,z[n-1]=a,z[1]=b; | ||
| + | _for(i,0,n)x[i]=read_int(); | ||
| + | while(t){ | ||
| + | if(t&1)Mul(y,z); | ||
| + | Mul(z,z); | ||
| + | t>>=1; | ||
| + | } | ||
| + | _for(i,0,n){ | ||
| + | _for(j,0,n) | ||
| + | ans[i]=(ans[i]+1LL*x[j]*y[(j-i+n)%n])%mod; | ||
| + | } | ||
| + | int inv=quick_pow(quick_pow(a+b+c,mod-2),k); | ||
| + | _for(i,0,n)space(1LL*ans[i]*inv%mod); | ||
| + | return 0; | ||
| + | } | ||
| + | </code> | ||
| + | </hidden> | ||
| + | |||
| + | ==== 题解 3 ==== | ||
| + | |||
| + | 设 $F=\{x_0,x_1\cdots x_{n-1}\},G=\{c,a,0\cdots 0,b\}$。 | ||
| + | |||
| + | 于是所求答案为 $FG^k$ 的长度为 $n$ 的循环卷积。 | ||
| + | |||
| + | 直接暴力卷积时间复杂度 $O(n\log n\log k)$，如果套用 $\text{Bluestein's Algotithm}$ 时间复杂度 $O(n(\log n+\log k))$。 | ||
2020-2021/teams/legal_string/jxm2001/contest/牛客练习赛68.1598669085.txt.gz · 最后更改: 2020/08/29 10:44 由 jxm2001
