登录 - 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、2
		
		c[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;
} 

---

知识点：动态规划