Codeforce #566 A B C(模拟) E(矩阵快速幂+欧拉降幂)

#include <bits/stdc++.h>
#define ll long long 
using namespace std;
const int maxn = 200005;
int main()
{
	int n;
	cin>>n;
	if(n%2==0){
		n/=2;
		cout<<(1<<n)<<endl;
	}else {
		cout<<0<<endl;
	}
	return 0;
}

//B
#include <bits/stdc++.h>
#define ll long long 
using namespace std;
char s[505][505];
int main()
{
	int n,m,dian = 0;
	cin>>n>>m;
	for(int i=0;i<n;i++){
		cin>>s[i];
		for(int j=0;j<m;j++){
			if(s[i][j]=='*')dian++;
		}
	}	
	int cent = 0,ni,nj,flag;
	for(int i=0;i<n;i++){
		
		for(int j=0;j<m;j++){
			flag = 1;
			if(s[i][j]=='*'); else flag = 0;
			if(i-1>=0&&s[i-1][j]=='*'); else flag = 0;
			if(j-1>=0&&s[i][j-1]=='*');	else flag = 0;
			if(j+1<m&&s[i][j+1]=='*'); else flag = 0;
			if(i+1<n&&s[i+1][j]=='*'); else flag = 0;
			if(flag){
				cent++;
				ni = i;
				nj = j;
			}
		}
		
	}
	if(cent!=1){
		printf("NO\n");
	}else {
		int tpi = ni,tpj = nj;
		while(tpi>=0&&s[tpi][tpj]=='*'){
			dian--;		tpi--;	
		}
		tpi = ni+1; tpj = nj;
		while(tpi<n&&s[tpi][tpj]=='*'){
			dian--;		tpi++;
		}
		tpi = ni;	tpj = nj - 1;
		while(tpj>=0&&s[tpi][tpj]=='*'){
			dian--;		tpj--;
		}
		tpi = ni;	tpj = nj + 1;
		while(tpj<m&&s[tpi][tpj]=='*'){
			dian--;		tpj++; 
		}
		if(dian==0){
			printf("YES\n");
		}else printf("NO\n");
	}
	return 0;
}

//C
#include <bits/stdc++.h>
#define ll long long 
using namespace std;
int n;
struct Node{
	string s;
	int num;
	char last;
}node[100005];
int cmp(Node a,Node b){
	if(a.num==b.num){
		return a.last<b.last;
	}else {
		return a.num<b.num;
	}
}
vector<pair<int,int> > pa1,pa2;
int main()
{
	string s;
	int num,size;
	char last;
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>s; num = 0; size = s.size();
		for(int i=0;i<size;i++){
				if(s[i]=='a'||s[i]=='e'||s[i]=='i'||s[i]=='o'||s[i]=='u'){
					num++;	last = s[i];
				}
		} 
		node[i].num = num,node[i].last = last,node[i].s = s;
	}
	sort(node,node+n,cmp);
	int ls=-1;
	int cnt = 1,pos = 0;
	while(pos<n){
		if(node[pos].num==node[pos+1].num&&node[pos].last==node[pos+1].last){
			pa1.push_back(make_pair(pos,pos+1));
			pos+=2;
		}else if(cnt!=node[pos].num){
			ls = pos;
			cnt = node[pos].num;
			pos++;
		}else if(ls==-1){
			ls = pos;
			cnt = node[pos].num;
			pos++;
		}else {
			pa2.push_back(make_pair(pos,ls));
			ls = -1;
			pos++;	
		}
	}	
	int ans,s1=pa1.size(),s2=pa2.size();	
	ans = min(s1,s2) + max(0,(s1-s2)/2);
	cout<<ans<<endl;
	for(int i=0;i<min(s1,s2);i++){
		cout<<node[pa2[i].first].s<<" "<<node[pa1[i].first].s<<endl;
		cout<<node[pa2[i].second].s<<" "<<node[pa1[i].second].s<<endl;
	}
	if(s1>s2){
			for(int i=min(s1,s2);i+1<s1;i+=2){
			cout<<node[pa1[i+1].first].s<<" "<<node[pa1[i].first].s<<endl;
			cout<<node[pa1[i+1].second].s<<" "<<node[pa1[i].second].s<<endl;
		}
	}
	return 0;
}

//E
#include <iostream>
#include <cstdio>
#include <cstring>
#define ll long long 
using namespace std;
struct Mat{
	ll m[101][101];
};
const ll mod = 1000000007;
int n;
Mat a;
Mat g,cx; 
Mat mul(Mat x,Mat y,ll mo,int bound){
	Mat cc;
	for(int i=1;i<=bound;i++){
		for(int j=1;j<=bound;j++){
			cc.m[i][j] = 0;	
			for(int k=1;k<=bound;k++){
				cc.m[i][j] = (cc.m[i][j]+ x.m[i][k]*y.m[k][j]%mo)%mo;
			}
		}
	}
	return cc;
}
Mat pow(Mat x,ll y,ll mo,int bound){
	Mat ans;
	for(int i=1;i<=bound;i++)
		for(int j=1;j<=bound;j++)
		if(i==j)ans.m[i][i] = 1;
		else ans.m[i][j] = 0;
	while(y){
		if(y&1)ans = mul(ans,x,mo,bound);
		x = mul(x,x,mo,bound);
		y>>=1;
	}
	return ans;
}
ll quick(ll x,ll y){
	ll re = 1;
	while(y){
		if(y&1)re = re*x%mod;
		x=x*x%mod;
		y>>=1; 
	}
	return re;
}
int main(){	
	ll n,f1,f2,f3,c;
	cin>>n>>f1>>f2>>f3>>c;
	g.m[1][1] = 1;	g.m[1][2] = 1;	g.m[1][3] = 1;
	g.m[2][1] = 1;	g.m[2][2] = 0;	g.m[2][3] = 0;
	g.m[3][1] = 0;	g.m[3][2] = 1;	g.m[3][3] = 0;
	cx.m[1][1] = 1;	cx.m[1][2] = 1;	cx.m[1][3] = 1;	cx.m[1][4] = 1;	cx.m[1][5] = 0;
	cx.m[2][1] = 1;	cx.m[2][2] = 0;	cx.m[2][3] = 0;	cx.m[2][4] = 0;	cx.m[2][5] = 0;
	cx.m[3][1] = 0;	cx.m[3][2] = 1;	cx.m[3][3] = 0;	cx.m[3][4] = 0;	cx.m[3][5] = 0;
	cx.m[4][1] = 0;	cx.m[4][2] = 0;	cx.m[4][3] = 0;	cx.m[4][4] = 1;	cx.m[4][5] = 2;
	cx.m[5][1] = 0;	cx.m[5][2] = 0;	cx.m[5][3] = 0;	cx.m[5][4] = 0;	cx.m[5][5] = 1;
	ll	exp_f1,exp_f2,exp_f3,num_c;

	g =  pow(g,n-3,1e9+6,3);

	exp_f1 = g.m[1][3];
	exp_f2 = g.m[1][2];
	exp_f3 = g.m[1][1];

	
	cx = pow(cx,n-3,1e9+6,5);
	num_c = (cx.m[1][4]*2 + cx.m[1][5])%(mod-1);

	ll ans=0;
	ans=quick(f1,exp_f1)%mod;
	ans=ans*(quick(f2,exp_f2)%mod)%mod;
	ans=ans*(quick(f3,exp_f3)%mod)%mod;
	ans=ans*(quick(c,num_c)%mod)%mod;
	cout<<ans<<endl;
	return 0;
}
/*
5 1 2 5 3

*/