模3问题

2019-04-13 14:38发布

站内文章 / 模拟电子
10778 0 1616
import java.math.BigInteger; import java.util.Scanner; public class five { public static void main(String[] args) { BigInteger[][] f = new BigInteger[100001][4]; int n,i; Scanner sc = new Scanner(System.in); n = sc.nextInt(); BigInteger one = new BigInteger("1"); BigInteger two = new BigInteger("2"); BigInteger big = new BigInteger("100007"); f[1][0] = two; f[1][1] = one; f[1][2] = two; for(i = 2;i <= n;i++){ f[i][0] = ((one.multiply(f[i-1][0])).add(two.multiply(f[i-1][1]))).add(two.multiply(f[i-1][2])); f[i][1] = ((two.multiply(f[i-1][0])).add(one.multiply(f[i-1][1]))).add(two.multiply(f[i-1][2])); f[i][2] = ((two.multiply(f[i-1][0])).add(two.multiply(f[i-1][1]))).add(one.multiply(f[i-1][2])); } System.out.println(((f[n][1]).subtract(one)).remainder(big)); } } 如果你要计算f[i][0]的话，你肯定是由f[i-1][0]，f[i-1][1]，f[i-1][2]三个值地推来的，如果是f[i-1][0]的话，说明原来的数模3除尽了，所以这个时候再加一位数，这个数只能是3，
如果是f[i-1][1]的话，说明原来的数模3除余1，所以这个时候再加一位数，这个数可能是2或者5,这两种情况，所以这种情况共有2*f[i-1][1]个，
如果是f[i-1][2]的话，说明原来的数模3除余2，所以这个时候再加一位数，这个数可能是1或者4,这两种情况，所以这种情况共有2*f[i-1][2]个
总的f[i][0]就是这三种情况的总和，，f[i][0]=f[i-1][0]+f[i-1][1]*2+f[i-1][2]*2

热门文章