Submission #1299141

#	Time	Username	Problem	Language	Result	Execution time	Memory
1299141		PieArmy	Chess Rush (CEOI20_chessrush)	C++20	36 / 100	2096 ms	24128 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;
pair<int,int>dp[123][2],dp2[123][2];

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 2\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=sum(cev,1);
				}
				else if(tar.fr-tar.sc<=m-2){
					cev=sum(cev,2);
				}
				else{
					cev=sum(cev,3);
				}
			}
			if(a!=1&&a!=m){
				a=m-a+1;
				b=m-b+1;
				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=sum(cev,1);
				}
				else if(tar.fr-tar.sc<=m-2){
					cev=sum(cev,2);
				}
				else{
					cev=sum(cev,3);
				}
			}
			cout<<cev<<" ";
			for(int j=1;j<=m;j++){
				dp[j][0]=dp[j][1]={1e9,0};
			}
			dp[a][0]=dp[a][1]={1,1};
			for(int i=2;i<=n;i++){
				for(int j=1;j<=m;j++){
					dp2[j][0]=dp2[j][1]={1e9,0};
				}
				for(int j=1;j<=m;j++){
					for(int l=0;l<2;l++){
						if(l){
							if(j!=m){
								pair<int,int>&p=dp2[j+1][1];
								pair<int,int>cur=dp[j][l];
								if(p.fr>=cur.fr){
									if(p.fr==cur.fr)p.sc=sum(p.sc,cur.sc);
									else p=cur;
								}
							}
							if(j!=1){
								pair<int,int>&p=dp2[j-1][0];
								pair<int,int>cur=dp[j][l];
								cur.fr++;
								if(p.fr>=cur.fr){
									if(p.fr==cur.fr)p.sc=sum(p.sc,cur.sc);
									else p=cur;
								}
							}
						}
						else{
							if(j!=m){
								pair<int,int>&p=dp2[j+1][1];
								pair<int,int>cur=dp[j][l];
								cur.fr++;
								if(p.fr>=cur.fr){
									if(p.fr==cur.fr)p.sc=sum(p.sc,cur.sc);
									else p=cur;
								}
							}
							if(j!=1){
								pair<int,int>&p=dp2[j-1][0];
								pair<int,int>cur=dp[j][l];
								if(p.fr>=cur.fr){
									if(p.fr==cur.fr)p.sc=sum(p.sc,cur.sc);
									else p=cur;
								}
							}
						}
					}
				}
				for(int j=1;j<=m;j++){
					dp[j][0]=dp2[j][0];
					dp[j][1]=dp2[j][1];
				}
			}
			pair<int,int>res1=dp[b][0],res2=dp[b][1];
			if(res1.fr==res2.fr){
				cout<<sum(res1.sc,res2.sc)<<endl;
				continue;
			}
			if(res1.fr<res2.fr){
				cout<<res1.sc<<endl;
				continue;
			}
			else cout<<res2.sc<<endl;
		}
		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