Submission #71937

#	Time	Username	Problem	Language	Result	Execution time	Memory
71937		블랙야크 (#119)	Cross on the Grid (FXCUP3_cross)	C++17	100 / 100	4 ms	820 KiB

cross

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <iostream>
#include <functional>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <bitset>

using namespace std;
typedef long long ll;
#define Fi first
#define Se second
#define pb(x) push_back(x)
#define szz(x) ((int)(x).size())
#define rep(i, n) for(int i=0;i<n;i++)
#define all(x) (x).begin(), (x).end()
typedef tuple<int, int, int> t3;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef long double ldouble;

const int MOD = 1e9 + 7;
const int L = 16;

struct mat {
	int p[L][L];
	mat operator*(mat A) {
		mat res;
		rep(a, L) rep(b, L) res.p[a][b] = 0;
		rep(a, L) rep(c, L) rep(b, L) if(p[a][c] && A.p[c][b]) res.p[a][b] = (res.p[a][b] + p[a][c] * (ll)A.p[c][b]) % MOD;
		return res;
	}
};

int chk(int x) {
	int a = x & 3, b = (x >> 2) & 3;
	if(a && b && abs(a - b) <= 1) return 0;
	return 1;
}

int main() {
	mat X, R;
	rep(i, L) rep(j, L) X.p[i][j] = 0;
	rep(i, L) rep(j, L) if(chk(i) && chk(j) && (i & 3) == ((j >> 2) & 3) && ((j & 3) == 0 || ((i >> 2) & 3) != (j & 3))) X.p[i][j] = 1;
	rep(i, L) rep(j, L) R.p[i][j] = (i == j ? 1 : 0);
	int N; scanf("%d", &N); N -= 2;
	while(N) {
		if(N & 1) R = R * X;
		X = X * X;
		N >>= 1;
	}
	ll ans = 0;
	rep(i, L) ans = (ans + R.p[0][i]) % MOD;
	printf("%lld\n", ans);
	return 0;
}

Compilation message (stderr)

cross.cpp: In function 'int main()':
cross.cpp:56:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  int N; scanf("%d", &N); N -= 2;
         ~~~~~^~~~~~~~~~

• Subtask 1: 22 / 22
• Subtask 2: 35 / 35
• Subtask 3: 43 / 43