社区讨论

为啥CE+如何改,本地编译可过,问题在__popcount上。

P2167[SDOI2009] Bill的挑战参与者 2已保存回复 1

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
1 条
当前快照
1 份
快照标识符
@mlhvs18z
此快照首次捕获于
2026/02/11 18:22
上周
此快照最后确认于
2026/02/13 15:55
6 天前
查看原帖
CPP
#include<bits/stdc++.h>
using namespace std;
string dp[(1 << 15) + 5],s[20];
int n,k;
long long check(string a) {
	long long ans = 1;
	for(int i = 0;i < a.size();i++) {
		if(a[i] == '?') ans = (ans * 26) % 1000003;
	}
	return ans % 1000003;
}
int main() {
	int t;
	cin >> t;
	while(t--) {
		cin >> n >> k;
		for(int i = 0;i < (1 << n);i++) dp[i] = "?????????????????????????????????????????????????";
		for(int i = 1;i <= n;i++) {
			cin >> s[i];
			dp[(1 << i - 1)] = s[i];
		}
		if(k > n) {
			cout << 0 << '\n';
			continue ;
		}
		long long ans = 0;
		for(int i = 1;i < (1 << n);i++) {
			int lo = i & (-i);
			//合并s[lo]和dp[i-lo]
			//			cout << lo << ' ' << __builtin_ctz(lo) + 1 << '\n';
			string a = s[__builtin_ctz(lo) + 1],b = dp[i - lo],c;
			for(int j = 0;j < a.size();j++) {
				if(a[j] == '?' && b[j] == '?') {
					c += '?';
				}
				else if(a[j] == '?') {
					c += b[j];
				}
				else if(b[j] == '?') {
					c += a[j];
				}
				else {
					c = "!!!!!!!!!!!!!!!!!!";
				}
			}
			//			cout << a << ' ' << b << ' ' << c << '\n';
			dp[i] = c;
		}
		for(int i = 1;i < (1 << n);i++) {
			int p = __popcount(i);
			if(p == k) {
				string a = dp[i],b = dp[((1 << n) - 1) ^ i],c;
				auto ita = a.find("!");
				auto itb = b.find("!");
				if(ita < a.size()) {
					continue ;
				}
				if(itb < b.size()) {
					ans = (ans + check(a)) % 1000003;
					continue ; 	
				}
				bool oplus = 0;//如果两个串已经不一样了,就不用管。
				//不一样,答案不变
				//有可能一样,减去一样的
				for(int j = 0;j < a.size();j++) {
					if(a[j] == '?' && b[j] == '?') c[j] = '?';
					else if(a[j] == '?') c[j] = b[j];
					else if(b[j] == '?') c[j] = a[j];
					else oplus = 1;
				}
				//				cout << i << "|" << (((1 << n) - 1) ^ i) << '|' << a << '|' << b << '|' << c << '|' << ans << '|' << check(a) << '|' << check(c) << '\n';
				if(oplus == 0) {
					ans = (ans + check(a)) % 1000003;
				}
				else {
					ans = (ans + check(a) - check(c) + 1000003) % 1000003;
				}
			}
		}
		cout << ans << '\n';
	}
	return 0;
}

回复

1 条回复,欢迎继续交流。

正在加载回复...