2020-2021:teams:legal_string:jxm2001:lgv引理
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:legal_string:jxm2001:lgv引理 [2021/08/15 14:41] jxm2001 |
2020-2021:teams:legal_string:jxm2001:lgv引理 [2021/08/15 16:02] (当前版本) jxm2001 [题解] |
||
|---|---|---|---|
| 行 43: | 行 43: | ||
| ===== 算法模板 ===== | ===== 算法模板 ===== | ||
| + | |||
| + | [[https://acm.hdu.edu.cn/showproblem.php?pid=5852|HDU5852]] | ||
| 给定一个二维平面，求满足如下条件的 $k$ 元路径组个数： | 给定一个二维平面，求满足如下条件的 $k$ 元路径组个数： | ||
| 行 120: | 行 122: | ||
| ===== 算法例题 ===== | ===== 算法例题 ===== | ||
| + | |||
| + | [[https://ac.nowcoder.com/acm/contest/11260/C|2021牛客暑期多校训练营9 C]] | ||
| ==== 题意 ==== | ==== 题意 ==== | ||
| 行 156: | 行 160: | ||
| $$ | $$ | ||
| M= | M= | ||
| + | \prod_{i=1}^n \frac 1{i!} | ||
| \begin{bmatrix} | \begin{bmatrix} | ||
| x_1&x_1(x_1+1)&\cdots&\prod_{i=0}^{n-1}(x_1+i)\\ | x_1&x_1(x_1+1)&\cdots&\prod_{i=0}^{n-1}(x_1+i)\\ | ||
| 行 168: | 行 173: | ||
| $$ | $$ | ||
| M= | M= | ||
| + | \prod_{i=1}^n \frac 1{i!} | ||
| \begin{bmatrix} | \begin{bmatrix} | ||
| x_1&x_1^2&\cdots&x_1^n\\ | x_1&x_1^2&\cdots&x_1^n\\ | ||
| 行 176: | 行 182: | ||
| $$ | $$ | ||
| + | 每行都提出一个 $x_i$，就可以得到一个范德蒙行列式，于是有 | ||
| + | $$ | ||
| + | \det M=\prod_{i=1}^n \frac {a_i+1}{i!}\prod_{1\le i\lt j\le n}(a_j-a_i) | ||
| + | $$ | ||
| + | |||
| + | |||
| + | 考虑 $\text{NTT}$ 计算每个值在 $\prod_{1\le i\lt j\le n}(a_j-a_i)$ 出现的次数。 | ||
| + | |||
| + | 具体的，可以设 $f(x)=\sum_{i=1}^n x^{a_i},g(x)=\sum_{i=1}^n x^{-a_i}$，则每个值 $k$ 出现次数就是 $[x^k]f(x)g(x)$。 | ||
| + | |||
| + | 注意还有 $i\lt j$ 的限制，根据对称性，考只考虑 $k\gt 0$ 的部分贡献然后做快速幂即可，时间复杂度 $O(V\log V)$。 | ||
| + | |||
| + | <hidden 查看代码> | ||
| + | <code cpp> | ||
| + | const int mod=998244353,MAXN=1e6+5; | ||
| + | int quick_pow(int n,int k){ | ||
| + | int ans=1; | ||
| + | while(k){ | ||
| + | if(k&1)ans=1LL*ans*n%mod; | ||
| + | n=1LL*n*n%mod; | ||
| + | k>>=1; | ||
| + | } | ||
| + | return ans; | ||
| + | } | ||
| + | namespace Poly{ | ||
| + | const int Mod=998244353,G=3; | ||
| + | int rev[MAXN<<2],Wn[30][2]; | ||
| + | void init(){ | ||
| + | int m=Mod-1,lg2=0; | ||
| + | while(m%2==0)m>>=1,lg2++; | ||
| + | Wn[lg2][1]=quick_pow(G,m); | ||
| + | Wn[lg2][0]=quick_pow(Wn[lg2][1],Mod-2); | ||
| + | while(lg2){ | ||
| + | m<<=1,lg2--; | ||
| + | Wn[lg2][0]=1LL*Wn[lg2+1][0]*Wn[lg2+1][0]%Mod; | ||
| + | Wn[lg2][1]=1LL*Wn[lg2+1][1]*Wn[lg2+1][1]%Mod; | ||
| + | } | ||
| + | } | ||
| + | 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,bool type){ | ||
| + | _for(i,0,n)if(i<rev[i]) | ||
| + | swap(f[i],f[rev[i]]); | ||
| + | int t1,t2; | ||
| + | for(int i=1,lg2=0;i<n;i<<=1,lg2++){ | ||
| + | int w=Wn[lg2+1][type]; | ||
| + | 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){ | ||
| + | int div=quick_pow(n,Mod-2); | ||
| + | _for(i,0,n)f[i]=(1LL*f[i]*div%Mod+Mod)%Mod; | ||
| + | } | ||
| + | } | ||
| + | void mul(int *f,int _n,int *g,int _m){ | ||
| + | int n=build(_n+_m-2); | ||
| + | _for(i,_n,n)f[i]=0;_for(i,_m,n)g[i]=0; | ||
| + | NTT(f,n,1);NTT(g,n,1); | ||
| + | _for(i,0,n)f[i]=1LL*f[i]*g[i]%Mod; | ||
| + | NTT(f,n,0); | ||
| + | } | ||
| + | } | ||
| + | int frac[MAXN],invf[MAXN],a[MAXN<<2],b[MAXN<<2]; | ||
| + | int main(){ | ||
| + | frac[0]=1; | ||
| + | _for(i,1,MAXN) | ||
| + | frac[i]=1LL*frac[i-1]*i%mod; | ||
| + | invf[MAXN-1]=quick_pow(frac[MAXN-1],mod-2); | ||
| + | for(int i=MAXN-1;i;i--) | ||
| + | invf[i-1]=1LL*invf[i]*i%mod; | ||
| + | int n=read_int(),base=1e6,ans=1; | ||
| + | _rep(i,1,n){ | ||
| + | int t=read_int(); | ||
| + | ans=1LL*ans*(t+1)%mod*invf[i]%mod; | ||
| + | a[t]++; | ||
| + | b[base-t]++; | ||
| + | } | ||
| + | Poly::init(); | ||
| + | Poly::mul(a,base+1,b,base+1); | ||
| + | _rep(i,base+1,base*2) | ||
| + | ans=1LL*ans*quick_pow(i-base,a[i])%mod; | ||
| + | enter((ans+mod)%mod); | ||
| + | return 0; | ||
| + | } | ||
| + | </code> | ||
| + | </hidden> | ||
2020-2021/teams/legal_string/jxm2001/lgv引理.1629009707.txt.gz · 最后更改: 2021/08/15 14:41 由 jxm2001
