Submission #847663

---

Source Code Expand

/**
 *    author:  [itmo] enot.1.10
 *    created: 21.08.2016 15:33:51       
**/
#define __USE_MINGW_ANSI_STDIO 0
#include <bits/stdc++.h>

#define F first
#define S second
#define pb push_back
#define mp make_pair
#define forn(i, n) for(int i = 0 ; (i) < (n) ; ++i)
#define eprintf(...) fprintf(stderr, __VA_ARGS__),fflush(stderr)
#define sz(a) ((int)(a).size())
#define all(a) (a).begin(),a.end()
#define pw(x) (1LL<<(x))

using namespace std;

typedef long long ll;
typedef double dbl;
typedef vector<int> vi;
typedef pair<int, int> pi;

const int inf = 1.01e9;
const dbl eps = 1e-9;

/* --- main part --- */

const int T = 3;
const int mod = 1e9 + 7;

ll tmp[T][T];
ll A[T][T], R[T][T];

void multRR()
{
    memset(tmp, 0, sizeof tmp);
    forn(i, T) forn(j, T) forn(k, T) tmp[i][j] = (tmp[i][j] + R[i][k] * (ll)R[k][j]) % mod;
    forn(i, T) forn(j, T) R[i][j] = tmp[i][j];
}

void multRA()
{
    memset(tmp, 0, sizeof tmp);
    forn(i, T) forn(j, T) forn(k, T) tmp[i][j] = (tmp[i][j] + R[i][k] * (ll)A[k][j]) % mod;
    forn(i, T) forn(j, T) R[i][j] = tmp[i][j];
}

int mpow(int a, ll b)
{
    int res = 1;
    while (b)
    {
        if (b & 1) res = (res * (ll)a) % mod;
        a = (a * (ll)a) % mod;
        b >>= 1;
    }
    return res;
}



const int N = 1010;

char s[N][N];


int main()
{
    #ifdef home
        assert(freopen("1.in", "r", stdin));
        assert(freopen("1.out", "w", stdout));
    #endif
    int n, m;
    scanf("%d%d", &n, &m);
    ll k;
    scanf("%lld", &k);
    if (k <= 1) return 0 * printf("1\n");
    forn(i, n) scanf("%s", s[i]);
    int V = 0, H = 0;
    forn(i, n) if (s[i][0] == '#' && s[i][m - 1] == '#') H++;
    forn(i, m) if (s[0][i] == '#' && s[n - 1][i] == '#') V++;
    if (H == 0 && V == 0)
    {
        int res = 0;
        forn(i, n) forn(j, m) res += s[i][j] == '#';
        res = mpow(res, k - 1);
        printf("%d\n", res);
        return 0;
    }
    if (H > 0 && V > 0) return 0 * printf("1\n");

    if (H == 0 && V > 0)
    {
        int mx = max(n, m);
        forn(i, mx) forn(j, mx) if (i < j) swap(s[i][j], s[j][i]);
        swap(n, m);
        swap(H, V);
    }
    ll cnt = 0;
    ll pairs = 0;
    ll sides = H;
    forn(i, n) forn(j, m) cnt += s[i][j] == '#';
    forn(i, n) forn(j, m - 1) if (s[i][j] == '#' && s[i][j + 1] == '#') pairs++;


    A[0][0] = cnt;
    A[1][1] = cnt;
    A[1][2] = pairs;
    A[2][2] = sides;

    forn(i, T) R[i][i] = 1;

    ll b = k - 2;
    for (int i = 60; i >= 0; --i)
    {
        multRR();
        if (b & pw(i)) multRA();
    }

    ll cnt2 = (cnt * (ll)R[0][0] + pairs * (ll)R[0][1] + sides * (ll)R[0][2]) % mod;
    ll pairs2 = (cnt * (ll)R[1][0] + pairs * (ll)R[1][1] + sides * (ll)R[1][2]) % mod;
    
    int res = (cnt2 - pairs2 + mod) % mod;

    printf("%d\n", res);

    
    #ifdef home
        eprintf("time = %d ms\n", (int)(clock() * 1000. / CLOCKS_PER_SEC));
    #endif
    return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:76:26: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &n, &m);
                          ^
./Main.cpp:78:22: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld", &k);
                      ^
./Main.cpp:80:33: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     forn(i, n) scanf("%s", s[i]);
                                 ^

Judge Result