题意:将一个序列的部分变为-1,要求k不能在k位置,已知变化后的序列问原序列有多少种

题解:不考虑不等于-1的部分,所有等于-1的部分对应的下标,可以分成两部分.

第一个部分是这个数的下标对应的数字不是-1,也就是说没有限制,有n1个

第二个部分是这个数的下标对应的数字是-1,也就是说有限制,这个数不能在这里,n2个

可以想到错排,错排可以用dp递推,也可以用容斥来推,这里用容斥

设f[i]为至少有i个数相同的序列个数f[i] = c(n2, i)*(n1+n2-i)!

相同的部分只能是n2中取,剩下的全排列

那么答案就是求f[0]并去除多余的部分

ans = f[0]-f[1]+f[2]-....+(-1)^n2*f[n2]

证明和错排一样,Ai为i在第i位的全排列

答案就是第一个不为1^第二个不为2....

摩根定律可以转化上面的式子...就是U-|容斥部分|

 

#include 
     
      #define ll long long#define maxn 100100using namespace std;const ll mod = 1e9+7;ll fc[maxn], fi[maxn], dir1[maxn], dir2[maxn], n, num1, num2, t;ll f(ll a,ll b){    ll ans = 1;    a %= mod;    while(b){        if(b&1) ans = ans*a%mod;        a = a*a%mod;        b >>= 1;    }    return ans;}void init(){    fc[0] = 1;    for(ll i=1;i<3000;i++) fc[i] = fc[i-1]*i%mod;    fi[2500] = f(fc[2500], mod-2);    for(ll i=2500;i>=1;i--) fi[i-1] = fi[i]*i%mod;}ll c(ll n,ll m){    if(n