Submission #44675506

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

#define x first
#define y second
#define fro(i, x, y) for(int i = (x);i <= (y);i++)
#define pre(i, x, y) for(int i = (x);i >= (y);i--)

typedef long long ll;
typedef __int128 lll;
typedef unsigned int uint;
typedef pair<int, int> PII;
typedef unsigned long long ull;

const int N = 1010;
const int mod = 1e9 + 7;

ll n, m, k;
char ch[N][N];

struct Mat
{
    ll a[2][2];
    inline Mat()
    {
        a[0][0] = a[1][1] = 1;
        a[0][1] = a[1][0] = 0;
    }
    inline Mat operator*(const Mat b)
    {
        Mat c;
        c.a[0][0] = (a[0][0] * b.a[0][0] + a[0][1] * b.a[1][0]) % mod;
        c.a[0][1] = (a[0][0] * b.a[0][1] + a[0][1] * b.a[1][1]) % mod;
        c.a[1][0] = (a[1][0] * b.a[0][0] + a[1][1] * b.a[1][0]) % mod;
        c.a[1][1] = (a[1][0] * b.a[0][1] + a[1][1] * b.a[1][1]) % mod;
        return c;
    }
};

inline Mat power(Mat x, ll y)
{
    Mat res;
    while(y)
    {
        if(y & 1) res = res * x;
        x = x * x, y /= 2;
    }
    return res;
}

inline ll power(ll x, ll y)
{
    ll res = 1;
    while(y)
    {
        if(y & 1) res = res * x % mod;
        x = x * x % mod, y /= 2;
    }
    return res;
}

signed main()
{
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> n >> m >> k;
    if(!k) cout << 1 << endl, exit(0);
    fro(i, 1, n) cin >> (ch[i] + 1);
    int l1, l2, s1, s2, d;
    l1 = l2 = s1 = s2 = d = 0;
    fro(i, 1, n) fro(j, 1, m) d += (ch[i][j] == '#');
    fro(i, 1, n) fro(j, 1, m - 1)
        l1 += (ch[i][j] == '#' && ch[i][j] == ch[i][j + 1]);
    fro(i, 1, n - 1) fro(j, 1, m)
        l2 += (ch[i][j] == '#' && ch[i][j] == ch[i + 1][j]);
    fro(i, 1, n) s1 += (ch[i][1] == '#' && ch[i][1] == ch[i][m]);
    fro(i, 1, m) s2 += (ch[1][i] == '#' && ch[1][i] == ch[n][i]);
    if(s1 && s2) cout << "1\n";
    else if(!s1 && !s2) cout << power(d, k - 1) << "\n";
    else
    {
        Mat a; ll s = 0;
        a.a[0][0] = d;
        if(s1) a.a[1][1] = s1, a.a[0][1] = l1;
        if(s2) a.a[1][1] = s2, a.a[0][1] = l2;
        a = power(a, k - 1);
        cout << (a.a[0][0] - a.a[0][1] + mod) % mod;
    }
    return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:81:19: warning: unused variable ‘s’ [-Wunused-variable]
   81 |         Mat a; ll s = 0;
      |                   ^

Judge Result