L - Team Work

CF932E

#include<bits/stdc++.h>
using namespace std;

#define int long long 

const int mod = 1e9 + 7;

int ksm(int x,int y){
    int z = 1;
    while(y){
        if(y & 1) z = z * x % mod;
        y >>= 1;
        x = x * x % mod;
    }
    return z;
}

int n,k;
int s[5005][5005];

signed main(){
    scanf("%lld%lld",&n,&k);
    
    s[0][0] = 1;
    for(int i = 1; i <= k; ++ i)
    for(int j = 1; j <= k; ++ j)
    s[i][j] = (s[i - 1][j - 1] + s[i - 1][j] * j % mod ) % mod;
    
    int ans = 0;
    int bas1 = 1, bas2 = 1, bas3 = ksm(2,n), inv2 = ksm(2, mod - 2);
    //bas1 j! , bas2 C(n,j), bas3 2^(n-j)
    for(int j = 0; j <= k; ++ j){
       int t = s[k][j];
       t = t * bas1 % mod;
       t = t * bas2 % mod;
       t = t * bas3 % mod;
       ans = ans + t; ans %= mod;
        
       bas1 = bas1 * (j + 1) % mod;
       bas2 = bas2 * (n - j) % mod * ksm(j + 1, mod - 2) % mod;
       bas3 = bas3 * inv2 % mod;
    }
    
    printf("%lld\n",ans);
    
    
    return 0;
}

L - Team Work

原文：https://www.cnblogs.com/zzhzzh123/p/13347231.html