[Codeforces 674F] Bears and Juice dp+巧妙的meet in the middle优化
题解：此题是最大值问题，而且又有"最优"这样的字眼，考虑用dp求解，
考虑最优策略，无需关注每一次每个选择具体是什么样的，
因为是最优，所以每轮游戏中， 不同的被ban掉的集合所对应的可能的a值集合应该不存在交集， 否则就不符合最优的性质了。
设dp[i][j]表示还能进行i轮游戏，还能允许j只熊喝醉的情况下的最大的R值，
根据上面的性质，可以通过枚举这一轮喝醉的熊的数量得到dp方程：
dp[i][j]=sigma(C(n+j-p,k)*dp[i-1][j-k]) (k=0...j)
而边界状态是：dp[0][i]=1 (i=0....p).
这样，我们就得到了一种复杂度为O(p^2*q)的做法，
但是p=130，q=2*10^6，这样的做法显然还需要改进。
于是考虑dp方程的优化，考虑构建矩阵，
按照预处理出的组合数，构造出p*p的矩阵，
这样就可以通过矩阵乘法实现dp[i]到dp[i+1]的转移，
但是这样做无法得到题目所需要的对于每个i的答案，
如果对于每个i分别进行这样的矩阵乘法，可以做到一次计算O(p^3logq).
其实这是很优的一个复杂度，但是由于我们需要dp数组的中间值计算答案，
直接进行矩阵乘法实际上是不可行的。
类似分段打表的思想，考虑meet in the middle，
我们考虑每隔q^k个位置计算一次dp数组的值，
因为连续，所以可以干掉矩阵快速幂的log，
这样的复杂度就是O(q^(1-k)*p^3).
然后对于每一段内部，可以发现对于mod q^k相同的位置，
由之前算好的部分的dp值转移到这个位置的dp值系数是恒定的，
于是O(q^k*p^2)计算出这个系数后，根据这个系数可以进行O(p)的转移与计算。
可以发现当k=2/3时，可以取得最优复杂度为O(q^1/3*logq*p^3)，从而实现了优化。
实现过程中，可以将q^k设为2^14以简化实际过程中的运算。
ORZ 当场通过推式子切掉此题的JHR大佬！！！
Code：
#include <bits/stdc++.h>
#define uint unsigned int
#define siz 16384
using namespace std;
struct mat
{uint p[131][131];
uint sz;
mat operator * (mat &b)
{mat ans;
ans.sz=sz;
uint i,j,k;
for (i=0;i<=sz;i++)
{for (j=0;j<=sz;j++)
{ans.p[i][j]=0;
for (k=0;k<=sz;k++)
{ans.p[i][j]+=p[i][k]*b.p[k][j];}
}
}
return ans;
}
}m[151];
uint c[151][151];//c[i][j]=C(n-p+i,j)
uint dp[siz+1][151];
inline uint gcd(uint a,uint b)
{while (a%b!=0)
{uint t=a;a=b;b=t%b;}
return b;
}
inline uint cal(uint n,uint m)
{uint a[151],i,j;
for (i=1;i<=m;i++) a[i]=n-i+1;
for (i=1;i<=m;i++)
{uint tp=i;
for (j=1;j<=m;j++)
{if (tp==1) {break;}
uint t=gcd(tp,a[j]);
tp/=t;a[j]/=t;
}
}
uint ans=1;
for (i=1;i<=m;i++) ans*=a[i];
return ans;
}
int main (){
uint i,j,k,n,p,q;
cin>>n>>p>>q;
p=min(p,n-1);
for (i=0;i<=p;i++)
{for (j=0;j<=i;j++)
{c[i][j]=cal(n-p+i,j);}
}
m[0].sz=m[1].sz=p;
for (i=0;i<=p;i++) m[0].p[i][i]=1;
for (i=0;i<=p;i++)
{for (j=0;j<=i;j++)
{m[1].p[i-j][i]=c[i][j];}
}
for (i=1;i<siz;i*=2)
{m[1]=m[1]*m[1];}
for (i=2;i<=q/siz;i++)
{m[i]=m[1]*m[i-1];}
for (i=0;i<=p;i++)
{dp[0][i]=1;}
for (i=1;i<siz;i++)
{for (j=0;j<=p;j++)
{for (k=0;k<=j;k++)
{dp[i][j]+=dp[i-1][j-k]*c[j][k];}
}
}
uint res=0;
for (i=1;i<=q;i++)
{uint rm=i%siz;
uint bel=i/siz;
uint ans=0;
for (j=0;j<=p;j++)
{ans+=m[bel].p[j][p]*dp[rm][j];}
res+=(ans^i);
}
cout<<res<<endl;
return 0;
}
UPD:还是推式子大法好，296ms就A了，
而上面的代码因为常数巨大，要998ms，还算同种做法中跑得快的。
查看7道真题和解析