首页 > 其他 > 详细

排列计数[SDOI2016]

时间:2017-08-21 20:05:56      阅读:29      评论:0      收藏:0      [点我收藏+]

标签:n-2   阶乘   perm   不能   表示   can   gcd   urn   但是   

题目描述

求有多少种长度为 n 的序列 A,满足以下条件:
1 ~ n 这 n 个数在序列中各出现了一次
若第 i 个数 A[i] 的值为 i,则称 i 是稳定的。序列恰好有 m 个数是稳定的
满足条件的序列可能很多,序列数对 10^9+7 取模。

输入

第一行一个数 T,表示有 T 组数据。
接下来 T 行,每行两个整数 n、m。
T=500000,n≤1000000,m≤1000000
 

输出

输出 T 行,每行一个数,表示求出的序列数

样例输入

5
1 0
1 1
5 2
100 50
10000 5000

样例输出

0
1
20
578028887
60695423

题解
这个数据范围,除了有公式否则怎么都过不了……然后开始推公式,这是个排列组合的问题吧,然后推推推,本来是手写了几种情况的,但是后来觉得可能不够准确就弃了。坚持从纯数学意义上推公式,然而有种悲剧叫数学能力不够,最终这题完全没有想到怎么做。据说是高考难度的数学题,但是我高考还没学到这,一年前夏令营陶陶讲的又差不多忘干净了QAQ。数学问题只能用数学方法拿分,这话相当有道理……
n个数里m个稳定,这一步用组合是毋庸置疑,随便预处理一下阶乘+乘法逆元就好。n-m个不稳定的是我在考场上没有想到解决办法的地方,整的式子推不出来,分类讨论又太过繁琐。然而这个错排是有公式的:f[n]=(n-1)*(f[n-1]+f[n-2])。
n个物品有n-1个位置可选,假设选定了k位置,考虑k的选择分两种,不选n和选n。不选n的情况,将n看作k,即k不能选择自身,转化为f[n-1];选N的情况即f[n-2]。

技术分享
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#define ll long long
using namespace std;
const int mod=1000000007;
const int sj=1000010;
int ca,n,m;
ll jc[sj],f[sj],ans;
ll e_gcd(ll n,ll m,ll &x,ll &y)
{
    if(m==0)
    {
       x=1,y=0;
       return n;
    }
    ll an=e_gcd(m,n%m,x,y);
    ll t=x;
    x=y;
    y=t-n/m*y;
    return an;
}
ll ny(ll a,ll c)
{
    ll x,y;
    ll gcd=e_gcd(a,c,x,y);
    x*=1/gcd;
    c/=gcd;
    if(c<0) c=-c;
    ll jg=x%c;
    if(jg<0) jg+=c;
    return jg;
}
int main()
{
    scanf("%d",&ca);
    jc[0]=jc[1]=1;
    for(int i=2;i<=sj-10;i++) jc[i]=(jc[i-1]*i)%mod;
    f[1]=0,f[0]=1;
    for(int i=2;i<=sj-10;i++)
      f[i]=((i-1)*(f[i-1]+f[i-2]))%mod;
    for(int l=1;l<=ca;l++)
    {
       scanf("%d%d",&n,&m);
       ans=(((jc[n]*ny(jc[m],mod))%mod)*ny(jc[n-m],mod))%mod;
       ans=(ans*f[n-m])%mod;
       printf("%lld\n",ans);
    }
    return 0;
}
permutation

 

 

排列计数[SDOI2016]

标签:n-2   阶乘   perm   不能   表示   can   gcd   urn   但是   

原文:http://www.cnblogs.com/moyiii-/p/7406292.html

(0)
(0)
   
举报
评论 一句话评论(0
0条  
登录后才能评论!
© 2014 bubuko.com 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号