AcWing 569. 猜拳游戏    原题链接    简单

作者： 作者的头像   这个显卡不太冷 ,  2019-04-01 00:26:12 ,  所有人可见 ,  阅读 1656

3


2

组合数

从n个位置选s个胜利，其他位置任选两种状态
$C{(n,s)} * 2^{n - s}$

暴力逆元，真O(n)算法，比xc大佬上课讲的近似o(n)更快

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int mod = 1e9 + 7;
ll c[2002][2002];
ll ksm(ll n, ll k)
{
    ll res = 1;
    while(k)
    {
        if(k & 1) res = (res * n) % mod;
        n = (n * n) % mod;
        k >>= 1;
    }
    return res % mod;
}
int main()
{
    int n, s; cin >> n >> s;
    ll ans1 = 1, ans2 = 1;
    for(int i = n, j = 1; j <= s; j++, i--) ans1 = (ans1 * i) % mod;
    for(int i = 1; i <= s; i++) ans2 = (ans2 * i) % mod;
    ans2 = ksm(ans2, mod - 2);
    ll ans = (((ans1 * ans2) % mod) * ksm(2, n - s)) % mod;
    cout<<ans;
}

7 评论

用户头像
Deft   2021-09-15 19:37         踩      回复

tql

用户头像
GRID   2020-07-28 10:44         踩      回复

请问ans2 = ksm(ans2, mod - 2);为什么要把mod-2传进去？

用户头像
这个显卡不太冷   2020-07-28 23:14         踩      回复

$x^{p-2}$即$x$在模质数$p$条件下的逆元

用户头像
哈哈哈hh   2020-06-29 13:42         踩      回复

老哥，这样写怎么纠错了哇，不是拟元的思想

#include<iostream>
#include <stack>
#include <string>
#include <cmath>

using namespace std;
const int mod = 1e9 + 7;
const int N = 2010;
int a[N];
int f[N][N];


int qmid(int k, int n)
{
    int res = 1;
    while(n)
    {
        if(n & 1) res =  res * k % mod;
        k = k*k % mod;
        n >>= 1;
    }
    return res % mod;
}
int main(){
    int n = 0;
    int m = 0;
    cin >> n >> m;
    for(int i = 0; i < n; i++)
    {
        cin >> a[i];
    }
    for(int i = 0; i <= n; i++)
    {
        for(int j = 0; j <= m ;j++)
        {
            if(!j) f[i][j] = 1;
            else f[i][j] = (f[i-1][j] + f[i - 1][j - 1])% mod;
        }
    }
    cout << (f[n][m] * qmid(2,n - m)) % mod <<endl;
}
用户头像
kennyassj   2019-04-13 22:16         踩      回复

不写注释看不懂啊- -

用户头像
这个显卡不太冷   2019-04-15 16:59         踩      回复

这里需要用到 逆元 这个前置知识~~

用户头像
我若为昆仑   2019-04-12 19:35         踩      回复

我知道，但是评论区写代码的时候，打出**是字母加粗的意思，就用^代替了