重庆公司网站设计制作网站建设与维护实训报告

登录 - XYOJ

思路：

        使用动态规划，设dp[n]表示当前数字之和模三等于0的组合数。

        状态转移方程：因为是模三，所以和的可能就只有0、1、2。等号右边的f和dp都表示当前一轮模三等于k的组合数。以第一行为例：等号右边表示 j转移到0的方案数+(当前j方案数*反正面等于0的个数)。ps：j转移到0表示  上一轮牌和为j到本轮的牌模三为0

			f[(j + 0) % 3] = (f[(j + 0) % 3] + dp[j] * c[0]) % MOD;f[(j + 1) % 3] = (f[(j + 1) % 3] + dp[j] * c[1]) % MOD;f[(j + 2) % 3] = (f[(j + 2) % 3] + dp[j] * c[2]) % MOD;

代码：

#include <bits/stdc++.h>
using namespace std;const int N = 1e5+9, MOD = 1e9 + 7;
int dp[3] = {1, 0, 0}; // dp[i]:和模三为i的组合数。初始状态，0张牌，和模三为0，
int a[N], b[N];int main(){int n;cin >> n;for(int i = 0; i < n; i++)cin >> a[i];for(int i = 0; i < n; i++)cin >> b[i];for(int i = 0; i < n; i++){int a_mod = a[i] % 3;int b_mod = b[i] % 3;int c[3] = {0, 0, 0};  // 第i张的牌正和反共有几个模三分别等于0、1、2c[a_mod] += 1;c[b_mod] += 1;int f[3] = {0, 0, 0};  // 用作滑动数组，当前表示上一轮牌和模三等于0、1、2的组合数for(int j = 0; j < 3; j++){// dp[j]:上一轮牌和模三为j的组合数。 f[(j + 0) % 3] = (f[(j + 0) % 3] + dp[j] * c[0]) % MOD;f[(j + 1) % 3] = (f[(j + 1) % 3] + dp[j] * c[1]) % MOD;f[(j + 2) % 3] = (f[(j + 2) % 3] + dp[j] * c[2]) % MOD;}for(int j = 0; j < 3; j++)dp[j] = f[j];  // 到此dp和f都表示本轮牌和模三为j的组合数}cout << dp[0] << '\n'; return 0;
} 

知识点：动态规划