【牛客 K-ary Heap】题意：问你某一个k叉堆是 所有可能的k叉堆中的第几个
思路：枚举第一个大于原序列的位置，得到大于该排列的k叉堆的总数，再用总数减去即可。
#include
using namespace std;
typedef long long LL;
typedef long long lint;
typedef pair pii;
const int maxn = 5005;
int a[maxn],fa[maxn];
vector ve[maxn];
int sz[maxn];
lint res[maxn];
typedef long long ll;
const ll oo=1000000007;
ll frac[maxn], carf[maxn];
ll inv(ll x){
if (x==1) return 1;
else return (oo-oo/x)*inv(oo%x)%oo;
}
LL ad( LL x,LL y ){
x += y;
return x%oo;
}
LL mul( LL x,LL y ){
x *= y;
return x%oo;
}
void init(){
frac[0]=1;
for (int i=1;
i<=5000;
i++)
frac[i]=frac[i-1]*i%oo;
carf[5000]=inv(frac[5000]);
for (int i=5000;
i>=1;
i--)
carf[i-1]=carf[i]*i%oo;
}ll C(int n, int m){
if (m>n) return 0;
else return frac[n]*carf[n-m]%oo*carf[m]%oo;
}
void dfs( int x,int f ){
fa[x] = f;
res[x] = 1;
sz[x] = 1;
for( inti = 0;
i < ve[x].size();
i++ ){
int y = ve[x][i];
dfs(y,x);
sz[x] += sz[y];
}
int le = sz[x]-1;
for( auto y:ve[x] ){
res[x] = mul( res[x],res[y]*C( le,sz[y] )%oo);
le -= sz[y];
}
}
void init( int n ){
for( int i = 0;
i <= n;
i++ ) ve[i].clear();
}
int b[maxn],n;
int lowbit( int x ){
return x&-x;
}
void add( int x,int v ){
while(x<=n){
b[x] += v;
x += lowbit(x);
}
}
int ask( int x ){
int res = 0;
while(x){
res += b[x];
x -= lowbit(x);
}
return res;
}
int query( int l,int r ){
if( l > r ) return 0;
return ask(r) - ask(l-1);
}
void initb( int n ){
for( int i =0 ;
i <= n;
i++ ) b[i] = 0;
for( int i = 2;
i <= n;
i++ ) add( i,1 );
}
set se;
LL ans = 0;
int main(){
init();
int T,k;
scanf("%d",&T);
for( int tt = 1;
tt <= T;
tt++ ){
printf("Case #%d: ",tt);
ans = 0;
scanf("%d%d",&n,&k);
init(n);
for( int i = 0;
i < n;
i++ )scanf("%d",&a[i]);
initb(n);
se.clear();
for( int i = 0;
i < n;
i++ )for( int j = k*i+1;
j <= min( k*i+k,n-1 );
j++ )ve[i].push_back(j);
dfs(0,-1);
for( auto x:ve[0] ) se.insert( pii( a[fa[x]],x ) );
for( int i = 1;
i < n;
i++ ){
LL re = 1;
int sum = 0;
se.erase( pii( a[fa[i]],i ) );
se.insert( pii( a[i],i ) );
for( auto p = se.rbegin();
p != se.rend();
p++ ){
int v = p->first;
int x = p->second;
int lef = query( v+1,n );
lef -= sum;
LL c =C( lef,sz[x] );
re = re * c %oo * res[x]%oo;
//ans += C( lef,sz[x] ) * res[x]%oo;
sum += sz[x];
}
ans = (ans + re)%oo;
add( a[i] ,-1);
se.erase( pii( a[i],i ) );
for( auto x : ve[i] ){
se.insert( pii( a[i],x ) );
}
}
LL ans0 = (res[0] - ans + oo)%oo;
printf("%lld\n",ans0);
}
return 0;
} 推荐阅读
- 刷题小结|51nod 1227 平均最小公倍数
- Code|CodeForces 839 D.Winter is here（莫比乌斯反演+组合数学）
- ACM|Codeforces 235E Number Challenge (神定理＋莫比乌斯反演)
- 算法和数据结构|生成r子集