TopCoder SRM 679 Div1 Hard BagAndCards

えーそれでいいの…。
https://community.topcoder.com/stat?c=problem_statement&pm=14126

問題

N人が0～(M-1)の値を書かれたカードを持っている。
i番の人は値jを書かれたカードをC[i][j]枚持っている。

N人から２人x,y(x＜y)選んだ時、さらに両者が自身の手持ちのカードを１枚ずつ選ぶ。
カードの値の和は0～(2M-2)の何れかになるが、一部の値は良いとされる(どの値が良いかは事前に与えられる)。
良い値を得られるような２人のカードの選び方の組み合わせをA[x][y]とする。

各x,yにおけるA[x][y]%1000000007の値をそれぞれxorで計算した値を答えよ。

解法

x,yについてa+bが良い値であるものに対しC[x][a]*C[y][b]を足し合わせればA[x][y]が求まる。
ただしこのままではO(N^2*M^2)かかり間に合わないので、何か計算量を減らす必要がある。

本番、畳み込みだと思ってFFTしたら、計算過程で10^20を超えるケースがありlong doubleでも精度不足で失敗した。

xを色々変化させるとき、aに対していつも同じC[y][b]を何度も掛け合わせるのでこの無駄を省こう。
前処理で各y,aに対し以下の値を求めておく(O(N*M^2))。
S[y][a] := sum(a+bが良い値であるようなbに対するC[y][b])

すると、A[x][y]はsum(C[x][a]*S[y][a])となりbのループが不要になるので計算量をO(N^2*M)に落とせる。
合わせてO(NM(N+M))なので2秒でも間に合う。

ll cnt[501][501];
ll S[501][1201];
ll mo=1000000007;

class BagAndCards {
	public:
	int getHash(int n, int m, int X, int a, int b, int c, string isGood) {
		int i,j,x,y;
		ZERO(S);
		FOR(i,n) {
			FOR(j,m) {
				cnt[i][j]=X;
				X=(((ll)X*a+b)^c)%mo;
			}
			FOR(x,m) {
				FOR(y,m) if(isGood[x+y]=='Y') S[i][x]+=cnt[i][y];
				S[i][x]%=mo;
			}
		}
		
		ll tot=0;
		FOR(j,n) FOR(i,j) {
			ll ret=0;
			FOR(x,m) (ret+=cnt[i][x]*S[j][x])%=mo;
			tot^=ret;
		}
		return tot;
	}
}

まとめ

Hardという言葉に踊らされて無駄にFFTなんて試してしまった。
これMediumで出てたら450ptクラスでは…。