SRM532第1组第2题：详细解析与优化策略

#include
using namespace std;

const int MOD &＃61; 1000000007;

typedef long long int64;

int64 f[35][1 <<9][35][9];

class DengklekBuildingRoads
{
public:
int numWays(int N, int M, int K)
{
memset(f, 0, sizeof(f));
for(int k &＃61; 0; k <&＃61; K; k&＃43;&＃43;)
f[0][0][0][k] &＃61; 1;
//f[0][0][0][0] &＃61; 1;

for(int i &＃61; 1; i {
for(int j &＃61; 0; j <&＃61; M; j&＃43;&＃43;)
{
// k &＃61; 0
for(int mask &＃61; 0; mask <(1 <<(K &＃43; 1)); mask&＃43;&＃43;)
{
if(!(mask & 1)) f[i][mask][j][0] &＃61; f[i - 1][mask / 2][j][K];
}
// k > 0
for(int k &＃61; 1; k <&＃61; K; k&＃43;&＃43;)
{
for(int mask &＃61; 0; mask <(1 <<(K &＃43; 1)); mask&＃43;&＃43;)
{
f[i][mask][j][k] &＃61; f[i][mask][j][k - 1];
if(k > i) continue;
f[i][mask][j][k] &＃43;&＃61; f[i][mask ^ 1 ^ (1 <1][k];
f[i][mask][j][k] %&＃61; MOD;
}
}
}
}
return f[N - 1][0][M][K];
}
};