Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 87 Accepted Submission(s): 44
#include <iostream> #include <cstdio> #include <cstring> #include <string> #include <cmath> #include <vector> #include <queue> #include <map> #include <set> #include <stack> #include <algorithm> using namespace std; #define root 1,n,1 #define lson l,mid,rt<<1 #define rson mid+1,r,rt<<1|1 #define lr rt<<1 #define rr rt<<1|1 typedef long long LL; typedef pair<int,int>pii; #define X first #define Y second const int oo = 1e9+7; const double PI = acos(-1.0); const double eps = 1e-6 ; const int N = 105 ; const int mod = 1e9+7; LL dp[N][N] , f[N] , C[N][N]; int n , m ; void init() { f[0] = 1 ; for( int i = 1 ; i <= 50 ; ++i ) f[i] = f[i-1] * 2 ; for( int i = 0 ; i < N; ++i ){ C[i][0] = C[i][i] = 1 ; for( int j = 1 ; j < i ; ++j ){ C[i][j] = ( C[i-1][j] + C[i-1][j-1] ) % mod ; } } } void Run() { memset( dp , 0 , sizeof dp ); dp[0][0] = 1 ; for( int i = 0 ; i < n ; ++i ){ for( int j = 0 ; j <= m ; ++j ){ for( int k = 0 ; j + k <= m ; k++ ){ LL cnt = f[j]; if( !k ) cnt--; cnt %= mod ; dp[i+1][j+k] += ( dp[i][j] * cnt % mod * C[m-j][k] ) % mod; dp[i+1][j+k] %= mod ; } } } printf("%I64d\n",dp[n][m]); } int main() { #ifdef LOCAL freopen("in.txt","r",stdin); #endif // LOCAL init(); while( ~scanf("%d%d",&n,&m) ) Run(); }
HDU 5155 Harry And Magic Box( DP )
原文:http://www.cnblogs.com/hlmark/p/4200068.html