武大校赛 F Figure out the sequence

Solution

简单dp, 令 为第 个字符串中第 个字母出现的次数
显然有递推式子
先预处理下 和 即可
注意 的 可能比较大, 数组要开大点

Code

/*
  autor: Kurisu
  2020年4月25日11:30:19
*/
#include<bits/stdc++.h>
using namespace std;

const long long inf = 1e18;
const int N = 105 + 5;
const double eps = 1e-10;
const int mod = 1e9 + 7;
typedef long long ll;

ll dp[N][320];

int main() {
  string s, t;
  cin >> s >> t;
  for(int i = 0; i < s.size(); i++) {
    for(int j = 0; j < 220; j++) {
      dp[1][j] += (s[i] == j);
    }
  }
  for(int i = 0; i < t.size(); i++) {
    for(int j = 0; j < 220; j++) {
      dp[2][j] += (t[i] == j);
    }
  }
  int n;
  cin >> n;
  for(int i = 3; i <= n; i++) {
    for(int j = 0; j < 220; j++) {
      dp[i][j] = dp[i - 1][j] + dp[i - 2][j];
    }
  }
  for(int j = 0; j < 220; j++) {
    if(dp[n][j])
      cout << char(j) << ": " << dp[n][j] << "\n";
  }
  return 0;
}