#P2188. 第3题-数组交替
-
1000ms
Tried: 74
Accepted: 8
Difficulty: 9
所属公司 :
百度
时间 :2024年10月15日-算法
第3题-数组交替
本题直接看很难看出规律,打表可以发现当n为偶数时规律很明显,如下图:

不难看出最后每个ai的系数跟杨辉三角有关,手玩几个样例可以发现当n为4的倍数时最后一列是相减,非4的倍数时最后一列是相加,当n为奇数时可以先算一列转换成偶数来做.
记组合数c(n,m),那么当n为偶数时最后一列的系数每两个数一组依次为c(n/2−1,i/2),直接预处理组合数再根据上述规律算即可
c++
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+10,mod=1e9+7;
ll a[N],f[N],g[N];
int n;
ll qmi(ll a,ll b)
{
ll res=1;
while(b)
{
if(b&1)res=res*a%mod;
b>>=1;
a=a*a%mod;
}
return res;
}
void init()//预处理
{
g[0]=f[0]=1;
for(int i=1;i<N;i++)
{
f[i]=f[i-1]*i%mod;
g[i]=g[i-1]*qmi(i,mod-2)%mod;
}
}
ll c(ll n,ll m)
{
if(n<m)return 0;
return f[n]*g[n-m]%mod*g[m]%mod;
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
init();
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
if(n<=2)//特判n<=2的情况
{
cout<<(a[1]+a[2])%mod<<endl;
return 0;
}
if(n&1)//n为奇数时可以转化成偶数来做
{
int mk=1;
for(int i=1;i<n;i++)
{
a[i]=a[i]+a[i+1]*mk;
mk=-mk;
}
n--;
}
int mk=(n%4)?1:-1;//打表可得
ll res=0;
for(int i=1;i<=n;i+=2)
{
ll temp=c(n/2-1,i/2);//本质是杨辉三角
res=(res+(a[i]+mk*a[i+1])*temp+mod)%mod;
}
cout<<(res+mod)%mod<<endl;
}
python
import sys
sys.setrecursionlimit(10**5)
MOD = 10**9 + 7
N = 10**5 + 10
a = [0] * N
f = [0] * N
g = [0] * N
def qmi(a, b):
res = 1
while b:
if b & 1:
res = res * a % MOD
b >>= 1
a = a * a % MOD
return res
def init(): # 预处理
g[0] = f[0] = 1
for i in range(1, N):
f[i] = f[i - 1] * i % MOD
g[i] = g[i - 1] * qmi(i, MOD - 2) % MOD
def c(n, m):
if n < m:
return 0
return f[n] * g[n - m] % MOD * g[m] % MOD
def main():
init()
n = int(input())
input_list = list(map(int, input().split())) # 将一行输入按空格分割并转为整数列表
for i in range(1, n + 1):
a[i] = input_list[i - 1] # 把输入列表的值赋给 a 数组
if n <= 2: # 特判n<=2的情况
print((a[1] + a[2]) % MOD)
return
if n & 1: # n为奇数时可以转化成偶数来做
mk = 1
for i in range(1, n):
a[i] = a[i] + a[i + 1] * mk
mk = -mk
n -= 1
mk = 1 if (n % 4) else -1 # 打表可得
res = 0
for i in range(1, n + 1, 2):
temp = c(n // 2 - 1, i // 2) # 本质是杨辉三角
res = (res + (a[i] + mk * a[i + 1]) * temp + MOD) % MOD
print((res + MOD) % MOD)
if __name__ == "__main__":
main()
java
import java.util.*;
public class Main {
static final int N = 100010, mod = 1000000007;
static long[] a = new long[N], f = new long[N], g = new long[N];
static int n;
static long qmi(long a, long b) {
long res = 1;
while (b != 0) {
if ((b & 1) != 0) res = res * a % mod;
b >>= 1;
a = a * a % mod;
}
return res;
}
static void init() { // 预处理
g[0] = f[0] = 1;
for (int i = 1; i < N; i++) {
f[i] = f[i - 1] * i % mod;
g[i] = g[i - 1] * qmi(i, mod - 2) % mod;
}
}
static long c(long n, long m) {
if (n < m) return 0;
return f[(int) n] * g[(int) (n - m)] % mod * g[(int) m] % mod;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
init();
n = sc.nextInt();
for (int i = 1; i <= n; i++) a[i] = sc.nextLong();
if (n <= 2) { // 特判n<=2的情况
System.out.println((a[1] + a[2]) % mod);
return;
}
if ((n & 1) != 0) { // n为奇数时可以转化成偶数来做
int mk = 1;
for (int i = 1; i < n; i++) {
a[i] = a[i] + a[i + 1] * mk;
mk = -mk;
}
n--;
}
int mk = (n % 4 != 0) ? 1 : -1; // 打表可得
long res = 0;
for (int i = 1; i <= n; i += 2) {
long temp = c(n / 2 - 1, i / 2); // 本质是杨辉三角
res = (res + (a[i] + mk * a[i + 1]) * temp + mod) % mod;
}
System.out.println((res + mod) % mod);
}
}
题目内容
由n个整数构成的数组{a1,a2,...,an},我们有如下操作:
-
你必须在这些整数之间交替写下加减符号,例如假设数组初始值 {1,2,3,4},交替写下加减符号变为1+2−3+4;
-
此时会生成第二行数组{1+2,2−3,3+4},即{3,−1,7};随后,再次交替写下加减符号变为3−(−1)+7(由于上一行末尾是+,所以这一行的开头是−);
-
此时会生成第三行数组{4,6},继续重复上述操作;
-
直到最后只剩下唯一一个数字时,中止操作,在上方的样例中,最后剩下的数字为−2。
现在,你需要独立求出给定的数组剩下的最后一个值是多少。
输入描述
第一行输入一个整数n(1≤n≤105)代表数组中的元素数量。
第二行输入n个整数a1,a2,...,an (1≤ai≤109)代表数组元素。
输出描述
在一行上输出一个整数,表示剩下的最后一个值。由于答案可能很大,只需要输出答案对109+7取模的结果。
样例1
输入
4
1 2 3 4
输出
1000000005
说明
该样例已在题面中说明,注意,负数也需要取模。