【洛谷P2270】奶牛的运算

题目链接

不难发现，每加一个括号，就相当于把括号内一段区间中的符号反转，于是就是看n-1个符号经过k次区间反转后的状态数，用插板法搞一搞就可以了

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;

int n,k;
struct Big_int{
    int v[1000],len;
}C[110][110],ans,_0,_1;

inline Big_int add(Big_int a,Big_int b){
    Big_int c=_0;
    int len=max(a.len,b.len);
    for(int i=1;i<=len;++i){
        c.v[i]+=a.v[i]+b.v[i];
        if(c.v[i]>9){
            c.v[i+1]+=c.v[i]/10;
            c.v[i]%=10;
        }
    }
    while(c.v[len+1]) ++len;
    c.len=len;
    return c;
}

void print(Big_int x){
    for(int i=x.len;i>=1;--i)
        printf("%d",x.v[i]);
    puts("");
}

signed main()
{
    scanf("%lld%lld",&n,&k);
    _1.len=1; _1.v[1]=1;
    C[0][0]=_1;
    for(int i=1;i<=100;++i){
        C[i][0]=_1;
        for(int j=1;j<=i;++j)
            C[i][j]=add(C[i-1][j],C[i-1][j-1]);
    }
    int M=min(n-3,k*2-1);
    for(int i=0;i<=M;++i)
        ans=add(ans,add(C[n-3][i],C[n-3][i]));
    if(k*2<=n-3) ans=add(ans,C[n-3][k*2]);
    print(ans);
    return 0;
}

【洛谷P2270】奶牛的运算

原文：https://www.cnblogs.com/yjkhhh/p/11629314.html