题目

求逆续对个数为\(k\)的\(n\)阶排列个数\(mod \ 1e9+7\)

$1 \le n \ , \ k \le 10^5 $ 

题解

  • $f_{i,j} = \sum_{k=0}^{i-1} f_{i-1,j-k} $

  • 则有\(F_i(x) = F_{i-1}(x) * \sum_{j=0}^{i-1}x^j = F_{i-1}(x)\frac{1-x^i}{1-x}\)

  • $F(x) \ = \ \frac{\prod_{i=1}{n}1-xi}{(1-x)^n} $

  • 分母可以直接展开成$ \sum_i C_{n+i-1}^{i} x^i $

  • 分子的求法有两种:

    • 1.取\(= exp(ln(\prod 1-x^i)) = exp( -\sum_{j\ge1} \frac{x^{ij}}{j})\)

    由于只需要前\(K\)项,所以求exp里面的部分是\(n log \ n\),接着套exp模板

    时间复杂度:\(O(n \ log \ n )\) (由于要写mtt常数巨大...)

    • 2.这个式子本质是一个背包问题,注意到可选的物品个数不超过\(\sqrt{2K}\)

    设\(g_{i,j}\)表示选了\(i\)个物品,容积为\(j\)的系数和,考虑体积的变化

    \(g_{i,j} \ = \ g_{i,j-i} - g_{i-1,j-i} + g_{i-1,j-n-1}\)

    时间复杂度:$O(n \sqrt{N}) $

Code

//sol 2
#include<bits/stdc++.h>
#define ll long long
#define ld double
#define mod 1000000007
#define il inline
#define rg register
using namespace std;
const int N=100010,M=500;
int n,m,K,fac[N<<1],inv[N<<1],ny[N<<1],f[M][N],a[N];
il void dec(int&x,int y){x-=y;if(x<0)x+=mod;}
il void inc(int&x,int y){x+=y;if(x>=mod)x-=mod;}
int cal(int x,int y){return x<y?0:1ll*fac[x]*inv[y]%mod*inv[x-y]%mod;}
int main(){
freopen("b.in","r",stdin);
freopen("b.out","w",stdout);
scanf("%d%d",&n,&K);
ny[1]=fac[0]=inv[0]=1;
for(int i=2;i<=n+K;++i)ny[i]=1ll*(mod-mod/i)*ny[mod%i]%mod;
for(int i=1;i<=n+K;++i){
fac[i]=1ll*fac[i-1]*i%mod;
inv[i]=1ll*inv[i-1]*ny[i]%mod;
} m=sqrt(2*K)+1;f[0][0]=1;
for(int i=1;i<=m;++i)
for(int j=i;j<=K;++j){
f[i][j]=(f[i][j-i]-f[i-1][j-i]+mod)%mod;
if(j>=n+1)inc(f[i][j],f[i-1][j-n-1]);
}
for(int i=0;i<=K;++i)
for(int j=0;j<=m;++j)inc(a[i],f[j][i]); int ans=0;
for(int i=0;i<=K;++i){
ll tmp=1ll*a[i]*cal(K-i+n-1,n-1)%mod;
inc(ans,tmp);
}
cout<<ans<<endl;
return 0;
}
//sol 1
#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define il inline
#define rg register
using namespace std;
const int N=1<<20,all=(1<<15)-1,mod=1e9+7;
const ld pi=acos(-1);
int n,K,ny[N],fac[N],inv[N],a[N],b[N],c[N],lst=-1;
il void inc(int&x,int y){x+=y;if(x>=mod)x-=mod;}
il void dec(int&x,int y){x-=y;if(x<0)x+=mod;}
il int cal(int x,int y){return x<y?0:(ll)fac[x]*inv[y]%mod*inv[x-y]%mod;}
struct C{
ld x,y;
C(ld _x=0,ld _y=0):x(_x),y(_y){};
C operator +(const C&A){return C(x+A.x,y+A.y);}
C operator -(const C&A){return C(x-A.x,y-A.y);}
C operator *(const C&A){return C(x*A.x-y*A.y,x*A.y+y*A.x);}
C operator /(const ld&A){return C(x/A,y/A);}
C operator !(){return C(x,-y);}
}Wn[2][N];
namespace poly{
int rev[N],L;
il void init(int l){
for(rg int i=1;i<l;i<<=1){
Wn[0][i]=C(cos(pi/i),sin(pi/i));
Wn[1][i]=!Wn[0][i];
}
}
il void fft(C*A,int l,int f){
for(L=0;(1<<L)<l;++L);
for(rg int i=0;i<l;++i){
rev[i]=(rev[i>>1]>>1)|((i&1)<<(L-1));
if(i<rev[i])swap(A[i],A[rev[i]]);
}
for(rg int i=1;i<l;i<<=1){
C wn=Wn[!~f][i];
for(rg int j=0;j<l;j+=i<<1){
C w(1,0);
for(rg int k=0;k<i;++k,w=w*wn){
C x=A[j+k],y=w*A[j+k+i];
A[j+k]=x+y,A[j+k+i]=x-y;
}
}
}
if(!~f)for(int i=0;i<l;++i)A[i]=A[i]/l;
}
il void mtt(int*A,int*B,int l){
static C t1[N],t2[N],t3[N],t4[N];
for(rg int i=0;i<l;++i){
t1[i]=C(A[i]&all,A[i]>>15);
t2[i]=C(B[i]&all,B[i]>>15);
}
fft(t1,l,1),fft(t2,l,1);
for(rg int i=0;i<l;++i){
C x1=t1[i],y1=!t1[(l-i)&(l-1)];
C x2=t2[i];
t3[i]=(x1+y1)*x2*C(0.5,0);
t4[i]=(x1-y1)*x2*C(0,-0.5);
}
fft(t3,l,-1),fft(t4,l,-1);
for(rg int i=0;i<l;++i){
A[i]=(
(ll)(t3[i].x+0.1)%mod
+( (ll)(t3[i].y+t4[i].x+0.1)%mod<<15)
+( (ll)(t4[i].y+0.1)%mod<<30)
)%mod;
}
}
il void cpy(int*A,int*B,int l){for(rg int i=0;i<l;++i)A[i]=B[i];}
il void clr(int*A,int l,int r){for(rg int i=l;i<r;++i)A[i]=0;}
il void dif(int*A,int l){for(rg int i=0;i<l-1;++i)A[i]=(ll)(i+1)*A[i+1]%mod;A[l-1]=0;}
il void der(int*A,int l){for(rg int i=l-1;i;--i)A[i]=(ll)ny[i]*A[i-1]%mod;A[0]=0;}
void inv(int*A,int*B,int l){
if(l==1){B[0]=1;return;}
static int t1[N];
inv(A,B,l>>1);
int len=l<<1;
cpy(t1,A,l),clr(t1,l,len);
clr(B,l,len);
mtt(t1,B,len);//clr(t1,l,len);
mtt(t1,B,len);//clr(t1,l,len);
for(rg int i=0;i<l;++i)B[i]=(2ll*B[i]-t1[i]+mod)%mod;
//clr(B,l,len);
}
void ln(int*A,int*B,int l){
static int t1[N];
int len=l<<1;
cpy(t1,A,l),clr(t1,l,len),dif(t1,l);
inv(A,B,l);
mtt(B,t1,len);
der(B,l),clr(B,l,len);
}
void exp(int*A,int*B,int l){
if(l==1){B[0]=1;return;}
static int t1[N];
exp(A,B,l>>1);
int len=l<<1;
ln(B,t1,l);
for(rg int i=0;i<l;++i)t1[i]=(A[i]-t1[i]+mod)%mod;
inc(t1[0],1);
mtt(B,t1,len),clr(B,l,len);
}
}
int main(){
freopen("b.in","r",stdin);
freopen("b3.out","w",stdout);
scanf("%d%d",&n,&K);
int len=1;while(len<=K)len<<=1;
int mx=max(n+K,len<<1);
ny[1]=1;for(rg int i=2;i<=mx;++i)
ny[i]=(ll)(mod-mod/i)*ny[mod%i]%mod;
for(rg int i=inv[0]=fac[0]=1;i<=n+K;++i){
inv[i]=1ll*inv[i-1]*ny[i]%mod;
fac[i]=1ll*fac[i-1]*i%mod;
}
for(rg int i=1;i<=n;++i)
for(rg int j=1;j<=K/i;++j)dec(a[i*j],ny[j]);
poly::init(len<<1);
poly::exp(a,b,len); int ans=0;
for(rg int i=0;i<=K;++i){
inc(ans,1ll*b[i]*cal(n+K-i-1,K-i)%mod);
}
cout<<ans<<endl;
return 0;
}//
//卡不过去....
//20190704

最新文章

  1. jQuery源码-jQuery.fn.attr与jQuery.fn.prop
  2. java泛型的使用
  3. python中读取配置文件ConfigParser
  4. 【转载】为什么不建议&lt;=3G的情况下使用CMS GC
  5. linux 学习之七-部分ssh命令
  6. db2 备份还原
  7. GO开发[六]:golang反射(reflect)
  8. selenium 不同版本Driver
  9. 微服务下 Spring Boot Maven 工程依赖关系管理
  10. learning makefile grammar
  11. day15_python_1124
  12. Javascript面试题收集
  13. SC-FDM和OFDM的区别
  14. EasyUi通过POI 实现导出xls表格功能
  15. tomcat启动时设定环境变量
  16. 实战-130W表增加字段耗时
  17. HTTP协议 - 协议格式
  18. PAT 1061. Dating
  19. BZOJ3675: [Apio2014]序列分割(斜率优化)
  20. OKVIS(一)初始化流程及代码结构

热门文章

  1. Web负载均衡学习笔记之K8S内Ngnix微服务服务超时问题
  2. apache设置外网访问的方法 (服务器)
  3. .NET / C# EF中的基础操作(CRUD)
  4. jQuery实现form表单基于ajax无刷新提交方法详解
  5. 递归-求n和n以前的自然数
  6. drf序列化与反序列化
  7. MySQL基础-1
  8. HTML5 新增文本标签
  9. EXCHANGE上冒充任意用户--Exchange Server权限提升漏洞(CVE-2018-8581)分析
  10. Springboot+Mybatis的逆向工程