用C语言代码编写：定义一个排列为“好排列”，当且仅当所有相邻两个数的乘积 均为偶数。 小欧想知道，长度n的好排列一共有多少种？由于该数可能 过大，请对10^9+7取模。 1输入描述 个正整数n。 2≤n≤10^5 输出描述 好排列的数量。 示例 输入 2 输出 2

在C语言中，我们可以采用动态规划的方式来解决这个问题。首先，我们创建一个布尔数组dp，其中dp[i]表示是否能从1到i形成一个满足条件的好排列。对于每个i，有两种情况：

dp[i-1] = true，意味着可以形成以i-1结尾的好排列，那么i需要是偶数，才能保证i*(i-1)的乘积也是偶数。此时dp[i] = (i % 2 == 0);
dp[i-1] = false，意味着不能以i-1结尾，那么i只要是偶数，都可以与i-1一起构成新的偶数乘积。所以dp[i] = ((i % 2 == 0) && (dp[(i-2)/2]));

我们需要初始化dp[0] = true，因为长度为1的序列只有一个，即"1"。
最后的结果是所有dp[i]为true的情况，我们可以通过累积dp数组并求模1e9+7来得到总数。以下是C代码实现：
#include <stdio.h>

#define MOD 1000000007

int main() {
int n;
scanf("%d", &amp;n);

// 初始化dp数组
bool dp[n + 1];
dp[0] = 1;

for (int i = 2; i <= n; ++i) {
if (i % 2 == 0)
dp[i] = dp[(i - 2) / 2]; // 如果i是偶数，则可以与前面偶数组合
else
dp[i] = dp[i - 1]; // 如果i是奇数，则只能由偶数组成
}

long long count = 0;
for (int i = 0; i <= n; ++i)
if (dp[i])
count++;

printf("%lld\n", count % MOD); // 对结果取模

return 0;
}
登录后复制