T2

题意： 第i个灯泡被k个开关控制，当有奇数/偶数个开关打开时灯泡会亮

实现方式：DFS搜索$O（2^N）$在最后判断所有灯泡是否点亮

#include<bits/stdc++.h>
using namespace std;
int n,m;
bool dp[11];
vector<int> v[15];
int p[11];
int ans;
void dfs(int x){
	if(x>n){
	for(int i=1;i<=m;i++){
	    int sum=0;

		for(int j=0;j<v[i].size();j++)
	    if(dp[v[i][j]]) sum++;
	    
		if(sum%2!=p[i]) return ;
	}

    ans++;
    return ;
	}
		
    dfs(x+1);
    dp[x]=1;
    dfs(x+1);
	dp[x]=0;
}
int main(){
	freopen("switch.in","r",stdin);
	freopen("switch.out","w",stdout);
    cin>>n>>m;
    int k,l;
    for(int i=1;i<=m;i++){
    	cin>>k;
    	while(k--) {
    	cin>>l;
		v[i].push_back(l);
		}
	}
	for(int i=1;i<=m;i++) cin>>p[i];
	dfs(1);
	cout<<ans;
	return 0;
} 

T3

题意：在1--N中找到不能表示为$a^b$的数

思考方向：找到可以表示为$a^b$的数，最后输出n-ans

实现方法：循环遍历i,标记i*i

#include<bits/stdc++.h>
using namespace std;
long long ans;
map<long long,long long> p;
int main(){  
    freopen("num.in","r",stdin);
    freopen("num.out","w",stdout);
	long long n;
	cin>>n;
	for(long long i=2;i*i<=n;i++){
		if(p[i]) continue;
		long long t=i*i;
		while(t<=n){
			ans++;
			p[t]++;
			t*=i;
		}
	}
	cout<<n-ans;
	return 0;
}

T6

题意：进行N次空间跃迁，有三种方式

1. （x,y）->(x+a,y+b)
2. （x,y）->(x+c,y+d)
3. （x,y）->(x+e,y+f)

障碍点不能跃迁

问有多少种路径

思考方向：标记跃迁方式

实现方法：设$dp~i~~u~~v~$:在i次跃迁中第一种u次，第二种v次，第三种w=i-u-v次

所到达的位置：$nx=A*u+C*v+E*w,ny=B*u+D*v+F*w$

障碍点的标记用哈希表来实现

if(!p.count({nx, ny})){
           dp[i][u][v]=dp[i-1][u][v]%mod;
           if(u>0) dp[i][u][v]=(dp[i][u][v]+dp[i-1][u-1][v])%mod;
           if(v>0) dp[i][u][v]=(dp[i][u][v]+dp[i-1][u][v-1])%mod;
           if(i==n) ans=(dp[n][u][v]+ans)%mod;
        ```

#include<bits/stdc++.h>
using namespace std;
int dp[302][302][302];
int mod=998244353;
int n,m;
int A,B,C,D,E,F;
long long ans=0;
map<pair<long long,long long>,bool> p;
int main(){
    freopen("jump.in","r",stdin);
    freopen("jump.out","w",stdout);
    cin>>n>>m;
    cin>>A>>B>>C>>D>>E>>F;
    for(int i=1;i<=m;i++){
        int x,y;
        cin>>x>>y;
        p[{x,y}]=1;
    }
    dp[0][0][0]=1;
    for(long long i=1;i<=n;i++){
        for(long long u=0;u<=i;u++){ 
            for(long long v=0;v<=i-u;v++){
                int w=i-v-u;
            long long nx=A*u+C*v+E*w,ny=B*u+D*v+F*w;
            if(!p.count({nx, ny})){
            dp[i][u][v]=dp[i-1][u][v]%mod;
            if(u>0) dp[i][u][v]=(dp[i][u][v]+dp[i-1][u-1][v])%mod;
            if(v>0) dp[i][u][v]=(dp[i][u][v]+dp[i-1][u][v-1])%mod;
            if(i==n) ans=(dp[n][u][v]+ans)%mod;
            }
        }
        }
    }
    cout<<ans;
    return 0;
}