Submission #71861

#	Time	Username	Problem	Language	Result	Execution time	Memory
71861		비타오백 (#119)	Cross on the Grid (FXCUP3_cross)	C++17	100 / 100	3 ms	628 KiB

cross

#include <bits/stdc++.h>
#define sz(x) ((int)x.size())
#define all(x) (x).begin(), (x).end()
using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector<int> VL;
typedef vector<VL> VVL;
const int MOD = 1e9 + 7;
VVL mul(VVL& a, VVL& b) {
	VVL c(12, VL(12));
	for(int i=0; i<12; i++) for(int j=0; j<12; j++)
		for(int k=0; k<12; k++) c[i][j] = (c[i][j] + 1ll * a[i][k] * b[k][j] % MOD) % MOD;
	return c;
}
VVL Pow(VVL a, int pw) {
	VVL b = a, r(12, VL(12));
	for(int i=0; i<12; i++) r[i][i] = 1;
	while(pw > 0) {
		if(pw & 1) r = mul(r, b);
		b = mul(b, b);
		pw >>= 1;
	}
	return r;
}
int in[12][12]={
	{1,1,1,1,0,0,0,0,0,0,0,0},
	{0,0,0,0,1,0,1,1,1,1,1,0},
	{0,0,0,0,0,1,0,1,1,1,1,1},
	{0,0,0,0,1,1,1,0,1,0,1,1},
	{1,0,0,0,0,0,0,0,0,0,0,0},
	{0,1,0,0,0,0,0,0,0,0,0,0},
	{0,0,1,0,0,0,0,0,0,0,0,0},
	{0,0,0,1,0,0,0,0,0,0,0,0},
	{0,0,0,0,1,0,0,0,0,0,0,0},
	{0,0,0,0,0,1,0,0,0,0,0,0},
	{0,0,0,0,0,0,1,0,0,0,0,0},
	{0,0,0,0,0,0,0,1,0,0,0,0}
};
int a[12]={1,1,1,1,1,0,0,0,1,0,0,0};
int main() {
	VVL init(12,VL(12));
	for(int i=0; i<12; i++) for(int j=0; j<12; j++) init[i][j]=in[i][j];
	int n;
	scanf("%d", &n);
	VVL mat = Pow(init, n-3);
	int res = 0;
	for(int i=0; i<4; i++) {
		int val = 0;
		for(int j=0; j<12; j++) val = (val + 1ll * mat[i][j] * a[j] % MOD) % MOD;
		res = (res + val) % MOD;
	}
	printf("%d", res);
	return 0;
}

Compilation message (stderr)

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

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