codeforces 816 D. Karen and Test（逆元+思维+组合数）

题目链接：http://codeforces.com/contest/816/problem/D

题解：显然一看到这题应该会想到是有什么规律的于是多写几项就会发现偶数列之间是有关系的。

满足a[i][j]=a[i-2][j]+a[i-2][j+2],于是递推到最后第2列a[2][0],a[2][1]就可以用最早出现的偶数列来求的，最后是加还是减只要看n就行了。

由于a[2][0]是有几个最早出现的偶数列的奇数项求的，而且这些奇数项选择的次数符合二项式分布（这个可以通过花一下杨辉三角理解一下）。

#include <iostream>

#include <cstring>

#include <cmath>

#include <cstdio>

#define mod 1000000007

using namespace std;

const int M = 2e5 + 10;

typedef long long ll;

ll anum[M] , bnum[M] , up[M] , down[M];

ll inv(ll a) {

    return a == 1 ? 1 : (ll)(mod - mod / a) * inv(mod % a) % mod;

}

//ll C(ll n , ll m)

//{

//    if(m < 0)return 0;

//    if(n < m)return 0;

//    if(m > n-m) m = n-m;

//    ll up = 1, down = 1;

//    for(ll i = 0 ; i < m ; i++){

//        up = up * (n-i) % mod;

//        down = down * (i+1) % mod;

//    }

//    return up * inv(down) % mod;

//}//原先利用逆元的算法，但是这里直接求会超时与处理一下up和down就行。

int main() {

    int n;

    scanf("%d" , &n);

    for(int i = 0 ; i < n ; i++) scanf("%lld" , &anum[i]) , bnum[i] = anum[i];

    if(n == 1) {printf("%lld\n" , anum[0]); return 0;}

    if(n & 1) {

        n--;

        int flag = 1;

        for(int i = 0 ; i < n ; i++) {

            if(flag) anum[i] = (bnum[i] + bnum[i + 1]) % mod;

            else anum[i] = (bnum[i] - bnum[i + 1] + mod) % mod;

            flag ^= 1;

        }

    }

    n = n / 2 - 1;

    ll ans1 = 0 , ans2 = 0;

    up[0] = 1 , down[0] = 1;

    for(int i = 1 ; i <= n / 2 ; i++) up[i] = up[i - 1] * (n - i + 1) % mod , down[i] = down[i - 1] * i % mod;

    for(int i = n / 2 + 1 ; i <= n ; i++) up[i] = up[n - i] , down[i] = down[n - i];

    for(int i = 0 ; i <= n ; i++) {

        ans1 += anum[2 * i] * (up[i] * inv(down[i]) % mod) % mod;

        ans1 %= mod;

        ans2 += anum[2 * i + 1] * (up[i] * inv(down[i]) % mod) % mod;

        ans2 %= mod;

    }

    if(n % 2) ans1 = (ans1 - ans2 + mod) % mod;

    else ans1 = (ans1 + ans2) % mod;

    printf("%lld\n" , ans1);

    return 0;

}

巴特西

codeforces 816 D. Karen and Test（逆元+思维+组合数）

最新文章

热门文章