BZOJ 1172 Balkan2007 Dream

BZOJ 1172 Balkan2007 Dream

提示：
1. 一个乘积如果要判断整除 k $k$ ，我们需要记录哪些量
2. 每一行最多取两个可以单独抽出来做 dp$dp$

#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cassert>
#include <cstdio>
#include <vector>
#include <cmath>
#include <queue>
#include <map>using namespace std;
const int maxn = 210;int n , m , k , l , cnt;
int d[maxn][maxn] , t[maxn] , now[maxn] , g[maxn][11000];
map<int , int> dic; int redic[maxn] , trans[maxn][maxn];int main(int argc, char *argv[]) {cin>>n>>m>>k>>l;for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) scanf("%d" , g[i] + j);for(int i=1;i<=k;i++) if(k % i == 0) redic[++cnt] = i , dic[i] = cnt;for(int i=1;i<=cnt;i++) for(int j=1;j<=cnt;j++) trans[i][j] = dic[__gcd((int)((1LL*redic[i]*redic[j])%k) , k)];d[0][1] = 1;for(int i=1;i<=n;i++){memset(t , 0 , sizeof t);for(int j=1;j<=m;j++) t[dic[__gcd(g[i][j] , k)]]++;memcpy(now , t , sizeof t);if(1 < i && i < n) {for(int j=1;j<=cnt;j++) for(int k=1;k<=cnt;k++) (now[trans[j][k]] += t[j]*t[k]) %= l;for(int j=1;j<=cnt;j++) (now[trans[j][j]] -= t[j]) %= l;}for(int j=1;j<=cnt;j++) for(int k=1;k<=cnt;k++) (d[i][trans[j][k]] += d[i-1][j]*now[k]) %= l;}cout<<(d[n][cnt]+l)%l<<endl;return 0;
}

di $d_i$ 记录目前 gcd(乘积,k)==i $gcd(乘积 , k) == i$ 的方案数 ， i $i$ 这个值的数量级是102$10^2$级别的
那么我们就可以把相同 gcd $gcd$ 值的数归类，那么整体复杂度就降到了 106 $10^6$ 级别。