题解 P2270 【[HNOI2002]奶牛的运算】

· · 题解

这绝对不是一道入门难度的题！

虽然我手贱写了入门。。。。

第一次写题解求轻喷

你会发现这道题改一下会变成这样

有一个长度为N-2的序列，你能进行M次操作

每次操作可以翻转其中的一个子序列（也可以不反转 浪费一次操作）

初始值全为0

求M次操作能获得的可能结果有多少种

然后就变成了求组合数的和

你会发现M次操作可以产生的0段1段的数量小于2*M+1

序列有N-3个空

插0~2*M次就可以了

注意除了2*M次 其他的组合数都是要*2的（你还有剩余操作可以把它整体翻过来嘛）

高精没优化也过了（数据并不是很强 我甚至不知道需不需要高精 但理论上讲是要的）

上代码

’‘’cpp

#include<bits/stdc++.h>
#define MAXN 105
int ans[MAXN],f[MAXN];
void cauculate1(int a)
{for(int i=0;i<MAXN;i++) f[i]*=a;
 for(int i=MAXN-1;i>=1;i--)
 {f[i-1]+=f[i]/10;f[i]%=10;}
 return;}
 void cauculate2(int a)
 {int flag=0;
  for(int i=0;i<MAXN;i++)
  {flag*=10;flag+=f[i];
   f[i]=flag/a;flag%=a;}
   return;}
void cauculate3(int k)
{
    for(int i=MAXN-1;i>=1;i--)
    {
       ans[i]+=k*f[i];    
       ans[i-1]+=ans[i]/10;
       ans[i]%=10; 
    }
    return;
}
void cmn(int n,int m)
{
    f[MAXN-1]=1;
    for(int i=0;i<m;i++) cauculate1(n-i);
    for(int i=0;i<m;i++) cauculate2(1+i);
    return;
}
int main()
{
    int op,l,i;
    scanf("%d%d",&l,&op);
    l=l-2;
    if(op==0)
    {
        printf("1");
        return 0;
    }
    if(op>(l-1)/2)
    {
        f[104]=1;
        for(i=0;i<l;i++) cauculate1(2);
        for(i=0;i<MAXN;i++) if(f[i]) break;
        for(;i<MAXN;i++) printf("%d",f[i]);
    }
    else
    {
        for(i=1;i<2*op;i++)
        {
            cmn(l-1,i);
            cauculate3(2);
            memset(f,0,sizeof(f));
        }
        cmn(l-1,2*op);
        cauculate3(1);
        memset(f,0,sizeof(f));
        f[MAXN-1]=2;
        cauculate3(1);
        for(i=0;i<MAXN;i++) if(ans[i]) break;
        for(;i<MAXN;i++) printf("%d",ans[i]);
    }
    return 0;
}
‘’‘