[Balkan2007]Dream

Time Limit:10000MS Memory Limit:165536K
Total Submit:3 Accepted:2
Case Time Limit:1000MS

Description

给出N行M列的数字矩阵.
从第一行的数列中选一个数字,从最后一行的数列中选一个数字.
从其它的行中,每行取一到两个数.
将取出来的数字相乘,希望其可以被K整除.
你只需要输出结果Mod L的值.

Input

第一行给出N,M
第二行给出K,L
下面有N行M列,用于描述数字矩阵
其值在[1,1000000]各不相同.

N在[3,200]
M在[3,10000]
K在[2,200000]
L在[2,30000]

Output

取法总数Mod L

Sample Input

Sample Output

Hint

以下为样例的12种取法.
5 2 1
2 1 2
3 7 4
Pic. 1

5 2 1
2 1 2
3 7 4
Pic. 2

5 2 1
2 1 2
3 7 4
Pic. 3

5 2 1
2 1 2
3 7 4
Pic. 4

5 2 1
2 1 2
3 7 4
Pic. 5

5 2 1
2 1 2
3 7 4
Pic. 6

5 2 1
2 1 2
3 7 4
Pic. 7

5 2 1
2 1 2
3 7 4
Pic. 8

5 2 1
2 1 2
3 7 4
Pic. 9

5 2 1
2 1 2
3 7 4
Pic. 10

5 2 1
2 1 2
3 7 4
Pic. 11

5 2 1
2 1 2
3 7 4
Pic. 12

Source
好吧这题不算难。。但是挺有意思的。。一开始我想的是记录对K的每种余数有多少个，但那样显然太SB了。。。。后来我感觉这样很浪费啊。。实际上当前唯一有用的信息是与K的最大公约数！！。。。而K的约数不会超过300个（还记得反素数那个题目么。。特意算了下）。。所以毫无压力的就可以A掉了。。。需要与处理一下两个约数相乘之后与K的最大公约数。。。。以及每个数与K的最大公约数（类似筛法的搞）。。。
另外最近一直在看TopCoder SRM Level 3的题目。。有了不少感触啊。。有时间写个表格饿囧。。
Code：

#include<cstdio>#include<algorithm>#include<iostream>#define rep(i,n) for(int i=0;i<n;i++)using namespace std;const int maxn=200,maxm=10000,maxk=200000,maxw=1000000,maxs=300;typedef long long ll;int mod,k,n,m,Div[maxw+1],L[maxs],dn=0,Next[maxs][maxs];inline void Add(int&x,int c){x+=c;x%=mod;}inline void Mult(int&x,int c){x*=c;x%=mod;}int Dp[2][maxs],c1[maxs],c2[maxs];int main(){ //freopen("in","r",stdin); scanf("%d%d%d%d",&n,&m,&k,&mod); for(int i=1;i<=k;i++)if(k%i==0)L[dn++]=i; rep(i,dn)rep(j,dn) for(int k=dn-1;k>=0;k–)if(ll(L[i])*L[j]%L[k]==0) { Next[i][j]=k;break; } rep(i,dn) { int x=L[i]; for(int j=x;j<=maxw;j+=x)Div[j]=i; } int x,now=0,old=1; rep(i,m)scanf("%d",&x),Add(Dp[now][Div[x]],1); rep(i,n-1) { swap(now,old);memset(Dp[now],0,sizeof Dp[now]); memset(c1,0,sizeof c1); memset(c2,0,sizeof c2); rep(i,m)scanf("%d",&x),Add(c1[Div[x]],1); memcpy(c2,c1,sizeof c1); if(i!=n-2) rep(a,dn)rep(b,a+1) if(a!=b)Add(c2[Next[a][b]],c1[a]*c1[b]*2); else Add(c2[Next[a][b]],c1[a]*(c1[a]-1)); rep(a,dn)rep(b,dn) Add(Dp[now][Next[a][b]],Dp[old][a]*c2[b]); } printf("%dn",Dp[now][dn-1]);}123 312 1005 2 12 1 23 7 4