平衡的选择题_

牛牛准备出一套卷子，这个卷子有n个多项选择题，每个选择题有A、B、C、D四个选项。

多项选择题的答案有15种：(A,B,C,D,AB,AC,AD,BC,BD,CD,ABC,ACD,ABD,BCD,ABCD)

牛牛对于试卷答案之间的平衡有奇妙的要求：他希望按顺序做下来，做完每一题的时候，目前正确答案中A出现的次数和C出现的次数差距不超过1，B出现的次数和D出现的次数差距不超过2.

举个例子：有两个选择题，那么第一题答案为AC，第二题答案为A，这是满足要求的，因为做完第一题的时候A出现了1次C出现了1次，做完第二题的时候A出现了2次，C出现了1次。

如果第一题答案是AD，第二题答案是A，那么做完第一题的时候A出现了1次，D出现了1次，符合要求。做完第二题的时候A出现了2次，C出现了0次，D出现了1次，A和C差距为2，则不符合要求。

现在牛牛想知道，如果有n个多项选择题，那么一共有多少种试卷答案是符合牛牛的要求的。

为了防止答案过大，答案对1e9+7取模

public class Solution { /** * 平衡的选择题 * * @param n int整型 * @return int整型 */ public int solve(int n) { /*case: * a : 3 (AC, BD, ACBD) —— 完全平衡 * b : 4 (A, ABD, C, CBD) —— |A - C| == 1 * c : 4 (B, ACB, D, ACD) —— |B - D| == 1 * d : 4 (AB, AD, CB, CD) —— |A - C| == 1 && |B - D| == 1 * e : 0 —— |B - D| == 2 * f : 0 —— |A - C| == 1 && |B - D| == 2 */ final int MOD = 1000000007; long a = 3, b = 4, c = 4, d = 4, e = 0, f = 0; long ta, tb, tc, td, te, tf; for (int i = 1; i < n; i++) { ta = (3 * a + 2 * b + 2 * c + d) % MOD; tb = (4 * a + 3 * b + 2 * c + 2 * d) % MOD; tc = (4 * a + 2 * b + 3 * c + 2 * d + 2 * e + f) % MOD; td = (4 * a + 4 * b + 4 * c + 3 * d + 2 * e + 2 * f) % MOD; te = (2 * c + d + 3 * e + 2 * f) % MOD; tf = (2 * c + 2 * d + 4 * e + 3 * f) % MOD; a = ta; b = tb; c = tc; d = td; e = te; f = tf; } return (int) ((a + b + c + d + e + f) % MOD); } }

class Solution { public: /** * 平衡的选择题 * @param n int整型 * @return int整型 */ int solve(int n) { const int M = 1000000007; long a=3, b=4, c=4, d=4, e=0, f=0, aa, bb, cc, dd, ee, ff; for(int i=1;i<n;i++){ aa = (3*a + 2*b + 2*c + d) % M; bb = (4*a + 3*b + 2*c + 2*d) % M; cc = (4*a + 2*b + 3*c + 2*d + 2*e + f) % M; dd = (4*a + 4*b + 4*c + 3*d + 2*e + 2*f) % M; ee = (2*c + d + 3*e + 2*f) % M; ff = (2*c + 2*d + 4*e + 3*f) % M; a = aa; b = bb; c = cc; d = dd; e = ee; f = ff; } return (a+b+c+d+e+f)%M; } };

平衡的选择题

输入

输出

说明

备注:

问题信息

热门推荐

通过挑战的用户

相关试题