A – Sticks
因为POJ出了点问题，于是用了洛谷上的同位题【P1120 小木棍】进行测评。进阶剪枝经典例题，里面涉及到了很多剪枝思想，以下一一注释在程序里面。
namespace lovelive{
int ai[100],n,sums,nxt[100];
bool used[100];
bool dfs(int cur,int tar,int fin,int r){
//cur : 当前已经拼接的长度
//tar : 目标长度
//fin : 已经拼接完成的棍子数量
//r : 寻找答案范围的最右端（从小到大排序的）
if(cur==tar){
cur = 0; fin++; r = n; // 注意重新开始拼接的时候
// 也要重置搜寻合适木棍的最右端
if(tar*fin==sums)return true;
}
for(int i=upper_bound(ai+1,ai+r+1,tar-cur)-ai-1;i>0;i--){
// 【排除等效冗余】既然比ai[r]大的都考虑过了
// 限制了r也就减少了冗余搜索操作
if(!used[i]){
used[i]=true;
if(dfs(cur+ai[i],tar,fin,i-1))return true;
used[i]=false;
if(tar-cur==ai[i]) return false;
// 【可行性剪枝】选中这根棍子就可以凑成一整根
// 如果当前的棍子选中了却无法凑出剩下的棍子
// 这之前的拼法就有问题，用其他的棍子拼完当前也无济于事
if(cur==0)return false;
// 【可行性剪枝】与上面的问题差不多，
// 这跟棍子在完全为空的棍子组合里用不到，
// 也别指望它能在别的有其他棍子的组合里用到
i=nxt[i];
// 【排除等效冗余】相同的木棍结果也是一样的
}
}
return false;
}
bool main(){
cin>>n;if(!n)return false;
sums = 0;
for(int i=1;i<=n;i++){
cin>>ai[i];sums += ai[i];
}
sort(ai+1,ai+n+1); //【顺序剪枝】
memset(used,0,sizeof(used));
for(int i=1;i<=n;i++){
if(ai[i]==ai[i-1])nxt[i] = nxt[i-1];
else nxt[i] = i;
//【排除等效冗余】加快寻找下一个方案的速度
}
// 【可行性剪枝】但有些不一样，
// 因为直接接成一整根一定可行，就不用更麻烦的方法考虑。
for(int parts=sums/ai[n]+1,tar;parts>1;parts--){
if(sums % parts)continue;
tar = sums / parts;
if(dfs(0,tar,0,n)){
cout<<tar<<endl;;
return true;
}
}
cout<<sums<<endl;
return true;
}
}B – 矩阵乘法
见C – 矩阵快速幂。
C – 矩阵快速幂
之前就做过ZJUT2022入门题单Week3 – L – Matrix Power Series了，所以这题看上去就像是只因本功。但矩阵快速幂有意思的在后面，所以告诫自己稍安勿躁，打好基础为重。
namespace lovelive{
typedef long long VAL;
typedef vector<vector<VAL>> MAT;
const int MOD = 1e9+7;
int matn,m;
MAT honoka,kotori,umi;
MAT build(int spec=0){
MAT res;
res.resize(matn+1);
for(int i=1;i<=matn;i++){
res[i].resize(matn+1);
res[i][i] = spec;
}
return res;
}
MAT add(MAT a,MAT b){
MAT res = a;
for(int i=1;i<=matn;i++){
for(int j=1;j<=matn;j++){
res[i][j] += b[i][j];
}
}
return res;
}
MAT mul(MAT a,MAT b){
MAT res = build();
for(int i=1;i<=matn;i++){
for(int j=1;j<=matn;j++){
for(int k=1;k<=matn;k++){
res[i][j] += a[i][k] * b[k][j];
res[i][j] %= MOD;
}
}
}
return res;
}
MAT qpow(MAT a,int pown){
MAT base = a, res = build(1);
while(pown){
if(pown&1)res = mul(res,base);
base = mul(base,base);
pown >>= 1;
}
return res;
}
void input(MAT& ai){
for(int i=1;i<=matn;i++){
for(int j=1;j<=matn;j++){
cin>>ai[i][j];
}
}
}
void output(MAT ai){
for(int i=1;i<=matn;i++){
for(int j=1;j<=matn;j++){
cout<<ai[i][j]<<" ";
}
cout<<endl;
}
}
void main(){
cin>>matn>>m;
umi = build();
//kotori = build();
input(umi);
//input(kotori);
//honoka = mul(umi,kotori);
honoka = qpow(umi,m);
output(honoka);
}
}D – 233 Matrix
矩阵快速幂应用之关键，在于原矩阵到目标矩阵之间关系矩阵，因而找出关系矩阵，并且对该关系矩阵进行快速幂，就有机会在得到答案的同时大幅度提高效率。
namespace lovelive{
typedef long long VAL;
typedef vector<vector<VAL>> MAT;
const int MOD = 10000007;
int matn,m;
MAT honoka,kotori,umi;
/*矩阵运算函数与B、C题同，
注意行列不统一，但符合计算条件的话，
可以等效于用不到的单元格全都是0.*/
bool main(){
if(!(cin>>matn>>m))return false;
matn += 2;
kotori = build();
kotori[1][1] = 233;
for(int i=2;i<matn;i++)cin>>kotori[1][i];
kotori[1][matn] = 3;
umi = build(1);
umi[1][1] = 10;
umi[1][matn] = 0;
umi[matn][1] = 1;
for(int i=2;i<matn;i++){
umi[1][i] = 1;
for(int j=2;j<i;j++)umi[j][i]=1;
}
honoka = mul(kotori,qpow(umi,m));
cout<<honoka[1][matn-1]<<endl;
return true;
}
}E – Fast Matrix Calculation
几十乘几十的矩阵进行暴力运算，计算机就有点受不了了（高代朱妈语），更别说直接 $A \centerdot B$ 的可能会上千的矩阵了。与其真的如朱妈所言把矩阵的简化运算性质转移到代码中，不如对于计算本身做一些微操。注意到对于矩阵，虽然交换律不成立，但结合律仍旧可用。那么就这样吧！由于$k \geq 6$，六乘六的矩阵总比上千的好太多！
$$
(A \cdot B) \cdot (A \cdot B)^{(N \cdot N – 2)} \cdot (A \cdot B) = A \cdot (B \cdot A)^{(N \cdot N – 1)} \cdot B
$$
因为涉及到了非方阵矩阵的运算，所以把矩阵的相关算法做了一些修改，就不能被省略了。
namespace lovelive{
typedef long long VAL;
struct MAT{
int n,m;
vector<vector<VAL>> ai;
MAT(int ni=0,int mi=-1){
if(mi==-1)mi=ni;
n = ni;m = mi;
if(ni==-1)return;
ai.resize(n+1);
for(int i=1;i<=n;i++){
ai[i].resize(m+1);
}
}
}ERR(-1);
const int MOD = 6;
int n,m;
MAT honoka,kotori,umi;
MAT build(int n,int m,int spec=0){
MAT res(n,m);
for(int i=1;i<=min(n,m);i++){
res.ai[i][i] = spec;
}
return res;
}
MAT add(MAT a,MAT b){
MAT res = a;
for(int i=1;i<=a.n;i++){
for(int j=1;j<=a.m;j++){
res.ai[i][j] += b.ai[i][j];
}
}
return res;
}
MAT mul(MAT a,MAT b){
MAT res(a.n,b.m);
for(int i=1;i<=a.n;i++){
for(int j=1;j<=b.m;j++){
for(int k=1;k<=a.m;k++){
res.ai[i][j] += a.ai[i][k] * b.ai[k][j];
res.ai[i][j] %= MOD;
}
}
}
return res;
}
MAT qpow(MAT a,int pown){
MAT base = a, res = build(a.n,a.n,1);
while(pown){
if(pown&1)res = mul(res,base);
base = mul(base,base);
pown >>= 1;
}
return res;
}
void input(MAT& a){
for(int i=1;i<=a.n;i++){
for(int j=1;j<=a.m;j++){
cin>>a.ai[i][j];
}
}
}
bool main(){
cin>>n>>m;
if(!n||!m)return false;
kotori = build(n,m);
input(kotori);
umi = build(m,n);
input(umi);
honoka = mul(umi,kotori);
honoka = qpow(honoka,n*n-1);
honoka = mul(kotori,honoka);
honoka = mul(honoka,umi);
VAL ans=0;
for(int i=1;i<=honoka.n;i++){
for(int j=1;j<=honoka.m;j++){
ans += honoka.ai[i][j];
}
}
cout<<ans<<endl;
return true;
}
}F – 世界冰球锦标赛
将原规模为$2^{40}$的问题折半为两个$2^{20}$的子问题，最后并在一起考虑。因为一个奇怪的long long卡了半天。
namespace lovelive{
LL ai[41],bi[1050000],ci[1050000];
int n;
long long cntb,cntc,ans,tmp,tmp2,m;
void main(){
cin>>n>>m;
for(int i=0;i<n;i++){
cin>>ai[i];
}
cntb=cntc=0;//一场都不看也是一种方案
for(int i=0;i<(1<<((n+1)/2));i++){
tmp=i;tmp2=0;
for(int j=0;j<(n+1)/2;j++){
if((1<<j)&i)tmp2 += ai[j];
}
if(tmp2<=m){
bi[++cntb]=tmp2;
}
}
for(int i=0;i<(1<<(n/2));i++){
tmp=i;tmp2=0;
for(int j=0;j<n/2;j++){
if((1<<j)&i)tmp2 += ai[j+(n+1)/2];
}
if(tmp2<=m){
ci[++cntc]=tmp2;
}
}
sort(bi+1,bi+cntb+1);
sort(ci+1,ci+cntc+1);
ans = 0;
for(int i=1;i<=cntb;i++){
cout<<ci[upper_bound(ci+1,ci+cntc+1,min(m-bi[i],m))-ci-1]<<endl;
ans += max((int)(upper_bound(ci+1,ci+cntc+1,min(m-bi[i],m))-ci-1),0);
}
cout<<ans<<endl;
}
}G – 4 Values whose Sum is 0
折半处理问题，用双指针减少寻找答案复杂度（回想起了以前肝力扣周赛天天双指针的痛）。注意可能会存在多种方案效果相同。
namespace lovelive{
LL ai[4][4005],bi[16000005],ci[16000005];
int n,bcnt,ccnt,bpos,cpos1,cpos2,ans;
void main(){
cin>>n;bcnt=0;ccnt=0;
for(int i=1;i<=n;i++){
for(int j=0;j<4;j++){
cin>>ai[j][i];
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
bi[++bcnt]=ai[0][i]+ai[1][j];
}
}
sort(bi+1,bi+bcnt+1);
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
ci[++ccnt]=ai[2][i]+ai[3][j];
}
}
sort(ci+1,ci+ccnt+1);
cpos1=cpos2=ccnt;ans=0;
for(bpos=1;bpos<=bcnt;bpos++){
while(cpos1&&bi[bpos]+ci[cpos1]>0)cpos1--;
while(cpos2&&bi[bpos]+ci[cpos2]>=0)cpos2--;
ans += cpos1-cpos2;
}
cout<<ans<<endl;
}
}H – Coin Change (IV)
跟上面几道题类似的思路，不同的是这里用到了三进制（
//输出在lovelive空间外面进行，该函数不会在标准输出输出任何东西
namespace lovelive{
LL ai[20],bi[60000],ci[60000],m,tmp2;
int n,bcnt,ccnt,bpos,cpos1,cpos2,ans,mid;
int main(){
cin>>n>>m;bcnt=0;ccnt=0;
for(int i=1;i<=n;i++){
cin>>ai[i];
}
mid = (n+1)/2;
//出现了，是三进制！
for(int i=0,tar=pow(3,mid),j,tmp;i<tar;i++){
j = 1;tmp = i;tmp2 = 0;
while(tmp){
tmp2 += ai[j] * (tmp % 3);
tmp /= 3; j++;
}
bi[++bcnt] = tmp2;
}
sort(bi+1,bi+bcnt+1);
for(int i=0,tar=pow(3,n/2),j,tmp;i<tar;i++){
j = mid + 1;tmp = i;tmp2 = 0;
while(tmp){
tmp2 += ai[j] * (tmp % 3);
tmp /= 3; j++;
}
ci[++ccnt] = tmp2;
}
sort(ci+1,ci+ccnt+1);
cpos1=cpos2=ccnt;ans=0;
for(bpos=1;bpos<=bcnt;bpos++){
while(cpos1&&bi[bpos]+ci[cpos1]>m)cpos1--;
while(cpos2&&bi[bpos]+ci[cpos2]>=m)cpos2--;
ans += cpos1-cpos2;
}
return ans;
}
}I – Subsequence
由于数据集全是正数，可以保证前缀和严格单调，此时可以上双指针。
namespace lovelive{
int n,l,r,ans;
LL m,ai[100005],sumi[100005];
void main(){
cin>>n>>m;sumi[0]=0;ans=n;
for(int i=1;i<=n;i++){
cin>>ai[i];
sumi[i] = sumi[i-1]+ai[i];
}
if(sumi[n]<m){
cout<<0<<endl;
return;
}
for(l=r=1;l<=n;l++){
while(r<=n&&sumi[r]-sumi[l-1]<m)r++;
if(r>n)break;
ans = min(ans,r-l+1);
}
cout<<ans<<endl;
}
}J – Graveyard Design
注意到又是连续序列并且前缀和能保持严格单调。双指针！
namespace lovelive{
long long n,l,r,sumi,tar;
vector<pair<int,int>> ansi;
void main(){
cin>>n;sumi = 0;
tar = sqrt(n);
for(l=r=1;l<=tar;l++){
while(r<=tar&&sumi<n){
sumi += r*r;
r++;
}
if(sumi==n)ansi.push_back(make_pair(l,r));
sumi-=l*l;
}
cout<<ansi.size()<<endl;
for(int i=0;i<ansi.size();i++){
cout<<ansi[i].second-ansi[i].first;
for(int j=ansi[i].first;j<ansi[i].second;j++){
cout<<" "<<j;
}
cout<<endl;
}
}
}K – 斐波那契数列
如果能把D题的关系矩阵想清楚的话，斐波那契的关系矩阵就变得十分easy了。代码用的是E题的模板。
namespace lovelive{
const int MOD = 1e9+7;
long long ni;
void main(){
cin>>ni;
if(ni==1){
cout<<1<<endl;return;
}
ni-=2;
kotori = build(2);
kotori.ai[1][1] = kotori.ai[1][2] = 1;
//output(kotori);
umi = build(2);
umi.ai[1][1] = umi.ai[1][2] = umi.ai[2][1] = 1;
//output(qpow(umi,ni));
honoka = mul(kotori,qpow(umi,ni));
cout<<honoka.ai[1][1]<<endl;
return ;
}
}
