D. Almost Identity Permutations
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

A permutation p of size n is an array such that every integer from 1 to n occurs exactly once in this array.

Let's call a permutation an almost identity permutation iff there exist at least n - k indices i (1 ≤ i ≤ n) such that pi = i.

Your task is to count the number of almost identity permutations for given numbers n and k.

Input

The first line contains two integers n and k (4 ≤ n ≤ 1000, 1 ≤ k ≤ 4).

Output

Print the number of almost identity permutations for given n and k.

Examples
input
Copy 
4 1
output 
1
input
Copy 
4 2
output 
7
input
Copy 
5 3
output 
31
input
Copy 
5 4
output 
76



题意: 0~k(1<=k<=4)个不同的书放在不是原来位置的方案数

思路: 错排,组合数预处理的时候开ll   c1000会爆int

#include<bits/stdc++.h>
#define PI acos(-1.0)
#define push_back pb
using namespace std;
typedef long long ll;

const int MAX_N=1e6+50;
const int MOD=1e9+7;
const int INF=0x3f3f3f3f;

ll c[1005][1005];
int D[10];
/// 错排公式  D[0]=1,D[1]=0,D[2]=1,D[n]=(n-1)*(D[n-1]+D[n-2]);

void init(){
    c[0][0]=c[1][0]=c[1][1]=1;
    for(int i=2;i<=1000;i++){
        c[i][0]=1;
        for(int j=1;j<=i&&j<=4;++j) c[i][j]=c[i-1][j]+c[i-1][j-1];
    }
    D[0]=1;
    D[1]=0;
    D[2]=1;
    D[3]=2;
    D[4]=9;
}

int main(void){
    init();
    int n,k;
    cin >> n>>k;
    ll ans=1;
    for(int i=2;i<=k;i++){
        ans+=c[n][i]*(i-1)*(D[i-1]+D[i-2]);  //c[n][i]和c[n][n-i]相同
    }
    cout << ans << endl;
    return 0;
}