bzoj1089

题解：

递推

f[i]=f[i-1]^n+1

ans=f[d]-f[d-1]

代码：

#include<bits/stdc++.h>

using namespace std;

int n,m;

struct zz

{

    int len,a[];

    void init()

     {

         memset(a,,sizeof a);

         len=;

     }

    void write()

     {

         printf("%d",a[len]);

         for (int i=len-;i;i--)

          {

              if (a[i]<)putchar('');

              if (a[i]<)putchar('');

              if (a[i]<)putchar('');

              printf("%d",a[i]);

          }

     }

}f[];

zz cf(zz x,zz y)

{

    zz z;

    z.init();

    z.len=x.len+y.len-;

    for (int i=;i<=x.len;i++)

     for (int j=;j<=y.len;j++)

      z.a[i+j-]+=x.a[i]*y.a[j];

    for (int i=;i<=z.len;i++)

     {

         z.a[i+]+=z.a[i]/;

         z.a[i]%=;

     }

    if (z.a[z.len+])z.len++;

    return z;

}

zz jf(zz z)

{

    z.a[]++;

    for (int i=;i<=z.len;i++)

     {

         z.a[i+]+=z.a[i]/;

         z.a[i]%=;

     }

    if (z.a[z.len+])z.len++;

    return z;

}

zz zf(zz x,zz y)

{

    for (int i=;i<=x.len;i++)

     {

         x.a[i]-=y.a[i];

         if (x.a[i]<)x.a[i+]--,x.a[i]+=;

     }

    while (x.len>&&x.a[x.len]==)x.len--;

    return x;

}

int main()

{

    scanf("%d%d",&n,&m);

    if (m==)

     {

         puts("");

         return ;

     }

    f[].a[]=f[].len=;

    for (int i=;i<=m;i++)

     {

         f[i].a[]=f[i].len=;

         for (int j=;j<=n;j++)

          f[i]=cf(f[i],f[i-]);

         f[i]=jf(f[i]);

     }

    zz ans=zf(f[m],f[m-]);

    ans.write();

}