[Hackerearth] StickerMix

 

Problem Link    : StickerMix
Category        : Math, Derangement
Contest         : December Circuits'23

#include "bits/stdc++.h"
using namespace std;
#define endl    '\n'
 
template <const int32_t MOD> struct modint {
    int32_t value;
    modint() = default;
    modint(int32_t value_) : value(value_) {}
    inline modint<MOD> operator + (modint<MOD> other) const { int32_t c = this->value + other.value; return modint<MOD>(c >= MOD ? c - MOD : c); }
    inline modint<MOD> operator - (modint<MOD> other) const { int32_t c = this->value - other.value; return modint<MOD>(c <    0 ? c + MOD : c); }
    inline modint<MOD> operator * (modint<MOD> other) const { int32_t c = (int64_t)this->value * other.value % MOD; return modint<MOD>(c < 0 ? c + MOD : c); }
    inline modint<MOD> & operator += (modint<MOD> other) { this->value += other.value; if (this->value >= MOD) this->value -= MOD; return *this; }
    inline modint<MOD> & operator -= (modint<MOD> other) { this->value -= other.value; if (this->value < 0) this->value += MOD; return *this; }
    inline modint<MOD> & operator *= (modint<MOD> other) { this->value = (int64_t)this->value * other.value % MOD; if (this->value < 0) this->value += MOD; return *this; }
    inline modint<MOD> operator - () const { return modint<MOD>(this->value ? MOD - this->value : 0); }
    modint<MOD> pow(uint64_t k) const { modint<MOD> x = *this, y = 1; for (; k; k >>= 1) { if (k & 1) y *= x; x *= x; } return y; }
    modint<MOD> inv() const { return pow(MOD - 2); }  // MOD must be a prime
    inline modint<MOD> operator /  (modint<MOD> other) const { return *this *  other.inv(); }
    inline modint<MOD> operator /= (modint<MOD> other)       { return *this *= other.inv(); }
    inline bool operator == (modint<MOD> other) const { return value == other.value; }
    inline bool operator != (modint<MOD> other) const { return value != other.value; }
    inline bool operator < (modint<MOD> other) const { return value < other.value; }
    inline bool operator > (modint<MOD> other) const { return value > other.value; }
};
template <int32_t MOD> modint<MOD> operator * (int64_t value, modint<MOD> n) { return modint<MOD>(value) * n; }
template <int32_t MOD> modint<MOD> operator * (int32_t value, modint<MOD> n) { return modint<MOD>(value % MOD) * n; }
template <int32_t MOD> istream & operator >> (istream & in, modint<MOD> &n) { return in >> n.value; }
template <int32_t MOD> ostream & operator << (ostream & out, modint<MOD> n) { return out << n.value; }
 
const int mod = 1e9 + 7;
using mint = modint<mod>;
 
const int maxn = 1e6 + 5;
 
mint fact[maxn];
mint derangements[maxn];
 
mint nCr(int n, int r) {
    return fact[n] / (fact[r] * fact[n - r]);
}
 
signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    cout.precision(12);
 
    bool FILEIO = 1;
    if (FILEIO and fopen("in.txt", "r")) {
        freopen("in.txt", "r", stdin);
    }
 
    fact[0] = 1;
    for (int i = 1; i < maxn; i++) {
        fact[i] = i * fact[i - 1];
        derangements[i] = i <= 2 ? i - 1 : (i - 1) * (derangements[i - 1] + derangements[i - 2]);
    }
 
    int tc;
    cin >> tc;
    for (int tcase = 1; tcase <= tc; tcase++) {
        int n;
        cin >> n;
        for (int i = 0; i < n; i++) {
            mint probability = nCr(n, i) * derangements[n - i] / fact[n];
            cout << probability << " ";
        }
        mint probability = mint(1) / fact[n];
        cout << probability << endl;
    }
}

[UVA] 12024 - Hats

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : 12024 - Hats
Source            : UVA Online Judge
Category          : Combinatorics
Algorithm         : Derangement
Verdict           : Accepted

1. #include <bits/stdc++.h>  
2.   
3. using namespace std;  
4.   
5. #define ll              long long  
6.   
7. static const int maxn = 21;  
8.   
9. ll nCr[maxn][maxn];  
10. ll fact[maxn];  
11.   
12. void factorial()  
13. {  
14.       fact[0] = 1;  
15.       for (int i = 1; i <= 20; i++) fact[i] = i * fact[i-1];  
16. }  
17.   
18. void combination()  
19. {  
20.       nCr[0][0] = 1;  
21.       for (int i = 1; i <= 20; i++)  
22.       {  
23.             nCr[i][i] = 1;  
24.             nCr[i][0] = 1;  
25.             for (int j = 1; j < i; j++)  
26.             {  
27.                   nCr[i][j] = nCr[i-1][j] + nCr[i-1][j-1];  
28.             }  
29.       }  
30. }  
31.   
32. int main()  
33. {  
34.       factorial();  
35.       combination();  
36.   
37.       int tc;  
38.       scanf("%d", &tc);  
39.       for (int tcase = 1; tcase <= tc; tcase++)  
40.       {  
41.             int n;  
42.             scanf("%d", &n);  
43.             ll derangement = fact[n];  
44.             for (int i = 1; i <= n; i++)  
45.             {  
46.                   if (i & 1) derangement -= nCr[n][i] * fact[n-i];  
47.                   else derangement += nCr[n][i] * fact[n-i];  
48.             }  
49.             printf("%lld/%lld\n", derangement, fact[n]);  
50.       }  
51. }