【（好题）组合数+Lucas定理+公式递推（lowbit+滚动数组）+打表找规律】2017多校训练七 HDU 6129 Just do it

http://acm.hdu.edu.cn/showproblem.php?pid=6129

【题意】

对于一个长度为n的序列a，我们可以计算b[i]=a1^a2^......^ai，这样得到序列b
重复这样的操作m次，每次都是从上次求出的序列a得到一个新序列b
给定初始的序列，求重复m次操作后得到的序列

【方法一】

假定n=5,我们模拟一次可以发现，经过m次操作后a1在b1......bn中出现的次数为：

m=0: 1 0 0 0 0
m=2: 1 2 3 4 5
m=3: 1 3 6 10 15
m=4:1 4 10 20 35
m=5:1 5 15 35 70

（画个杨辉三角出来就可以看出这些都是组合数）

容易推出来操作m次后，a1在答案bi中出现的次数C(m+i-2,m-1),由于是异或，我们只需知道C(m+i-2,m-1)%2

根据Lucas定理（2是素数），x=m-1,y=m+i-2,C(x,y)%2为x和y写成二进制后每一位C(xi,yi)%2的连乘，可以发现，只有C(0,1)是0，也就是C(x,y)%2==0 <=> y的二进制位置为1的集合是x的子集 <=> (x&y)==y

这道题m=1的时候是n^2的，然而这个复杂度是可以过的（奇怪）

附上AC代码

【AC】

 #include<bits/stdc++.h>

 using namespace std;

 typedef long long ll;

 const int maxn=2e5+;

 ll a[maxn];

 ll b[maxn];

 int n;

 ll m;

 int main()

 {

     int T;

     scanf("%d",&T);

     while(T--)

     {

         memset(b,,sizeof(b));

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

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

         {

             scanf("%I64d",&a[i]);

         }

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

         {

             ll y=m-;

             ll x=m+i-;

             if((x&y)==y)

             {

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

                 {

                     b[j]^=a[j-i+];

                 }

             }

         }

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

         {

             if(i==) printf("%I64d",b[i]);

             else printf(" %I64d",b[i]);

         }

         puts("");

     }

     return ;

 }

【经验】

把a,b二进制表达后b中1的位置是a中1的位置的子集 <=> (a&b)==b
C(2^k-1,i)%2==1 <=> 0<=i<=2^k-1

********************************************************************************************************************************

【方法二】

dp(i, j)表示第i次变换第j列的数。
dp(i, j) = dp(i, j-1)^dp(i-1, j) = dp(i, j-2)^dp(i-1, j-1)^dp(i-1, j-1)^dp(i-2, j) = dp(i, j-2)^dp(i-2, j) => dp(i, j-2^n)^dp(i-2^n, j)
从m中的最高位或最低位开始递推。

类似于dp[i][j]=dp[i-1][j]+dp[i][j-1],最后求dp[m][j](1<=j<=n)我们可以开一个滚动数组从前往后递推(dp[i][j]=dp[i-1][j]+dp[i][j+1]则是从后往前推)

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

 {

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

     {

         dp[j]^=dp[j-];

     }

 }

dp[i][j]=dp[i-1][j]^dp[i][j-1]

计算dp[i][j]=dp[i-2^n][j]^dp[i][j-2^n]，用lowbit从右往左枚举m的每一位，每一次都对整列进行更新。

 while(m)

 {

     int x=lowbit(m);

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

     {

         dp[j]^=dp[j-x];

     }

     m-=x;

 }

dp[i][j]=dp[i-2^n]^dp[i][j-2^n]

【AC】

 #include<bits/stdc++.h>

 using namespace std;

 typedef long long ll;

 const int maxn=2e5+;

 int n,m;

 int dp[maxn];

 int main()

 {

     int T;

     scanf("%d",&T);

     while(T--)

     {

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

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

         {

             scanf("%d",&dp[i]);

         }

         while(m)

         {

             int x=m&(-m);

             for(int i=x;i<n;i++)

             {

                 dp[i]^=dp[i-x];

             }

             m-=x;

         }

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

         {

             if(i==) printf("%d",dp[i]);

             else printf(" %d",dp[i]);

         }

         puts("");

     }

     return ;

 }

递推+lowbit+滚动数组

***********************************************************************************************************************************

【方法三】

http://m.blog.csdn.net/silence255713/article/details/77200056

巴特西

【（好题）组合数+Lucas定理+公式递推（lowbit+滚动数组）+打表找规律】2017多校训练七 HDU 6129 Just do it

最新文章

热门文章