SRM502 Div2 Hard

1000
DPする。
DP[何匹目まで見た mod 2][数字の合計 mod N][何匹が逃げた];

この実装だと、実行時間がそうとうギリギリ。
テーブルの半分を毎回初期化するのはもちろん、剰余算を少し余計にやっただけでアウト。
剰余算は四則演算よりステップ数がかかるらしいことは知ってたけど、ツラい。

view plainprint?

1. class TheCowDivTwo {  
2. public:  
3.   int find(int N, int K)  
4.   {  
5.     const lli mod = 1000000007;  
6.   
7.     const int SUM = 1000 + 1;  
8.     const int COW = 50;  
9.   
10.     lli dp[2][SUM][COW];  
11.     fill(&dp[0][0][0], &dp[2 - 1][SUM - 1][COW], 0);  
12.     dp[0][0][0] = 1;  
13.   
14.     for (int i = 0; i < N; ++i) {  
15.       int a = i % 2;  
16.       int b = (i + 1) % 2;  
17.       for (int sum = 0; sum < N; ++sum) {  
18.         for (int cow = 0; cow <= K; ++cow) {  
19.           dp[b][sum][cow] = dp[a][sum][cow];  
20.           if (cow) {  
21.             dp[b][sum][cow] += dp[a][(sum - i + N) % N][cow - 1];  
22.           }  
23.           dp[b][sum][cow] %= mod;  
24.         }  
25.       }  
26.     }  
27.   
28.     return dp[N%2][0][K];  
29.   }  
30. };  

class TheCowDivTwo {
public:
  int find(int N, int K)
  {
    const lli mod = 1000000007;

    const int SUM = 1000 + 1;
    const int COW = 50;

    lli dp[2][SUM][COW];
    fill(&dp[0][0][0], &dp[2 - 1][SUM - 1][COW], 0);
    dp[0][0][0] = 1;

    for (int i = 0; i < N; ++i) {
      int a = i % 2;
      int b = (i + 1) % 2;
      for (int sum = 0; sum < N; ++sum) {
        for (int cow = 0; cow <= K; ++cow) {
          dp[b][sum][cow] = dp[a][sum][cow];
          if (cow) {
            dp[b][sum][cow] += dp[a][(sum - i + N) % N][cow - 1];
          }
          dp[b][sum][cow] %= mod;
        }
      }
    }

    return dp[N%2][0][K];
  }
};