1 条题解

  • 1
    @ 2022-8-29 9:42:23
    #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;
    }
    
    • 1

    信息

    ID
    2339
    时间
    1000ms
    内存
    256MiB
    难度
    7
    标签
    (无)
    递交数
    15
    已通过
    9
    上传者