能给我看看这个算法题吗
你有一个大小为n×n的矩阵, 你可以在矩阵中自由地填写数字
假如将这个矩阵每个位置都填上0或1这两种数字, 不难计算: 共有2的(n×n)次方这么多种填写方案
但是小度不喜欢偶数, 它希望矩阵的任意某行或任意某列的数字之和均为奇数
那么按上述规则将n×n矩阵用0或1填满, 将有多少种方案去填写呢? 你能帮小度计算出来吗?
答案可能很大, 请输出答案对1000000007 (10⁹+7)取模后的结果
格式
输入格式
输入仅包含一个正整数n (1≤n≤109), 含义如题面所述
输出格式
输出一个非负整数, 含义如题面所述
2的（n-1）*(n-1)次方，到oj上试试
如果对你有帮助，可以给我个采纳吗，谢谢!! 点击我这个回答右上方的【采纳】按钮
我的想法是可能可以迭代求解，你把它设成一个关于n的函数，因为不管是哪一列和是奇数都不影响总数，你可以设置两个函数
$A_n$表示第一行和是偶数，$B_n$表示第一行和是奇数，那么当$n\rightarrow n+1$的时候
$A_{n+1}=B_n\times 2^{2n}+A_n\times 2^{2n}; $
$B_{n+1}$也类似