Submission #1299098

#	Time	Username	Problem	Language	Result	Execution time	Memory
1299098		PieArmy	Chess Rush (CEOI20_chessrush)	C++20	36 / 100	2095 ms	24136 KiB

chessrush

#include<bits/stdc++.h>
typedef long long ll;
#define pb push_back
#define fr first
#define sc second
#define endl '\n'
using namespace std;
#define mid ((left+right)>>1)

const int mod=1e9+7;

int sum(int x,int y){
	if(x+y<mod)return x+y;
	return x+y-mod;
}

int sub(int x,int y){
	if(y)y=mod-y;
	return sum(x,y);
}

int mul(ll x,ll y){
	return x*y%mod;
}

int fpow(int x,ll y){
	int res=1;
	while(y>0){
		if(y&1)res=mul(res,x);
		x=mul(x,x);
		y>>=1;
	}
	return res;
}

typedef vector<vector<int>> mat;

mat matmul(mat x,mat y){
	int n=x.size();
	mat res(n,vector<int>(n,0));
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			for(int l=0;l<n;l++){
				res[i][j]=sum(res[i][j],mul(x[i][l],y[l][j]));
			}
		}
	}
	return res;
}

mat matpow(mat x,ll y){
	int n=x.size();
	mat res(n,vector<int>(n,0));
	for(int i=0;i<n;i++){
		res[i][i]=1;
	}
	while(y>0){
		if(y&1)res=matmul(res,x);
		x=matmul(x,x);
		y>>=1;
	}
	return res;
}

int n,m,q;

int main(){
	ios_base::sync_with_stdio(23^23);cin.tie(NULL);
	cin>>n>>m>>q;
	mat ma(m,vector<int>(m,0));
	for(int i=0;i<m;i++){
		if(i)ma[i][i-1]=1;
		ma[i][i]=1;
		if(i<m-1)ma[i][i+1]=1;
	}
	ma=matpow(ma,n-1);
	while(q--){
		char c;cin>>c;
		int a,b;cin>>a>>b;
		if(c=='P'){
			if(a==b){
				cout<<n-1<<" 1\n";
			}
			else cout<<"0 0\n";
			continue;
		}
		if(c=='R'){
			if(a==b){
				cout<<"1 1\n";
			}
			else cout<<"2 2\n";
			continue;
		}
		if(c=='Q'){
			if(a==b){
				cout<<"1 1\n";
			}
			else if(min(a,b)==1&&max(a,b)==m&&n==m){
				cout<<"1 1\n";
			}
			else{
				cout<<"2 ";
				int cev=4;
				if(((n+b)&1)==((1+a)&1)){
					int x=a+1,y=1+1;
					while(x<=m){
						if(x+y==n+b){
							cev++;
							break;
						}
						x++;
						y++;
					}
					x=a-1;y=1+1;
					while(x>0){
						if(y-x==n-b){
							cev++;
							break;
						}
						x--;
						y++;
					}
				}
				if(n==m&&(a==1||a==m||b==1||b==m)){
					cev++;
				}
				cout<<cev<<endl;
			}
			continue;
		}
		if(c=='B'){
			if((n+b+1+a)&1){
				cout<<"0 0\n";
				continue;
			}
			if(n==m){
				if(min(a,b)==1&&max(a,b)==m){
					cout<<"1 1\n";
				}
				else{
					cout<<"2 1\n";
				}
				continue;
			}
			int h=2*m-2,w=m;
			int cev=0,cnt=0;
			{
				pair<int,int>loc={(h-(m-a))%h,a};
				pair<int,int>tar={(loc.fr+(n-1))%h,b};
				cev=sum(cev,((n-1-(1+m-a))/h)*2+!!(m-a));
				int spike=0;
				if(tar.fr==0&&tar.sc==m){
					cev+=0;
				}
				else if(tar.sc-tar.fr<=m){
					cev+=1;
				}
				else if(tar.fr+tar.sc>=m){
					cev+=2;
				}
				else{
					cev+=3;
				}
			}
		}
		if(c=='K'){
			cout<<n-1<<" "<<ma[a-1][b-1]<<endl;
		}
	}
}

• Subtask 1: 0 / 0
• Subtask 2: 8 / 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