[cqoi2012] local minima & Mike and foam

[CQOI2012] Local minima

The question ：
There is one $n$ That's ok $m$ The integer matrix of columns , among $1$ To $n\ast m$ Every integer between appears exactly once . If one grid is bigger than all the adjacent grids （ Adjacency refers to having a common edge or vertex ） All small , We say that this lattice is a local minimum .
Give the positions of all local minima , Your task is to judge how many possible matrices there are .
$(n<=4,m<=7)$

Ideas ：
For the scheme of determining the minimum point , Can pass $dp$ To solve ,$dp[i][j]$, Represents the current enumeration to the number , Which minimum points are assigned , Satisfy the definition of minimum , That is, the point around the minimum must be assigned a value greater than that after the minimum point （ Enumerating the number assignment from small to large ）, Follow this idea to transfer .
Satisfying these points is the minimum , But other points cannot be satisfied, which is not a minimum , Solve with tolerance and exclusion , Consider the scheme of enumerating all minimum points , Then do it once $dp$ that will do ;
When enumerating the point removal schemes , You can prune with two minimum points that are not adjacent , There are not many plans ;
Code ：

#include<bits/stdc++.h>
#include<unordered_map>
using namespace std;
#define ll long long 
#define mp make_pair
const ll mod=12345678;

int n,m;
char s[5][10];
ll ans=0;
vector<pair<int,int> >v;
pair<int,int>st[30];
int top=0;
int d[][2]={
    1,0,-1,0,0,1,0,-1,1,1,1,-1,-1,1,-1,-1};
ll dp[30][270];
int cnt[270];
int mpp[5][10];
ll solve(){
    
	memset(dp,0,sizeof(dp));
	memset(cnt,0,sizeof cnt);
	dp[0][(1<<top)-1]=1;
	for(int i=0;i<(1<<top);i++){
    
		memset(mpp,0,sizeof mpp);
		for(int j=0;j<top;j++){
    
			mpp[st[j+1].first][st[j+1].second]=1;
			if((1<<j)&i){
    
				for(int k=0;k<8;k++){
    
					int nx=st[j+1].first+d[k][0];
					int ny=st[j+1].second+d[k][1];
					if(nx<1||nx>n||ny<1||ny>m)continue;
					mpp[nx][ny]=1;
				}
			}
		}
		for(int j=1;j<=n;j++){
    
			for(int k=1;k<=m;k++){
    
				if(mpp[j][k]==0)cnt[i]++;
			}
		}
	}
	for(int i=0;i<n*m;i++){
    
		for(int j=0;j<(1<<top);j++){
    
			if(dp[i][j]==0)continue;
			int res=cnt[j]-i;
			for(int k=0;k<top;k++){
    
				if((1<<k)&j){
    
					dp[i+1][j^(1<<k)]+=dp[i][j];
					dp[i+1][j^(1<<k)]%=mod;
				}else res++;
			}
			dp[i+1][j]+=dp[i][j]*res%mod;
			dp[i+1][j]%=mod;
		}
	}
	return dp[n*m][0];
}
void dfs(int x,int cnt){
    
	if(x==v.size()){
    
		if(cnt%2==1)ans-=solve();
		else ans+=solve(); 
		ans=(ans+mod)%mod;
		return ;
	}
	dfs(x+1,cnt);
	int f=1;
	for(int i=0;i<8;i++){
    
		int nx=v[x].first+d[i][0];
		int ny=v[x].second+d[i][1];
		if(nx<1||nx>n||ny<1||ny>m)continue;
		if(s[nx][ny]=='X')f=0;
	}
	if(f){
    
		s[v[x].first][v[x].second]='X';
		top++;
		st[top]=mp(v[x].first,v[x].second);
		dfs(x+1,cnt+1);
		top--;
		s[v[x].first][v[x].second]='.';
	}
}
int main(){
    
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)scanf("%s",s[i]+1);
	for(int i=1;i<=n;i++){
    
		for (int j=1;j<=m;j++){
    
			if(s[i][j]=='X'){
    
				top++;st[top]=mp(i,j);
			}else {
    
				int f=1;
				for(int k=0;k<8;k++){
    
					int nx=i+d[k][0];
					int ny=j+d[k][1];
					if(nx<1||nx>n||ny<1||ny>m)continue;
					if(s[nx][ny]=='X')f=0;
				}
				if(f)v.push_back(mp(i,j));
			}
		}
	}
	dfs(0,0);
	printf("%lld\n",ans);
	return 0;
}

Mike and Foam

The question ：
$Mike$ yes $Rico$ The bartender in the bar . stay $Rico$ Bar , They put beer glasses on a special shelf . stay $Rico$ Bar , Yes $n$ Kind of beer number from $1$ To $n$. The first $i$ A bottle of beer has $a_i$ Ml of foam .
$Maxim$ yes $Mike$ Boss . Today he let $Mike$ answer $q$ A query . At first the shelf was empty . In each operation ,$Maxim$ Give him a number $X$. If the number is $X$ Our beer is already on the shelf , that $Mike$ It should be removed from the shelf , Otherwise he should put it on the shelf .

After each inquiry ,$Mike$ He should be told the score of shelf . They think that the score of the shelf is satisfied $i<j$ also $gcd(a_i,a_j)=1$ The number of $(i,j)$ The number of .
$n,q<=2e5,a_i<=5e5$

Ideas ：
Two numbers are coprime == Two numbers do not have the same prime factor ;
It's not hard to find out $a_i<=5e5$, signify $a_i$ The different qualitative factors of will not exceed 7 individual ;
Then, according to the prime factor, we can get the number of numbers that are coprime with the current number ;
Preprocess the prime factor of each number , Reuse $unordered$_$map$ Save each content and exclusion item .

Code ：

#include<bits/stdc++.h>
#include<unordered_map>
using namespace std;
#define ll long long 

unordered_map<ll,int>mp;
const ll mod=1e9+7;
int n,m;
struct node{
    
	ll h;
	int sig;
};
vector<node>v[200050];
int vis[200050];
int num=0;
ll ans=0;
int main(){
    
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
    
		int a;scanf("%d",&a);
		vector<int>tmp;
		tmp.clear();
		for(int j=2;1LL*j*j<=a;j++){
    
			if(a%j==0){
    
				tmp.push_back(j);
				while(a%j==0)a/=j;
			}
		}
		if(a!=1)tmp.push_back(a);
		for(int j=0;j<(1<<tmp.size());j++){
    
			ll h=1;
			int si=1;
			for(int k=0;k<tmp.size();k++){
    
				if((1<<k)&j){
    
					h=h*977777+tmp[k];
					h%=mod;
					si=-si; 
				}
			}
			v[i].push_back(node{
    h,si});
		}
	}
	while(m--){
    
		int a;
		scanf("%d",&a);
		ll res=0;
		res=num;
		int f=vis[a];
		for(auto to:v[a]){
    
			if(f){
    
				mp[to.h]--;
				res+=to.sig*mp[to.h];
			}else{
    
				res+=to.sig*mp[to.h];
				mp[to.h]++;
			}
		}
		vis[a]^=1;
		if(f)ans-=res;
		else ans+=res;
		printf("%lld\n",ans);	
	}
	return 0;
}