UVA – 11282(Mixing Invitations)

Problem Name11282 – Mixing Invitations
JudgeUVA(OnlineJudge)
Problem Linkhttps://onlinejudge.org/external/112/11282.pdf
Algorithms & DSCombinatorics, Dearranement
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<ll>fact;
void ctFact(ll n)
{
    fact.resize(n+5);
    fact[0]=1;fact[1]=1;
    for(ll i=2;i<=n;i++){
        fact[i]=fact[i-1]*i;
    }
}

vector<ll>nCr[25];
void ctnCr(ll n)
{
    for(ll i=0;i<=n;i++){
        ll up=fact[i];
        for(ll j=0;j<=i;j++){
            ll down=fact[i-j]*fact[j];
            nCr[i].push_back(up/down);
        }
    }
}

int main()
{
    ctFact(20);
    ctnCr(20);
    ll n, m;
    while(cin>>n){
        cin>>m;
        ll ans=0;
        for(ll i=0;i<=m;i++){
            ll wrong=n-i;
            ll tmp_ans=0;
            bool tog=true;
            for(ll j=0;j<=wrong;j++){
                ll tmp=nCr[wrong][j]*fact[wrong-j];
                if(tog==true){
                    tmp_ans+=tmp;
                    tog=false;
                }else{
                    tmp_ans-=tmp;
                    tog=true;
                }
            }
            tmp_ans*=nCr[n][i];
            ans+=tmp_ans;
        }
        cout<<ans<<endl;
    }
    return 0;
}
Subscribe
Notify of
guest
0 Comments
Inline Feedbacks
View all comments
error: Alert: Content is protected !!