社区讨论
为啥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 条回复,欢迎继续交流。
正在加载回复...