How many ways are for K people to work a one-day shift for N days so each of them works at least one day 
*

*Each person must work at least a day.



*Only one person can work in a given day.



Example: 2 people, 3 days -> 6 -> (1,1,2), (1,2,1), (1,2,2), (2,1,1), (2,1,2), (2,2,1)
 A: What you want is ${N \brace K}K!$. Where the brackets denote the Stirling number of the second kind.
This is because, first you must split the $N$ days into $K$ non-empty groups (this can be done in $N\brace K$ ways ). And then, these $K$ groups must be distributed among the $K$ persons, this can be done in $K!$ ways.
Calculating the Stirling numbers of the second kind on a computer is easy with a recursion, just as easy as calculating binomial coefficients, the important recursion is ${N\brace K}=K{N-1\brace K}+{N-1\brace K-1}$.
The following C++ code calculates ${ N \brace K}$ with the previous method:
#include <iostream>
using namespace std;

const int MAX=100;
int ST[MAX][MAX]; // here we store  {i,j} with i,j under MAX

int main(){
    for(int i=1; i<MAX; i++){
        ST[i][1]=1;
    }
    for(int i=1; i<MAX; i++){
        for(int j=2; j<MAX; j++){
            ST[i][j]=j*ST[i-1][j] + ST[i-1][j-1];
        }
    }
    int N,K;
    cin >> N >> K;
    cout << ST[N][K] << endl;
}


There is another way which does not use recursion (assuming you calculate the binomial coefficients otherwise).
It is the formula ${N \brace K} = \frac{1}{K!}\sum\limits_{i=0}^K(-1)^{K-i}\binom{K}{i}i^n$.
So your final answer is also $\sum\limits_{i=0}^K(-1)^{K-i}\binom{K}{i}i^n$. (the proof of this is simple via inclusion/exclusion)
This formula allows you to calculate each query in linear time (with respect to $K$). 
The other method allows you to precalculate all of the queries in time $K\cdot N$, but it answers each query in constant time.
