[atARC134F]Flipping Coins

对于$i\ge P_{i}$的位置,由于$P_{i}$此时正面向下,因此操作$i$并不会改变$k$,不妨撤销此类操作

另外,对于满足$P_{j}=i$的操作$j$,若$j<i$则已经操作$,j>i$则也被撤销,因此不影响

综上,仅对$i<P_{i}$建边$(i,P_{i})$,那么$k$即为其中长度为奇数的极长链个数

 

对于排列$\{P\}$,按照如下方式构造排列$\{Q\}$:

对所有$i$建边$(i,P_{i})$,假设图中有$m$个环且第$i$个环上的点(沿着边)依次构成序列$\{h_{i}\}$

不妨强制$h_{i,1}\le h_{i,j}$且$h_{1,1}>h_{2,1}>...>h_{m,1}$,则$\{Q\}=\sum_{i=1}^{m}\{h_{i}\}$(指拼接)

从排列$\{Q\}$的角度考虑此问题,那么$k$即为其中长度为奇数的极长连续上升子序列个数

另一方面,不难证明排列$\{P\},\{Q\}$一一对应,因此也即统计所有排列的上述信息

 

进一步的,将排列中的极长连续上升子序列从前往后标记为$AB$,剩下的位置标记为$C$

确定上述标记后,$k$即为其中$C$的个数,同时限制即$A$小于其下一个数且$C$在末尾或大于其下一个数

(注意并不关心偶数长度的序列,因此不需要考虑$BA$和$BC$之间的大小关系)

根据限制,在所有$B$之后断开,断开后每一段序列限制是独立的,且总是形如若干个$C$(允许为0)$+(AB)$

另外,如果没有$AB$显然必然是最后一段,这可以在最后处理(即以下强制存在$AB$)

在此基础上,进行dp计算,令$f_{i}$表示前$i$个位置的答案,转移即$f_{i}=\sum_{j=2}^{i}{i\choose j}(j-1)W^{j-2}f_{i-j}$

结合最后一段$C$,最终答案即$\sum_{i=0}^{n}{n\choose i}W^{i}f_{n-i}$,显然可以$o(n)$计算

 

关于上述dp式子的计算,可以使用cdq分治+NTT做到$o(n\log^{2}n)$,或使用生成函数进一步优化

具体的,定义$F(x)=\sum_{i\ge 0}\frac{f_{i}}{i!}x^{i}$,代入转移即
$$
\begin{array}{ll}
F(x)
&=\sum_{i\ge 0}\frac{\sum_{j=2}^{i}{i\choose j}(j-1)W^{j-2}f_{i-j}}{i!}x^{i}\\
&=1+\sum_{j\ge 2}\frac{(j-1)W^{j-2}}{j!}\sum_{i\ge j}\frac{f_{i-j}}{(i-j)!}x^{i}\\
&=1+\sum_{j\ge 2}\frac{(j-1)W^{j-2}}{j!}x^{j}F(x)
\end{array}
$$
简单移项,解得$F(x)=\frac{1}{1-\sum_{j\ge 2}\frac{(j-1)W^{j-2}}{j!}x^{j}}$,那么多项式求逆即可

时间复杂度为$o(n\log n)$,可以通过

[atARC134F]Flipping Coins
 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define N 200005
 4 #define mod 998244353
 5 #define ll long long
 6 int n,W,ans,mi[N],inv[N],rev[N<<2];
 7 struct Poly{
 8     vector<int>a;
 9     Poly(){
10         a.clear();
11     }
12 }a;
13 int qpow(int n,int m){
14     int s=n,ans=1;
15     while (m){
16         if (m&1)ans=(ll)ans*s%mod;
17         s=(ll)s*s%mod,m>>=1;
18     }
19     return ans;
20 }
21 void ntt(Poly &a,int n,int p=0){
22     for(int i=0;i<n;i++)
23         if (i<rev[i])swap(a.a[i],a.a[rev[i]]);
24     for(int i=2;i<=n;i<<=1){
25         int s=qpow(3,(mod-1)/i);
26         if (p)s=qpow(s,mod-2);
27         for(int j=0;j<n;j+=i)
28             for(int k=0,ss=1;k<(i>>1);k++,ss=(ll)ss*s%mod){
29                 int x=a.a[j+k],y=(ll)a.a[j+k+(i>>1)]*ss%mod;
30                 a.a[j+k]=(x+y)%mod,a.a[j+k+(i>>1)]=(x-y+mod)%mod;
31             }
32     }
33     if (p){
34         int s=qpow(n,mod-2);
35         for(int i=0;i<n;i++)a.a[i]=(ll)a.a[i]*s%mod;
36     }
37 }
38 Poly mul(Poly a,Poly b,int n){
39     int m=1;
40     while (m<n)m<<=1;
41     m<<=1,a.a.resize(m),b.a.resize(m);
42     for(int i=n;i<m;i++)a.a[i]=b.a[i]=0;
43     for(int i=0;i<m;i++)rev[i]=(rev[i>>1]>>1)+((i&1)*(m>>1));
44     ntt(a,m),ntt(b,m);
45     for(int i=0;i<m;i++)a.a[i]=(ll)a.a[i]*b.a[i]%mod;
46     ntt(a,m,1),a.a.resize(n);
47     return a;
48 }
49 Poly get_inv(Poly a,int n){
50     Poly ans;
51     if (n==1){
52         ans.a.push_back(qpow(a.a[0],mod-2));
53         return ans;
54     }
55     Poly s=get_inv(a,(n+1>>1));
56     ans=mul(s,a,n);
57     for(int i=0;i<n;i++)ans.a[i]=(mod-ans.a[i])%mod;
58     ans.a[0]=(ans.a[0]+2)%mod;
59     return mul(ans,s,n);
60 }
61 int main(){
62     scanf("%d%d",&n,&W);
63     mi[0]=inv[0]=inv[1]=1;
64     for(int i=1;i<N;i++)mi[i]=(ll)mi[i-1]*W%mod;
65     for(int i=2;i<N;i++)inv[i]=(ll)(mod-mod/i)*inv[mod%i]%mod;
66     for(int i=1;i<N;i++)inv[i]=(ll)inv[i-1]*inv[i]%mod;
67     for(int i=0;i<=n;i++){
68         if (!i)a.a.push_back(1);
69         if (i==1)a.a.push_back(0);
70         if (i>=2){
71             int s=(ll)(i-1)*mi[i-2]%mod*inv[i]%mod;
72             a.a.push_back((mod-s)%mod);
73         }
74     }
75     a=get_inv(a,n+1);
76     for(int i=0;i<=n;i++)ans=(ans+(ll)inv[i]*mi[i]%mod*a.a[n-i])%mod;
77     for(int i=1;i<=n;i++)ans=(ll)ans*i%mod; 
78     printf("%d\n",ans);
79     return 0;
80 }
View Code

 

上一篇:Spring 3整合Quartz 2实现定时任务三:动态暂停 恢复 修改和删除任务


下一篇:JAVA多线程机制之线程创建