情侣？给我烧了！题解

P4921 MtOI2018 情侣？给我烧了！

传送门

考虑答案：

$$ans_k=C_n^k\times A_n^k\times 2^k\times g(n-k)$$

其中，$g(x)$ 代表 $x$ 对情侣都错开的方案总数。

上面的式子意义是：$n$ 对情侣中选 $k$ 对情侣 $C_n^k$；他们前后的相对位置共有 $A^k_n$ 中方案；每对情侣可以可以左右位置互换，有 $k$ 对，贡献 $2^k$ 中方案；其他情侣都错开的方案数 $g(n-k)$ 。

那么现在的问题变成求 $g(x)$ 的方法，不难看出 $g(x)$ 可通过递推来处理。

在错位的情侣共有三种情况：

• 男男

一共有 $x$ 个男人，选出两个男人的情况是：$C^2_x=x(x-1)$ 种情况。

然后考虑配偶情况分为两种情况：

1. 强制不配对，继续保持当前的情况，贡献：$g(x-1)$。

2. 强制配对，在剩下的 $x-1$ 排中许选择一排，两人顺序可以交换，转移：$2(x-1)\times g(x-2)$。

• 女女

情况同上。

• 一男一女（不是情侣）（和一女一男的情况）

可以交换的顺序方案为：$x(x-1)$。

$$g(x)=4x(x-1)\times (g(x-1)+2(x-1)\times (x-2))$$

代码

#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<queue>
#include<vector>
#include<stack>
#include<map> 
#include<unordered_map>
using namespace std;
long long r_r(){//快读 
  long long k=0,f=1;
  char c=getchar();
  while(!isdigit(c)){
    if(c=='-')f=-1;
    c=getchar();
  }
  while(isdigit(c)){
    k=(k<<1)+(k<<3)+(c^48);
    c=getchar(); 
  }
  return k*f;
}
const int o_o=1e3+10,m_d=998244353;
long long j_c[o_o];//阶乘 
long long n_y[o_o];//逆元 
long long n_j[o_o];//阶乘倒数逆元 
long long m_2[o_o];//2 的 n 次幂 
long long g[o_o];//记录函数 
void a_d(long long &a,long long b){
  a+=b;
  if(a>=m_d) a-=m_d;
}
long long k_m(long long a,long long b){//快速幂 
  long long r_s=1;
  while(b){
    if(b&1)r_s=r_s*a%m_d;
    a=a*a%m_d;
    b>>=1;
  }
  return r_s;
}
long long C(int n,int m){//组合数 
  return j_c[n]*n_j[n-m]%m_d*n_j[m]%m_d;
}
int main(){
  j_c[0]=n_j[0]=n_y[1]=m_2[0]=1;//初始化 
  for(int i=1;i<=o_o-10;i++){
    if(i>1)n_y[i]=(m_d-m_d/i)*n_y[m_d%i]%m_d;//乘法逆元 
    j_c[i]=j_c[i-1]*i%m_d;//阶乘，处理 A 
    n_j[i]=n_j[i-1]*n_y[i]%m_d;//阶乘的倒数逆元，和阶乘一起用处理 C 
    m_2[i]=m_2[i-1]*2%m_d;//2 的 n 次幂 
  }
  g[0]=1,g[1]=0;//初始化函数 
  for(int i=2;i<=o_o-10;i++)//将函数每个值都计算出来 
    g[i]=4ll*i*(i-1)%m_d*(g[i-1]+2*(i-1)*g[i-2])%m_d;//套公式 
  int q=r_r();
  while(q--){
    int x_x=r_r();
    for(int i=0;i<=x_x;i++)//输出结果 
      printf("%lld\n",C(x_x,i)*(C(x_x,i)%m_d*j_c[i])%m_d*m_2[i]%m_d*g[x_x-i]%m_d);
      //套公式 
  }
  return 0;
}

P4931 MtOI2018 情侣？给我烧了！（加强版）

传送门

假设 $f_k$ 代表恰好 $k$ 对情侣在一排的方案数，$g_k$ 为钦定 $k$ 同一排的方案数：

$$g_k=\sum^{n}_{i=k}f_i=C^k_nA^k_n2^k(2n-2k)!$$

二项式反演：

$$f_k=\sum_{i=k}^n(-1)^{i-k}C^k_ig_i$$

带入：

$$f_k=\sum_{i=k}^n(-1)^{i-k}C^k_iC^i_nA^i_n2^i(2n-2i)!$$ $$=\frac{(n!)^2}{k!}\sum_{i=k}^n{(-1)^{i-k}}\frac{2^i}{(i-k)!}C^{n-i}_{2n-2i}$$

设 $m=n-k$：

$$=\frac{(n!)^22^k}{k!}\sum_{i=k}^m{\frac{(-2)^{i}}{i!}}C^{m-i}_{2m-2i}$$

设：

$$A(x)=\sum_{i=0}^{\infty}{\frac{(-2)^i}{i!}x^i},B(x)=\sum^{\infty}_{i=0}{C^i_{2i}x^i}$$

则：

$$=\frac{(n!)^22^k}{k!}[x^m]A(x)\times B(x)$$

（$[x^m]$ 取 $x^m$ 的系数）。

$$A(x)=e^{-2k}$$

$B(x)$ 需要卡特兰数生成函数：

$$C(x)=\frac{\sqrt{1-4x}}{2x}=\sum_{i=0}^{\infty}{\frac{C^i_{2i}}{i+1}}x^i$$

移相，求导：

$$(C(x)\times x)^{'}=\sum_{i=0}^{\infty}{C^i_{2i}x^i}=\frac{1}{\sqrt{1-4x}}=B(x)$$ $$=\frac{(n!)^22^k}{k!}[x^m]\frac{e^{-2x}}{\sqrt{1-4x}}$$

设 $f(x)=\frac{e^{-2x}}{\sqrt{1-4x}}$，考虑他的系数。平方后移项：

$$(1-4x)f^2=e^{-4x}$$

两边同时求导，等号依然成立：

$$(1-4x)\times 2f\times f^{'}-4f^2=-4e^{-4x}$$

将：

$$(1-4x)f^2=e^{-4x}$$

带入：

$$(1-4x)\times 2f\times f^{'}-4f^2=-4(1-4x)f^2$$ $$(1-4x)\times 2f^{'}-4f=-4(1-4x)f$$ $$f_i= \begin{cases} f_0=1\\ f_1=0\\ f_i\times i=4(i-1)\times f_{i-1}+8f_{i-2}(i\ge 2) \end{cases}$$ $$ans_k=\frac{(n!)^22^k}{k!}f_{n-k}$$

代码

#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<queue>
#include<vector>
#include<stack>
#include<map> 
#include<unordered_map>
using namespace std;
long long r_r(){//快读 
  long long k=0,f=1;
  char c=getchar();
  while(!isdigit(c)){
    if(c=='-')f=-1;
    c=getchar();
  }
  while(isdigit(c)){
    k=(k<<1)+(k<<3)+(c^48);
    c=getchar();
  }
  return k*f;
}
const int o_o=5e6+10,m_d=998244353;
long long f[o_o];//递推函数 
long long n_y[o_o];//逆元 
long long j_c[o_o];//阶乘 
long long m_2[o_o];//2 的 n 次幂 
long long n_j[o_o];//阶乘倒数的逆元 
int main (){
  int t=r_r();
  j_c[0]=n_j[0]=n_y[1]=m_2[0]=f[0]=1,f[1]=0;//初始化 
  for(int i=2;i<=o_o-10;i++){
    n_y[i]=n_y[m_d%i]*(m_d-m_d/i)%m_d;//逆元 
    f[i]=(f[i-1]*4*(i-1)+f[i-2]*8)%m_d*n_y[i]%m_d;//递推函数 
  }
  for(int i=1;i<=o_o-10;i++){
    j_c[i]=j_c[i-1]*i%m_d;//阶乘 
    n_j[i]=n_j[i-1]*n_y[i]%m_d;//阶乘倒数逆元 
    m_2[i]=m_2[i-1]*2%m_d;//2 的 i 次幂 
  }
  while(t--){
    int n=r_r(),k=r_r();
    
    //套公式 
    long long a_s=j_c[n]*j_c[n]%m_d*m_2[k]%m_d*n_j[k]%m_d*f[n-k]%m_d;
    printf("%lld\n",a_s);
  }
  return 0;
}