Painful Bases LightOJ

Painful Bases LightOJ - 1021

题意：给出0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F中的一些字符（不重复）还有一个进制base，求这些字符的排列形成的base进制数中，有多少个能被k整除。

方法：

正常的做法：

http://blog.csdn.net/chenzhenyu123456/article/details/51155038

自己的做法（常数很大，仅做记录）：

ans[i][S][j]表示i进制下，S集合中数字可用，总产生余数为j时方案数

digit(S)表示S集合中元素数量。那么，当前数字为一个digit(S)位的base进制数，其第digit(S)位的值转换为10进制后除以k产生的余数就是j。

ans[i][S][j]=sum{ans[i][S-p][(j+k-pow(i,digit(S)-1)*p%k)%k}

其含义：把S中任意一个数字p当做首位，首位产生的余数$pow(i,digit(S)-1)*p%k$，然后剩下数字的余数应该是$(j+k-pow(i,digit(S)-1)*p%k)%k$。

实际使用时，这样定义状态会爆空间，因此只能把i的一维舍去，每组数据都重新算。

错误次数：2

原因：

1.用循环，被卡常，改成了记忆化搜索。

2.在用循环的时候，为了卡常，改了循环内外层，但不正确。

卡常记录：把记录a^b改成记录所有a^b%k，时间缩短到1/3。

 #include<cstdio>

 #include<cstring>

 typedef long long LL;

 LL ans[][];

 LL T,TT;

 bool ok[];

 char ss[];

 LL popcount[];

 LL powww[][][];

 LL base,k;

 LL poww(LL a,LL b)

 {

     if(powww[a][b][k])    return powww[a][b][k];

     LL base=a,ans=,b1=b;

     while(b)

     {

         if(b&)    ans=ans*base%k;

         b>>=;

         base=base*base%k;

     }

     return powww[a][b1][k]=ans;

 }

 LL get(LL s,LL j)

 {

     if(ans[s][j]!=-)    return ans[s][j];

     int j1;

     ans[s][j]=;

     for(j1=;j1<base;j1++)

         if(s&(<<j1))

             ans[s][j]+=get(s^(<<j1),(j+k-poww(base,__builtin_popcount(s)-)*j1%k)%k);

     return ans[s][j];

 }

 int main()

 {

     LL i,tt;

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

         popcount[i]=__builtin_popcountll(i);

     scanf("%lld",&T);

     for(TT=;TT<=T;TT++)

     {

         tt=;

         memset(ok,,sizeof(ok));

         memset(ans,-,sizeof(ans));

         scanf("%lld%lld",&base,&k);

         ans[][]=;

         scanf("%s",ss);

         for(i=;i<strlen(ss);i++)

             if(ss[i]>=''&&ss[i]<='')

                 ok[ss[i]-'']=;

             else

                 ok[ss[i]-'A'+]=;

         for(i=;i<base;i++)

             if(ok[i])

                 tt^=(<<i);

         printf("Case %lld: %lld\n",TT,get(tt,));

     }

     return ;

 }

巴特西

Painful Bases LightOJ - 1021

最新文章

热门文章