前言

你有没有试过以下几种情况：

• 代码在别的OJ上能过，在洛谷上就T了
• 你的代码和同学的几乎相同，但他的AC了，你的却TLE了

遇到这些情况，你可能要花上一个多小时才能解决，甚至难以解决，将问题一直搁置。不过，下ma下面有一种方法，可以让你的代码快许多。如果你有上面的第二种情况，那用这个方法，大概率能过。

怎么办

比如这一题：P6097 【模板】子集卷积

TLE代码

#include<bits/stdc++.h>
using namespace std;
int n;
long long a[1<<21],b[1<<21],c[1<<21],ct[1<<21],ans[1<<21],ta[22][1<<21],tb[22][1<<21];
long long mod=1e9+9;
void fwt(long long *w,long long fl){for(int s=2;s<=(1<<n);s<<=1){int mid=s>>1;for(int v=0;v<(1<<n);v+=s){for(int i=0;i<mid;i++){w[v+mid+i]=(w[v+mid+i]+fl*w[v+i]+mod)%mod;}}}
}
int main()
{scanf("%d",&n);for(int i=1;i<(1<<n);i++){ct[i]=ct[i-(i&(-i))]+1;}for(int i=0;i<(1<<n);i++){scanf("%lld",&a[i]);ta[ct[i]][i]=a[i];}for(int i=0;i<(1<<n);i++){scanf("%lld",&b[i]);tb[ct[i]][i]=b[i];}for(int i=0;i<=n;i++){fwt(ta[i],1);fwt(tb[i],1);}for(int i=0;i<=n;i++){for(int j=0;j<=i;j++){for(int k=0;k<(1<<n);k++){c[k]=(c[k]+ta[j][k]*tb[i-j][k]%mod)%mod;}}fwt(c,-1);for(int j=0;j<(1<<n);j++){if(ct[j]==i) ans[j]=c[j];c[j]=0;}}for(int i=0;i<(1<<n);i++){printf("%lld ",ans[i]);}return 0;
}

这个方法是正解，代码也没有太大的问题，但就是TLE了。

但是，如果我在$mod$的变量定义前加上$const$，也就是在第五行行首加上$const$，就能AC了。

AC代码

#include<bits/stdc++.h>
using namespace std;
int n;
long long a[1<<21],b[1<<21],c[1<<21],ct[1<<21],ans[1<<21],ta[22][1<<21],tb[22][1<<21];
const long long mod=1e9+9;
void fwt(long long *w,long long fl){for(int s=2;s<=(1<<n);s<<=1){int mid=s>>1;for(int v=0;v<(1<<n);v+=s){for(int i=0;i<mid;i++){w[v+mid+i]=(w[v+mid+i]+fl*w[v+i]+mod)%mod;}}}
}
int main()
{scanf("%d",&n);for(int i=1;i<(1<<n);i++){ct[i]=ct[i-(i&(-i))]+1;}for(int i=0;i<(1<<n);i++){scanf("%lld",&a[i]);ta[ct[i]][i]=a[i];}for(int i=0;i<(1<<n);i++){scanf("%lld",&b[i]);tb[ct[i]][i]=b[i];}for(int i=0;i<=n;i++){fwt(ta[i],1);fwt(tb[i],1);}for(int i=0;i<=n;i++){for(int j=0;j<=i;j++){for(int k=0;k<(1<<n);k++){c[k]=(c[k]+ta[j][k]*tb[i-j][k]%mod)%mod;}}fwt(c,-1);for(int j=0;j<(1<<n);j++){if(ct[j]==i) ans[j]=c[j];c[j]=0;}}for(int i=0;i<(1<<n);i++){printf("%lld ",ans[i]);}return 0;
}

跑得快了许多。

后记

这个问题我之前就遇到过，但一直没有在意。直到今天我调这道题，调了半个多小时才发现这里的问题。我觉得如果不知道这一点，可能还要浪费更多的时间。

有时候不加$const$就会TLE，加上就AC了。在洛谷上会这样，但在本地，不管加不加$const$，跑的时间都差不多。