SPOJ2829TLETimeLimitExceeded题解及优化方法

题目链接——SPOJ

题目链接——洛谷

problem

给出n，m和一个长度为n的数列c。求有多少个数列a满足以下条件：

• \(1\le a_i <2^m\)


• \(a_i\&a_{i-1}=0\)


• \(c_i\nmid a_i\)

答案读对\(1000000000\)取模。

solution

用\(f[t][i]\)表示长度为t且以i结尾的满足条件的数列的数量。\(f[t][i]=\sum\limits_{j,j\&i=0}f[t-1][j]\)

观察\(j\&i=0\)这个限制，其实等价于\(i\&(\sim j)=i\)。所以每次处理完之后，将答案的下标与自己的补集交换，然后就成了枚举超集。用\(FMT\)优化即可。复杂度\(\Theta(nm2^m)\)

这样处理完了前两个限制，对于第三个限制，每次处理完之后将下标\(c_i\)倍数的答案变为0即可。

code

/*
* @Author: wxyww
* @Date: 2019-12-15 09:58:26
* @Last Modified time: 2019-12-15 10:11:19
*/
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
typedef long long ll;
const int N = 1 <<20,mod = 1000000000;
ll read() {
ll x = 0,f = 1;char c = getchar();
while(c <&＃39;0&＃39; || c > &＃39;9&＃39;) {
if(c == &＃39;-&＃39;) f = -1; c = getchar();
}
while(c >= &＃39;0&＃39; && c <= &＃39;9&＃39;) {
x = x * 10 + c - &＃39;0&＃39;; c = getchar();
}
return x * f;
}
int f[N],a[N];
int main() {
int T = read();
while(T--) {
int n = read(),m = read();
int LIM = (1 < memset(f,0,sizeof(f));
f[0] = 1;
for(int i = 1;i <= n;++i) a[i] = read();
for(int i = 1;i <= n;++i) {
for(int j = 0;j <= LIM;j += 2) swap(f[j],f[j ^ LIM]);
for(int j = 0;j for(int k = 0;k <= LIM;++k) {
if(!(k >> j & 1)) f[k] += f[k | (1 < }
}
for(int j = 0;j <= LIM;j += a[i]) f[j] = 0;
}
ll ans = 0;
for(int i = 0;i <= LIM;++i) ans += f[i],ans %= mod;
printf("%lld\n",ans);
}
return 0;
}