116. 小欧的卡牌（卡码网周赛第十七期（23年oppo提前批B组笔试真题））
题目描述
小欧有 n 张卡牌，第 i 张卡牌的正面写了个数字 ai，背面写了个数字 bi。小欧对于每张卡牌可以选择一面向上，她希望最终向上的数字之和为 3 的倍数。你能告诉小欧有多少方案吗？由于答案过大，请对 10 ^ 9 + 7 取模.
输入
第一行输入一个正整数 n，代表卡牌数量。
接下来的 n 行，每行输入两个正整数 ai 和 bi，代表第 i 张卡牌的正面和背面的数字. 1 <= n <= 10^5 1 <= ai,bi <= 10^9
输出
一个整数，代表方案数对 10^9 + 7 取模的值
样例输入
3
1 2
2 3
3 2
样例输出
3
题解1（C++版本）
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
const LL MOD = 1e9 + 7;
int n, a[N][2];
LL dp[N][3]; // dp[i][j]表示以第i个元素结尾，模3之后的余数为j的方案数
int main(){
scanf("%d", &n);
for(int i = 1; i <= n; i++){
scanf("%d %d", &a[i][0], &a[i][1]);
a[i][0] %= 3;
a[i][1] %= 3;
}
dp[0][0] = 1;
for(int i = 1; i <= n; i++){
for(int j = 0; j < 3; j++){
int m1 = (j - a[i][0]+3)%3;
int m2 = (j - a[i][1]+3)%3;
dp[i][j] = (dp[i][j] + dp[i - 1][m1] + dp[i - 1][m2]) % MOD;
}
}
printf("%lld\n", dp[n][0]);
return 0;
}