Submission #1005396

---

Source Code Expand

#include "bits/stdc++.h"
using namespace std;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
static const int INF = 0x3f3f3f3f; static const long long INFL = 0x3f3f3f3f3f3f3f3fLL;
typedef vector<int> vi; typedef pair<int, int> pii; typedef vector<pair<int, int> > vpii; typedef long long ll;
template<typename T, typename U> static void amin(T &x, U y) { if(y < x) x = y; }
template<typename T, typename U> static void amax(T &x, U y) { if(x < y) x = y; }


template<int MOD>
struct ModInt {
	static const int Mod = MOD;
	unsigned x;
	ModInt() : x(0) {}
	ModInt(signed sig) { int sigt = sig % MOD; if(sigt < 0) sigt += MOD; x = sigt; }
	ModInt(signed long long sig) { int sigt = sig % MOD; if(sigt < 0) sigt += MOD; x = sigt; }
	int get() const { return (int)x; }

	ModInt &operator+=(ModInt that) { if((x += that.x) >= MOD) x -= MOD; return *this; }
	ModInt &operator-=(ModInt that) { if((x += MOD - that.x) >= MOD) x -= MOD; return *this; }
	ModInt &operator*=(ModInt that) { x = (unsigned long long)x * that.x % MOD; return *this; }

	ModInt operator+(ModInt that) const { return ModInt(*this) += that; }
	ModInt operator-(ModInt that) const { return ModInt(*this) -= that; }
	ModInt operator*(ModInt that) const { return ModInt(*this) *= that; }
};
typedef ModInt<1000000007> mint;
template<int... Sizes>
struct MultidimensionalIndex;
template<>
struct MultidimensionalIndex<> {
	MultidimensionalIndex() {}
	int getTotalSize() const { return 1; }
	int getIndexAcc(int acc) const { return acc; }
};
template<int Head, int... Tail>
struct MultidimensionalIndex<Head, Tail...> : MultidimensionalIndex<Tail...> {
	using Base = MultidimensionalIndex<Tail...>;
	enum { size = Head };
	template<typename... TailT>
	MultidimensionalIndex(TailT... tail) : Base(tail...) {}
	int getTotalSize() const { return size * Base::getTotalSize(); }
	template<typename... TailT>
	int getIndexAcc(int acc, int head, TailT... tail) const { return Base::getIndexAcc(acc * size + head, tail...); }
};
template<int... Tail>
struct MultidimensionalIndex<0, Tail...> : MultidimensionalIndex<Tail...> {
	using Base = MultidimensionalIndex<Tail...>;
	const int size;
	template<typename... TailT>
	MultidimensionalIndex(int head, TailT... tail) : size(head), MultidimensionalIndex<Tail...>(tail...) {}
	int getTotalSize() const { return size * Base::getTotalSize(); }
	template<typename... TailT>
	int getIndexAcc(int acc, int head, TailT... tail) const { return Base::getIndexAcc(acc * size + head, tail...); }
};

template<typename Val, int... Sizes>
struct DP : MultidimensionalIndex<Sizes...> {
	using Base = MultidimensionalIndex<Sizes...>;
	std::vector<Val> dp;
	template<typename... SizesT>
	DP(SizesT... sizes) : Base(sizes...) {}
	void init(Val val) { dp.assign(Base::getTotalSize(), val); }
	void init() { dp.assign(Base::getTotalSize(), Val()); }
	template<typename... SizesT>
	Val &operator()(SizesT... indices) { return dp[Base::getIndexAcc(0, indices...)]; }
	template<typename... SizesT>
	Val operator()(SizesT... indices) const { return dp[Base::getIndexAcc(0, indices...)]; }
	void swap(DP &that) { dp.swap(that.dp); }
};

typedef bitset<300> BitSet;
int getRank(vector<BitSet> v, int B) {
	int n = (int)v.size(), rank = 0, used = 0;
	for(int j = B - 1; j >= 0; j --) {
		int i = used;
		while(i < n && !v[i][j]) i ++;
		if(i < n) {
			BitSet x = v[i];
			swap(v[i], v[used ++]);
			++ rank;
			for(i = used; i < n; i ++)
				if(v[i][j])
					v[i] ^= x;
		}
	}
	return rank;
}

int main() {
	int N;
	while(~scanf("%d", &N)) {
		vector<BitSet> C(N);
		for(int i = 0; i < N; ++ i) {
			BitSet row;
			rep(j, N) {
				int c;
				scanf("%d", &c);
				row[j] = c != 0;
			}
			C[i] = row;
		}
		int rank = getRank(C, N);
		vector<mint> two(N * N + 1);
		two[0] = 1;
		rer(n, 1, N * N)
			two[n] = two[n - 1] + two[n - 1];
		DP<mint, 0, 0> dp(N + 1, rank + 1), ndp = dp;
		ndp.init();
		ndp(0, 0) = 1;
		rep(i, N) {
			dp.swap(ndp);
			ndp.init();
			rer(j, 0, i) rer(k, 0, min(j, rank)) {
				mint x = dp(j, k);
				if(x.x == 0) continue;
				ndp(j, k) += x * two[j];
				ndp(j + 1, k) += x * (two[N] - two[j + rank - k]);
				if(k < rank)
					ndp(j + 1, k + 1) += x * (two[j + rank - k] - two[j]);
			}
		}
		mint ans;
		rer(j, rank, N)
			ans += ndp(j, rank) * two[N * (N - j)];
		printf("%d\n", ans.get());
	}
	return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:100:20: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &c);
                    ^

Judge Result