TopCoder SRM536 Div1Hard

問題

係数が mod 2 の世界で、N (高々 49)次の多項式の M (高々 10¹⁶) 乗の K 乗の係数を求めよ。

解法

まず、多項式の M 乗は結構大変なことになりうるので、大変なことにならない状態を考える。
多項式の 2 乗を考えると、mod 2 の世界では各項の指数が 2 倍になったものに変化することがわかる。そこで、M を 2 進展開することにより、O(log M) 個の、項が高々 N 個の多項式の積として表せることになる。
その多項式の積を、次数が低い順に並べる。K 乗の項の係数を求めるためには、Σ(最初の多項式の i 乗の係数) * (それ以外の多項式の積の K-i 乗の係数) を求めればいい。
そのために set を用いて、求めるべき次数を管理する。まず set には K が入っている。最初の多項式から順に、「set の各要素 i について、(i - 各項の次数) としたものを次の set に追加する」ということを行う。この set は、2 個同じものを入れるとどちらも消えるようにしておく。これを最後の多項式まで行い、set に 0 が入っているか確認すればよい。
しかし、これでは単純に展開しても同じことである。だが、各多項式ごとに、各項の次数は、2 の冪の倍数になっていることを使うと、最初の set の追加のときに、次以降の多項式ではどう頑張っても絶対に 0 にできないようなものを排除することができ、これを行うと非常に速くなり、解くことができる。
（これだけで速くなる理由は、「すべて、ある 2 の冪の倍数」になっているなら情報は下位ビットに共通する 0 の数だけ失われていることになり、多項式を 1 個進めるごとに、「set の中にある次数」の差の情報が 1 ビット以上失われていき、差は高々 N しか拡大しないため、set の中身の差は高々 2N に抑えられることからわかる）
下の実装では、進めるごとに set の中身を 2 で割っている。

コード

#include<vector>
#include<algorithm>
#include<set>
using namespace std;
typedef long long i64;

class BinaryPolynomialDivOne
{
public:
	int findCoefficient(vector<int> A, i64 M, i64 K)
	{
		set<i64> prev, now;
		prev.insert(K);
		for(int i=0;i<60;i++){
			//succ
			if(M & (1LL << (i64)i)){
				for(set<i64>::iterator iter=prev.begin(); iter != prev.end(); iter++){
					for(int j=0;j<A.size();j++) if(A[j]){
						i64 nex = *iter - j;
						if(nex<0) continue;
						if(now.count(nex)==1){
							now.erase(nex);
						} else now.insert(nex);
					}
				}
				prev.swap(now);
				now.clear();
			}
			//right shift
			for(set<i64>::iterator iter=prev.begin(); iter != prev.end(); iter++){
				if(*iter%2==0) now.insert(*iter / 2);
			}
			prev.swap(now);
			now.clear();
		}
		
		return prev.count(0);
	} 
};