算法进阶-简单组合数学

High21 穿搭大挑战

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vll = vector<ll>;
#define pb push_back
#define m_p make_pair
#define fi first
#define se second
const int MOD = 1000000007;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3fLL;
inline ll addmod(ll a, ll b ,int mod) { return (a + b) % mod; }
inline ll submod(ll a, ll b ,int mod) { return (a - b + mod) %mod; }
inline ll mulmod(ll a, ll b ,int mod) { return a * b % mod; }
//HIGH21 穿搭大挑战
//https://www.nowcoder.com/practice/cd190da0f3614a8393c84981a11d024e
/*
 *简单组合数学
 *翻一下就是每次三个部位只穿两个，两两相乘相加就行了（乘法原理
 */

ll fastPower(ll a, ll b, ll mod) {
    ll res = 1;
    for (; b; b >>= 1) {
        if (b & 1) res = (res * a) % mod;
        a = a * a % mod;
    }
    return res%mod;
}

ll divmod(ll a, ll b, ll mod) {
    if (b == 0) return a;
    if (mod == 0) return b;
    ll inv = fastPower(b, mod-2, mod);
    return mulmod(a, inv ,mod);
}


void solve() {
    ll a,b,c;
    cin>>a>>b>>c;
    ll ans=a*b+b*c+a*c;
    cout<<ans<<'\n';
}


int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t=1;
    cin>>t;
    while(t--) {
        solve();
    }
    return 0;
}

High22 刷题统计

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vll = vector<ll>;
#define pb push_back
#define m_p make_pair
#define fi first
#define se second
const int MOD = 1000000007;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3fLL;
inline ll addmod(ll a, ll b ,int mod) { return (a + b) % mod; }
inline ll submod(ll a, ll b ,int mod) { return (a - b + mod) %mod; }
inline ll mulmod(ll a, ll b ,int mod) { return a * b % mod; }
//HIGH22 刷题统计
//https://www.nowcoder.com/practice/99ddb1a6e71d47dcbbe4f272aba532b8
/*
 *容斥原理
 *推演后为(a+b+c-d-n)/2
 *
 */

ll fastPower(ll a, ll b, ll mod) {
    ll res = 1;
    for (; b; b >>= 1) {
        if (b & 1) res = (res * a) % mod;
        a = a * a % mod;
    }
    return res%mod;
}

ll divmod(ll a, ll b, ll mod) {
    if (b == 0) return a;
    if (mod == 0) return b;
    ll inv = fastPower(b, mod-2, mod);
    return mulmod(a, inv ,mod);
}


void solve() {
    ll n,a,b,c,d;
    cin>>n>>a>>b>>c>>d;
    ll ans=(a+b+c-d-n)/2;
    cout<<ans<<'\n';
}


int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t=1;
    cin>>t;
    while(t--) {
        solve();
    }
    return 0;
}

High23 墙壁划线

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vll = vector<ll>;
#define pb push_back
#define m_p make_pair
#define fi first
#define se second
const int MOD = 1000000007;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3fLL;
inline ll addmod(ll a, ll b ,int mod) { return (a + b) % mod; }
inline ll submod(ll a, ll b ,int mod) { return (a - b + mod) %mod; }
inline ll mulmod(ll a, ll b ,int mod) { return a * b % mod; }
//HIGH23 墙壁划线
//https://www.nowcoder.com/practice/e197f9012fe74c4a9d003094bb3a2988
/*
 *根据数论中的一个经典结论，一条从 (0, 0) 连接到 (a, b) 的直线所经过的整数坐标点的数量为 gcd(a,b)+1
 *(gcd(a,b)+1)用来减去整数坐标位置被重复计算的点
 *单个线的穿过的点有：(a+1)+(b+1)-(gcd(a,b)+1)=a+b-gcd(a,b)+1，
 *这个值乘2就是答案，如果a,b中有一个偶数就得再-1(因为当是偶数时，中心点在网格线上被重复计算了一次，所以得-1)
 */

ll fastPower(ll a, ll b, ll mod) {
    ll res = 1;
    for (; b; b >>= 1) {
        if (b & 1) res = (res * a) % mod;
        a = a * a % mod;
    }
    return res%mod;
}

ll divmod(ll a, ll b, ll mod) {
    if (b == 0) return a;
    if (mod == 0) return b;
    ll inv = fastPower(b, mod-2, mod);
    return mulmod(a, inv ,mod);
}


void solve() {
    int a,b,x,y;
    cin >> a >> b >> x >> y;
    ll ans=2*(a+b-__gcd(a,b)+1);
    if (a%2==0||b%2==0) ans--;
    cout << ans;
}


int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t=1;
    //cin>>t;
    while(t--) {
        solve();
    }
    return 0;
}

High24 [HNOI2008]越狱

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vll = vector<ll>;
#define pb push_back
#define m_p make_pair
#define fi first
#define se second
const int MOD = 1000000007;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3fLL;
inline ll addmod(ll a, ll b ,int mod) { return (a + b) % mod; }
inline ll submod(ll a, ll b ,int mod) { return (a - b + mod) %mod; }
inline ll mulmod(ll a, ll b ,int mod) { return a * b % mod; }
//HIGH24 [HNOI2008]越狱
//https://www.nowcoder.com/practice/33d5016548d84cbe8cdb08ca0c13c2f1
/*
 *第一个房间可以是M种宗教中的任意一个，之后的房间只可能是M-1个中的一个
 *所以总的安全做法是 m*(m-1)^(n-1)
 *而总做法是m^n
 *所以不安全做法是m^n-m*(m-1)^(n-1)
 *记得用mod加减乘除
 *乘法原理相乘即可
 */

ll fastPower(ll a, ll b, ll mod) {
    ll res = 1;
    for (; b; b >>= 1) {
        if (b & 1) res = (res * a) % mod;
        a = a * a % mod;
    }
    return res%mod;
}

ll divmod(ll a, ll b, ll mod) {
    if (b == 0) return a;
    if (mod == 0) return b;
    ll inv = fastPower(b, mod-2, mod);
    return mulmod(a, inv ,mod);
}


void solve() {
    ll m,n;
    cin >> m >> n;
    ll all=fastPower(m,n,100003);
    ll ans=m*fastPower(m-1,n-1,100003)%100003;
    cout << submod(all,ans,100003);
}


int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t=1;
    //cin>>t;
    while(t--) {
        solve();
    }
    return 0;
}

High25 前缀平方和序列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vll = vector<ll>;
#define pb push_back
#define m_p make_pair
#define fi first
#define se second
const int MOD = 1000000007;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3fLL;
inline ll addmod(ll a, ll b ,int mod) { return (a + b) % mod; }
inline ll submod(ll a, ll b ,int mod) { return (a - b + mod) %mod; }
inline ll mulmod(ll a, ll b ,int mod) { return a * b % mod; }
//HIGH25 前缀平方和序列
//https://www.nowcoder.com/practice/51101e7b91064da8a10dbfd8c9217119
/*
 *通过x找到有几个可以使用的数能组成严格递增序列，
 *但神秘的是，题解是把x开方后找有几个可使用的数
 *我是预处理1e6内的平方数后反推
 *
 *反正是过了
 */

ll fastPower(ll a, ll b, ll mod) {
    ll res = 1;
    for (; b; b >>= 1) {
        if (b & 1) res = (res * a) % mod;
        a = a * a % mod;
    }
    return res%mod;
}

ll divmod(ll a, ll b, ll mod) {
    if (b == 0) return a;
    if (mod == 0) return b;
    ll inv = fastPower(b, mod-2, mod);
    return mulmod(a, inv ,mod);
}

template<typename T>
T combination(T n, T k) { //组合数计算模版，C(n,k)，适用于整数类型
    if (k < 0 || k > n) return 0;
    if (k > n - k) k = n - k;
    T result = 1;
    for (T i = 1; i <= k; ++i) {
        result = mulmod(result,(n - k + i),MOD);
        result = divmod(result,i,MOD);
    }
    return result;
}

void solve() {
    map<ll,ll>map; //预处理平方数
    for (int i=1;;i++) {
        ll temp=i*i;
        map[temp]=i;
        if (temp>1e6l) break;
    }

    ll n,x;
    cin>>n>>x;
    ll k=0;
    while (!k) { //找x向下的第一个开方数
        k=map[x];
       // cout<<k<<' ';
        x--;
       // cout<<n<<endl;
    }

    //cout<<k<<' '<<n<<' ';;
    ll ans=combination(k,n);
    cout<<ans;
}



int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t=1;
    //cin>>t;
    while(t--) {
        solve();
    }
    return 0;
}

High26 分割序列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vll = vector<ll>;
#define pb push_back
#define m_p make_pair
#define fi first
#define se second
const int MOD = 1000000007;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3fLL;
inline ll addmod(ll a, ll b ,int mod) { return (a + b) % mod; }
inline ll submod(ll a, ll b ,int mod) { return (a - b + mod) %mod; }
inline ll mulmod(ll a, ll b ,int mod) { return a * b % mod; }
//HIGH26 分割序列
//https://www.nowcoder.com/practice/f49a64748c2344c1be65f9be417a495a
/*
 *以1为分隔符，1之间的0的数量相乘就是答案，乘法原理
 *
 */

ll fastPower(ll a, ll b, ll mod) {
    ll res = 1;
    for (; b; b >>= 1) {
        if (b & 1) res = (res * a) % mod;
        a = a * a % mod;
    }
    return res%mod;
}

ll divmod(ll a, ll b, ll mod) {
    if (b == 0) return a;
    if (mod == 0) return b;
    ll inv = fastPower(b, mod-2, mod);
    return mulmod(a, inv ,mod);
}

template<typename T>
T combination(T n, T k) { //组合数计算模版，C(n,k)，适用于整数类型
    if (k < 0 || k > n) return 0;
    if (k > n - k) k = n - k;
    T result = 1;
    for (T i = 1; i <= k; ++i) {
        result = mulmod(result,(n - k + i),MOD);
        result = divmod(result,i,MOD);
    }
    return result;
}

void solve() {
    ll n,first1=-1;
    string s;
    cin>>n>>s;
    for (ll i = 0; i < n; i++) {
        if (s[i] == '1') {
            first1 = i;
            break;
        }

    }

    if (first1 == -1) {
        cout<<"0";
        return;
    }

    ll ans=1,now0=0;
    for (ll i = first1+1; i < n; ++i) {
        if (s[i] == '0') {
            now0++;
        }
        else {
            ans = mulmod(ans,now0+1,MOD);
            now0 = 0;
        }
    }
    cout<<ans;

}



int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t=1;
    //cin>>t;
    while(t--) {
        solve();
    }
    return 0;
}

High28 矩形计数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vll = vector<ll>;
#define pb push_back
#define m_p make_pair
#define fi first
#define se second
const int MOD = 1000000007;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3fLL;
inline ll addmod(ll a, ll b ,int mod) { return (a + b) % mod; }
inline ll submod(ll a, ll b ,int mod) { return (a - b + mod) %mod; }
inline ll mulmod(ll a, ll b ,int mod) { return a * b % mod; }
//HIGH28 矩形计数
//https://www.nowcoder.com/practice/0ece8b3002c94320b8866ff0fc5d5fe0
/*
 *注意！
 *这道题同一集合的方块只要在同一行或同一列即可
 *不需要连续，所以只要知道一行/一列有白和黑各几个方块就可以知道这一行/这一列的数量
 *通过计算可知一行/一列有n个同色方块，则有2^n-1种可能
 *同时要根据容斥原理，记得删去一遍单个方块集合数量
 *只有一个方块的集合会被重复计算一次
 */

ll fastPower(ll a, ll b, ll mod) {
    ll res = 1;
    for (; b; b >>= 1) {
        if (b & 1) res = (res * a) % mod;
        a = a * a % mod;
    }
    return res%mod;
}

ll divmod(ll a, ll b, ll mod) {
    if (b == 0) return a;
    if (mod == 0) return b;
    ll inv = fastPower(b, mod-2, mod);
    return mulmod(a, inv ,mod);
}

template<typename T>
T combination(T n, T k) { //组合数计算模版，C(n,k)，适用于整数类型
    if (k < 0 || k > n) return 0;
    if (k > n - k) k = n - k;
    T result = 1;
    for (T i = 1; i <= k; ++i) {
        result = mulmod(result,(n - k + i),MOD);
        result = divmod(result,i,MOD);
    }
    return result;
}

void solve() {
    ll n,m;
    cin>>n>>m;
    vector<vector<ll>> a(n+1, vector<ll>(m+1,0));
    vll white_col(n+1,0),black_col(n+1,0),white_raw(m+1,0),black_raw(m+1,0);
    for (ll i = 1; i <= n; ++i) {
        for (ll j = 1; j <= m; ++j) {
            cin>>a[i][j];
            if (a[i][j] == 1) {
                black_col[i] ++;
                black_raw[j] ++;
            }else {
                white_col[i] ++;
                white_raw[j] ++;
            }
        }
    }


    ll ans=0;
    for (ll i = 1; i <= n; ++i) {
        //cout<<white_col[i]<<" "<<black_col[i]<<endl;
        if (white_col[i]!=0)ans=addmod(ans,fastPower(2,white_col[i],MOD)-1,MOD);
        if (black_col[i]!=0)ans=addmod(ans,fastPower(2,black_col[i],MOD)-1,MOD);
    }
    for (ll i = 1; i <= m; ++i) {
        if (white_raw[i]!=0)ans=addmod(ans,fastPower(2,white_raw[i],MOD)-1,MOD);
        if (black_raw[i]!=0)ans=addmod(ans,fastPower(2,black_raw[i],MOD)-1,MOD);
        ans=submod(ans,white_raw[i],MOD);
        ans=submod(ans,black_raw[i],MOD);
    }


    cout<<ans;



}



int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t=1;
    //cin>>t;
    while(t--) {
        solve();
    }
    return 0;
}

High29 【模板】组合数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vll = vector<ll>;
#define pb push_back
#define m_p make_pair
#define fi first
#define se second
const int MOD = 1000000007;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3fLL;
inline ll addmod(ll a, ll b ,int mod) { return (a + b) % mod; }
inline ll submod(ll a, ll b ,int mod) { return (a - b + mod) %mod; }
inline ll mulmod(ll a, ll b ,int mod) { return a * b % mod; }
//HIGH29 【模板】组合数
//https://www.nowcoder.com/practice/53f82db091b2452bae5fef4437ffd0bb
/*
 *组合数模版
 */

ll fastPower(ll a, ll b, ll mod) {
    ll res = 1;
    for (; b; b >>= 1) {
        if (b & 1) res = (res * a) % mod;
        a = a * a % mod;
    }
    return res%mod;
}

ll divmod(ll a, ll b, ll mod) {
    if (b == 0) return a;
    if (mod == 0) return b;
    ll inv = fastPower(b, mod-2, mod);
    return mulmod(a, inv ,mod);
}


const int MAXN = 5e5;   //记得修改n的范围
ll fact[MAXN + 1];      // 阶乘
ll invFact[MAXN + 1];   // 阶乘的逆元

// 初始化，在 main 开头调用一次，传入模数
void initComb(int mod) {
    fact[0] = 1;
    for (int i = 1; i <= MAXN; ++i)
        fact[i] = mulmod(fact[i - 1], i, mod);

    invFact[MAXN] = fastPower(fact[MAXN], mod - 2, mod);
    for (int i = MAXN; i >= 1; --i)
        invFact[i - 1] = mulmod(invFact[i], i, mod);
}

// 查询 C(n, k) % mod，O(1) ,需要初始化，适合n大一点的，查询次数多，有mod限制的情况
ll combination2(int n, int k, int mod) {
    if (k < 0 || k > n) return 0;
    return mulmod(mulmod(fact[n], invFact[k], mod), invFact[n - k], mod);
}


void solve() {
    ll n,m;
    cin >> n >> m;
    ll ans=combination2(m,n,MOD);
    cout << ans << '\n';
}



int main() {
    initComb(MOD);
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t=1;
    cin>>t;
    while(t--) {
        solve();
    }
    return 0;
}

High30 人员分组问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vll = vector<ll>;
#define pb push_back
#define m_p make_pair
#define fi first
#define se second
const int MOD = 1000000007;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3fLL;
inline ll addmod(ll a, ll b ,int mod) { return (a + b) % mod; }
inline ll submod(ll a, ll b ,int mod) { return (a - b + mod) %mod; }
inline ll mulmod(ll a, ll b ,int mod) { return a * b % mod; }
//HIGH30 人员分组问题
//https://www.nowcoder.com/practice/482f31bf028f46aa9b7882a4b921ffcf
/*
 *组合数模版
 *C(n,5)+C(n,6)+C(n,7)就是答案
 */

ll fastPower(ll a, ll b, ll mod) {
    ll res = 1;
    for (; b; b >>= 1) {
        if (b & 1) res = (res * a) % mod;
        a = a * a % mod;
    }
    return res%mod;
}

ll divmod(ll a, ll b, ll mod) {
    if (b == 0) return a;
    if (mod == 0) return b;
    ll inv = fastPower(b, mod-2, mod);
    return mulmod(a, inv ,mod);
}


const int MAXN = 1e6;   //记得修改n的范围
ll fact[MAXN + 1];      // 阶乘
ll invFact[MAXN + 1];   // 阶乘的逆元

// 初始化，在 main 开头调用一次，传入模数
void initComb(int mod) {
    fact[0] = 1;
    for (int i = 1; i <= MAXN; ++i)
        fact[i] = mulmod(fact[i - 1], i, mod);

    invFact[MAXN] = fastPower(fact[MAXN], mod - 2, mod);
    for (int i = MAXN; i >= 1; --i)
        invFact[i - 1] = mulmod(invFact[i], i, mod);
}

// 查询 C(n, k) % mod，O(1) ,需要初始化，适合n大一点的，查询次数多，有mod限制的情况
ll combination2(int n, int k, int mod) {
    if (k < 0 || k > n) return 0;
    return mulmod(mulmod(fact[n], invFact[k], mod), invFact[n - k], mod);
}


void solve() {
    ll n,m;
    cin >> n;
    ll ans=addmod(addmod(combination2(n,5,MOD),combination2(n,6,MOD),MOD), combination2(n,7,MOD), MOD);
    cout << ans;
}



int main() {
    initComb(MOD);
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t=1;
    //cin>>t;
    while(t--) {
        solve();
    }
    return 0;
}

High31 长椅安置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vll = vector<ll>;
#define pb push_back
#define m_p make_pair
#define fi first
#define se second
const int MOD = 1000000007;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3fLL;
inline ll addmod(ll a, ll b ,ll mod) { return (a + b) % mod; }
inline ll submod(ll a, ll b ,ll mod) { return (a - b + mod) %mod; }
inline ll mulmod(ll a, ll b ,ll mod) { return a * b % mod; }
//HIGH31 长椅安置
//https://www.nowcoder.com/practice/35ed6ac93abc43e39fe2fe3fb49ee9fc
/*
 *行列各可以选C(n，5)
 *排列所有可能P(n，5)
 *答案就是这俩相乘
 *等价于P(n，5)*P(n，5)/120
 *等价于P(n，5)/120*P(n，5)（防止溢出
 */

ll fastPower(ll a, ll b, ll mod) {
    ll res = 1;
    for (; b; b >>= 1) {
        if (b & 1) res = (res * a) % mod;
        a = a * a % mod;
    }
    return res%mod;
}

ll divmod(ll a, ll b, ll mod) {
    if (b == 0) return a;
    if (mod == 0) return b;
    ll inv = fastPower(b, mod-2, mod);
    return mulmod(a, inv ,mod);
}


ll combination1(ll n, ll k, ll mod) {//查询O(k)，适合少量查询
    if (k < 0 || k > n) return 0;
    if (k > n - k) k = n - k;
    ll result = 1;
    for (ll i = 1; i <= k; ++i) {
        result = mulmod(result, n - k + i, mod);
        result = divmod(result, i, mod);
    }
    return result;
}

ll permutation1(ll n, ll k, ll mod) {
    if (k < 0 || k > n) return 0;
    ll result = 1;
    for (ll i = 0; i < k; ++i) {
        result = mulmod(result, n - i, mod);   // 依次乘 n, n-1, ..., n-k+1
    }
    return result;
}

void solve() {
    ll n;
    cin >> n;
    ll ans = permutation1(n,5,LINF);
    cout << ans/120*ans;
}




int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t=1;
    //cin>>t;
    while(t--) {
        solve();
    }
    return 0;
}