组合数
从n个位置选s个胜利，其他位置任选两种状态
C(n,s)∗2n−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;
}
tql
请问ans2 = ksm(ans2, mod - 2);为什么要把mod-2传进去？
xp−2即x在模质数p条件下的逆元
老哥，这样写怎么纠错了哇，不是拟元的思想
#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; }不写注释看不懂啊- -
这里需要用到 逆元 这个前置知识~~
我知道，但是评论区写代码的时候，打出**是字母加粗的意思，就用^代替了