.交通管控

• 题意有\(n\)个操作，每个操作为一个字符串，代表从\(k\)个红绿灯的变化，初始\(k\)个灯全为绿灯，变化顺序为\(绿黄红循环\), + 代表每个灯变为下一种状态 , -代表每个灯变为上一种状态, 0代表没有变化， 问你这n个操作能组成的红绿灯的状态的数量
  
• $ 1 <= n <= 500, 1 <= k <=10, 2 <= m <= 1e9+7 $

其实就是那些操作选和不选，暴力的话可以二进制枚举，但是只能接受 \(n <=20\) 以内的大小,这里因为赛时的\(debug\)原因，还是写了个暴力对拍。
放个暴力对拍的代码

void solve(){
    ll n, k, M;
    cin >> n >> k >> M;
    vector<string> s(n + 1);
    for(int i = 0; i < n; i ++) cin >> s[i];
    map<string, int> mp;
    for(int i = 0; i < (1 << n); i ++){
        vector<ll> now(k, 0);
        for(int j = 0; j < n; j ++){
            if(i >> j & 1){
                for(int p = 0; p < k; p ++){
                    if(s[j][p] == '+') now[p] ++;
                    else if(s[j][p] == '-') now[p] --;
                }
            }
        }
        for(int p = 0; p < k; p ++){
            now[p] %= 3;
            now[p] += 3;
            now[p] %= 3;
        }
        string s1;
        for(int j = 0; j < k; j ++){
            ll x = now[j];
            if(x == 0) s1 += 'A';
            else if(x == 1) s1 += 'B';
            else s1 += 'C';
        }
        mp[s1] ++;
        mp[s1] %=M;
    }
    for(auto [x, y] : mp){
        cout << x << ' ' << y % M << endl;
    }
}

signed main(){
//    freopen("in.txt", "r", stdin);
//    freopen("out.txt", "w", stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int t = 1;
//    cin >> t;
    while(t --){
        solve();
    }
//    fclose(stdin);
//    fclose(stdout);
    return 0;
}

对于这种求方案数的问题，可以考虑\(dp\)，这里因为牵扯到\(k\)个灯的颜色变化，可以开\(k\)维数组，但是程序没法自动开，所以只剩状态压缩这一种办法，\(k\)个灯代表\(k\)个位置，每个位置有三种状态，即有\(3^k\)种状态，k最大为10，一种有\(3^k=59049\)看作\(1e5\), 时间复杂度为\(O(n*3^k*k)\) 大约\(5e8\)左右，限制给了\(10\)秒，复杂度很正确了，接下来考虑状态定义 dp[i][j] 代表用前\(i\)个操作达到\(j\)状态的方案数，答案就是 dp[i][state]， \(state\)代表出现过的状态，状态转移，\(dp[i][state] = dp[i - 1][j]， 这里的j是出现过的方案\),这里赛时用了一维的st数组标记的，导致样例对，交上去时wa，因为这里的st[j]时当前这一层的\(j\)状态，但是我们需要的是\(i - 1\)时的标记状态，导致得到错误的答案，赛时我们的判断有没有出现过的依据是\(dp[i-1][j]> 0\) 这里其实是有问题的涉及到取模，可能会取模成\(0\)，导致漏了某些合法方案数，所以st数组要开成\(n\)维，没有一个合法方案就\(st[i][state] = 1\) 代表这种方案出现过，注意更新的时候要算上不要这种操作的情况，也就是\(dp[i][j] = dp[i - 1][j]\)转移，这里也要更新st数组。初始的状态是\(dp[0][0] = 1, st[0][0] = 1\)，代表初始状态合法，这里空间有点极限，可以考虑滚动数组优化

void solve(){
	int n, k, m; cin >> n >> k >> m;
	vector<string> s(n + 1);
	for(int i = 1; i <= n; i ++) {
		cin >> s[i];
	}
	int sum = pow(3, k);
	vector<vector<int>>  dp(2, vector<int> (sum + 100));
	auto st = dp;
	dp[0][0] = 1;
	st[0][0] = 1;
	auto n_to_s = [&](int x) {
		string res;
		while(x) {
			res += (x % 3) + 'A';
			x /= 3;
		}
		while(res.size() < k) res.push_back('A');
		reverse(res.begin(), res.end());
		return res;
	};
	auto s_to_n = [&](string x) {
		int res = 0;
		for(int i = 0; i < x.size(); i ++) {
			res = res * 3 + (x[i] - 'A');
		}
		return res;
	};
	

	for(int i = 1; i <= n; i ++) {
		for(int j = 0; j < sum; j ++) dp[i & 1][j] = 0;
		for(int j = 0; j < sum; j ++) {
			dp[i & 1][j] += dp[(i - 1) & 1][j];
			if(st[(i - 1) & 1][j]) {
				st[i & 1][j] = 1;
			}
			dp[i & 1][j] %= m;
			string t = n_to_s(j);
			for(int p = 0; p < k; p ++) {//更新灯的状态
				if(s[i][p] == '+') {
					if(t[p] == 'C') t[p] = 'A';
					else t[p] ++;
				} else if(s[i][p] == '-') {
					if(t[p] == 'A') t[p] = 'C';
					else t[p] --;
				}
			}
			//cout << t << endl;
			int state = s_to_n(t);
			dp[i & 1][state] += dp[(i - 1) & 1][j];
			if(st[(i - 1) & 1][j]) {
				//cout << n_to_s(j) << ' ' << t << endl;
				st[i & 1][state] = 1;
			}
			dp[i & 1][state] %= m;
			
		}
	}
	for(int i = 0; i < sum; i ++) {//从小到大就是字典序了
		if(st[n & 1][i]) {
			cout << n_to_s(i) << ' ' << dp[n & 1][i] << endl;
		}
	}
}
int main()
{
	IOS;
	int T=1;
	cin>>T;
	while(T--){
		solve();
	}
	return 0;
}