复习了一发FWT,发现还挺简单的。。。
没时间写了,就放一个博客吧:Great_Influence 的博客
注意这一句
本来应该是,变一下就是
然后就是板子了
好强。。
CODE
#include
using namespace std;
const int MAXS = 1const int MAXN = 20;
const int MAXM = 100005;
typedef long long LL;
int n, m, a[MAXM], bit[MAXS];
LL f[MAXS], dp[MAXS];
inline void FWT(LL arr[], int len, int flg) {
LL x, y;
for(int i = 2; i for(int j = 0; j for(int k = j; k x = arr[k], y = arr[k + i/2];
if(~flg) arr[k] = x + y, arr[k + i/2] = x - y;
else arr[k] = (x + y) >> 1, arr[k + i/2] = (x - y) >> 1;
}
}
char s[MAXM];
int main () {
scanf("%d%d", &n, &m);
for(int i = 1; i scanf("%s", s+1);
for(int j = 1; j a[j] = (a[j] }
for(int i = 1; i for(int s = 0; s >1] + (s&1);
for(int s = 0; s FWT(f, 1 for(int i = 0; i FWT(f, 1 LL ans = n*m;
for(int i = 0; i printf("%I64dn", ans);
}