20250316 OPPO笔试

#include <iostream>#include <vector>#include <string>using namespace std;
const int MOD = 1e9 + 7;
int main() {
  int n;string s;cin >> n >> s;
  long long sum_known = 0;
  vector<int> unknown_positions;

  for (int i = 0; i < n; ++i) {
	  if (s[i] == '?') {
		  unknown_positions.push_back(i);
	  } else {
		  sum_known += s[i] - '0';
	  }
  }

  int s_rem = sum_known % 3;
  int target_rem = (3 - s_rem) % 3;

  if (unknown_positions.empty()) {
	  cout << (s_rem == 0 ? 1 : 0) << endl;
	  return 0;
  }

  bool first_is_unknown = (unknown_positions[0] == 0);

  vector<long long> dp(3, 0);

  if (first_is_unknown) {
	  // 处理第一个问号（不能为0）
	  dp[0] = 3; // 可选的余数0的数字：3,6,9
	  dp[1] = 3; // 余数1：1,4,7
	  dp[2] = 3; // 余数2：2,5,8

	  // 处理剩余问号
	  for (int i = 1; i < unknown_positions.size(); ++i) {
		  vector<long long> new_dp(3, 0);
		  for (int prev = 0; prev < 3; ++prev) {
			  // 转移公式：dp[prev]表示前 i-1 个数值为prev的可能组合数，(prev + 0) % 3 表示prev转移为(prev + 0)的组合数。
			  new_dp[(prev + 0) % 3] = (new_dp[(prev + 0) % 3] + dp[prev] * 4) % MOD;
			  new_dp[(prev + 1) % 3] = (new_dp[(prev + 1) % 3] + dp[prev] * 3) % MOD;
			  new_dp[(prev + 2) % 3] = (new_dp[(prev + 2) % 3] + dp[prev] * 3) % MOD;
		  }
		  dp = new_dp;
	  }
  } else {
	  // 所有问号都不是首位
	  dp[0] = 1;
	  for (int pos : unknown_positions) {
		  vector<long long> new_dp(3, 0);
		  for (int prev = 0; prev < 3; ++prev) {
			  new_dp[(prev + 0) % 3] = (new_dp[(prev + 0) % 3] + dp[prev] * 4) % MOD;
			  new_dp[(prev + 1) % 3] = (new_dp[(prev + 1) % 3] + dp[prev] * 3) % MOD;
			  new_dp[(prev + 2) % 3] = (new_dp[(prev + 2) % 3] + dp[prev] * 3) % MOD;
		  }
		  dp = new_dp;
	  }
  }
  cout << dp[target_rem] % MOD << endl;
  return 0;
}