2 条题解
-
1
#include <cmath> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; const int N = 1e6 + 5, MX = 1e8 + 7; int n, m, f[N], orz = 1, mx = 1, A[N]; int qpow(int a, int b) { int res = 1; while (b) b & 1 ? res = 1ll * res * a % MX : 0, a = 1ll * a * a % MX, b >>= 1; return res; } int main() { int i; cin >> n >> m; for (i = 1; i <= n; i++) orz = orz * 2 % MX; orz = (orz - 1 + MX) % MX; A[0] = 1; for (i = 1; i <= m; i++) A[i] = 1ll * A[i - 1] * ((orz - i + 1 + MX) % MX) % MX, mx = 1ll * mx * i % MX; f[f[1] = 0] = 1; for (i = 2; i <= m; i++) f[i] = (A[i - 1] - f[i - 1] + MX - 1ll * f[i - 2] * (i - 1) % MX * (orz - i + 2 + MX) % MX + MX) % MX; cout << 1ll * f[m] * qpow(mx, MX - 2) % MX << endl; return 0; }
-
0
#include<cstdio> #define MAXN 999999 typedef long long ll; const int mod = 100000007; int n, m, invm, a[MAXN], f[MAXN]; ll ksm(ll a, int b){ ll res = 1; while(b){ if(b & 1) res = res * a % mod; a = a * a % mod; b >>= 1; } return res; } int main(){ scanf("%d%d", &n, &m); invm = 1; for(int i = 1; i <= m; i++) invm = (ll)invm * i % mod; invm = ksm(invm, mod - 2); int mxn = ksm(2, n); a[0] = 1; for(int i = 1; i <= m; i++ ) a[i] = (ll)a[i - 1] * (mxn - i) % mod; f[0] = 1; for(int i = 2; i <= m; i++ ) f[i] = a[i - 1] - f[i - 1] - (ll)f[i - 2] * (i - 1) % mod * (mxn - i + 1) % mod, f[i] = (f[i] % mod + mod) % mod; printf("%lld", (ll)f[m] * invm % mod); return 0; }
- 1
信息
- ID
- 2150
- 时间
- 1000ms
- 内存
- 128MiB
- 难度
- 7
- 标签
- 递交数
- 8
- 已通过
- 6
- 上传者