[atAGC045D]Lamps and Buttons

由于$p_{i}$是随机的，不断选择最小的、未被操作过的$i$并处理其所在的环一定是最优的，而这样与已知$p_{i}$的区别是，当选择了一个$i=p_{i}$，那么必然失败（而已知$p_{i}$时不会去选择）

考虑令$t=\min_{p_{i}=i或i=A+1}i$，我们只能操作到$t-1$为止，因此即要求：

1.$\forall 1\le i<t,i\ne p_{i}$，同时若$t\le A$，则$p_{t}=t$

2.$\forall A<i\le n$，满足$\exists 1\le j<t,i和j在同一个环中$

对于$1\le i<t,i=p_{i}$的$i$数量容斥，即枚举这个数量$j$，之后这$j$个位置以及$t$（若$t\le A$）可以看作删除（这里有$(-1)^{j}{t-1\choose j}$的系数）

通过容斥，我们就去除了第一个条件（注意：容斥仅仅强制了这$j$个位置满足$p_{i}=i$，对其余位置没有限制），再整理一下，可以看作以下问题——

令$x=t-1-j$（初始是亮的且可以操作）、$y=\max(A-t,0)$（初始是亮的但不能操作）和$z=n-A$（初始不亮），统计$x+y+z$阶的排列：$\forall i\in z$，满足$\exists j\in x,i和j在同一个环中$

（上面的$\in x$指属于这$x$个点中的一个，$y$和$z$类似）

将排列看作一张有向图，每一次插入$i$，有两种可能：

新建一条边$(i,i)$或选择一条边$(x,y)$，删除该边并建立$(x,i)$和$(i,y)$（$x$可以等于$y$）

归纳可得这样可以得到所有排列（所对应的有向图），同时我们考虑依次插入$x+y+z$个数，对于前$x$个数是任意的，再填$z$个数，但都只能在之前插入而不能选择自环，最后$y$个数依旧任意

（如果先填$y$个数，那么$z$不能选择仅由$y$组成的环，因此不正确）

根据乘法原理将这些乘起来，即$\frac{x(x+y+z)!}{x+z}$，综合前面答案即为$\sum_{t=1}^{A+1}\sum_{j=0}^{t-1}(-1)^{j}{t-1\choose j}\frac{x(x+y+z)!}{x+z}$，预处理阶乘和逆元就可以做到$o(n+A^{2})$

 1 #include<bits/stdc++.h>

 2 using namespace std;

 3 #define N 10000005

 4 #define mod 1000000007

 5 int n,a,ans,fac[N],inv[N],inv_fac[N];

 6 int c(int n,int m){

 7     return 1LL*fac[n]*inv_fac[m]%mod*inv_fac[n-m]%mod;

 8 }

 9 int calc(int x,int y,int z){

10     return 1LL*fac[x+y+z]*x%mod*inv[x+z]%mod;

11 }

12 int main(){

13     scanf("%d%d",&n,&a);

14     fac[0]=inv[0]=inv[1]=inv_fac[0]=1;

15     for(int i=1;i<N-4;i++)fac[i]=1LL*fac[i-1]*i%mod;

16     for(int i=2;i<N-4;i++)inv[i]=1LL*(mod-mod/i)*inv[mod%i]%mod;

17     for(int i=1;i<N-4;i++)inv_fac[i]=1LL*inv_fac[i-1]*inv[i]%mod;

18     for(int i=1;i<=a+1;i++)

19         for(int j=0;j<i;j++){

20             int s=1LL*c(i-1,j)*calc(i-1-j,max(a-i,0),n-a)%mod;

21             if (j&1)s=mod-s;

22             ans=(ans+s)%mod;

23         }

24     printf("%d",ans);

25 }

巴特西

[atAGC045D]Lamps and Buttons

最新文章

热门文章