Submission #1355085

#	Time	Username	Problem	Language	Result	Execution time	Memory
1355085		sano	Chess Rush (CEOI20_chessrush)	C++20	28 / 100	2102 ms	259812 KiB

chessrush

#include <bits/stdc++.h>
#define P vector
#define F(i, n) for(l i = 0; i < n; i++)
#define l long long
using namespace std;
l r, c, q, x, y; 
P<P<l>> C(P<P<l>>& a, P<P<l>>&b){
    P<P<l>> v(c, P<l>(c, 0));
    F(i, c) F(j, c) F(k, c) v[i][j] = (v[i][j] + a[i][k] * b[k][j]) % 1000000007;
    return v;
}
signed main(){
    cin >> r >> c >> q; r--;
    P<P<l>> m[32];
    F(i, 32) m[i].assign(c, P<l>(c, 0));
    F(i, c) F(j, c) if(abs(i-j) <= 1) m[0][i][j] = 1;
    F(i, 31) m[i+1] = C(m[i], m[i]);
    P<P<l>> z(c, P<l>(c, 0));
    F(i, c) z[i][i] = 1;
    F(i, 32) if(r & (1<<i)) z = C(z, m[i]);
    F(i, q){
        char t; cin >> t >> x >> y; x--;y--;
        cout << r << ' ' << z[x][y] << '\n';
    }
}

• Subtask 1: 0 / 0
• Subtask 2: 0 / 8
• Subtask 3: 0 / 15
• Subtask 4: 0 / 22
• Subtask 5: 5 / 5
• Subtask 6: 8 / 8
• Subtask 7: 15 / 15
• Subtask 8: 0 / 20
• Subtask 9: 0 / 7