TopCoder SRM 502 Div2 Hard TheCowDivTwo

また妙に簡単な回。
http://community.topcoder.com/stat?c=problem_statement&pm=11352

問題

数N,Kが与えられる。
0～(N-1)のN個の数のうちK個を選択し、その総和がNの倍数になる選択の仕方は何通りあるか。

解法

状態として[現在の処理番号][選択済みの総和 % N][残り選択数]を持って普通にDPするだけ。
O(N^2*K)だがNもKも大きくないので十分。

ll mo=1000000007;
ll dpdp[2][1001][50];
class TheCowDivTwo {
	public:
	int find(int N, int K) {
		int i,x,y;
		ZERO(dpdp);
		dpdp[0][0][K]=1;
		
		FOR(i,N) {
			int cur=i%2,tar=cur^1;
			memmove(dpdp[tar],dpdp[cur],sizeof(dpdp[tar]));
			FOR(x,N) for(y=1;y<=K;y++) {
				dpdp[tar][(x+i)%N][y-1] += dpdp[cur][x][y];
				dpdp[tar][(x+i)%N][y-1] %= mo;
			}
		}
		return dpdp[N%2][0][0];
		
	}
}

まとめ

Div2とはいえ簡単過ぎないか？
総和のmod Nを持つアイデアを問う問題？