又是一套神题啊，来看看F题吧：
Problem F - Kitty's Game
[Description]
Kitty最近迷上了一款游戏
这个游戏有n个场景（编号1到n），而每个场景都有一个数值pi
当kitty进入场景i的时候她的分数将会变为lcm(x, pi)的分数
x为上个场景的得分，lcm(a, b)为a和b的最小公倍数
注意如果kitty前后两次的得分相同的话，她就会变得很生气
现在一开始kitty处于场景1，并且得到了p1的分数，现在问题来了：
挖掘机学校到底哪家强？（这哪冒出来的？！不是这个！）
她想到达场景n，并且最终累计得到k的分数，一共有多少条不同路径？
当且仅当一条路径上的边的序列不同时，我们认为是不同的路径（我感觉这句话没什么用，打上来嘛，你们自己体会哈）（这句不是我加的）
当然，不管怎么走，你都不能让kitty生气
[Input]
多组数据，对于每组数据，
第一行三个整数，n, m, k分别表示n个场景，m条边，最后达到的分数k
接下来m行，每行两个整数u, v，表示kitty可以从场景u走到场景v
最后一行p个整数，分别为每个场景的数值pi
[Output]
对于每组数据，输出一行一个整数，即不同路径数对1000000007取模后的结果
[Sample Input]
5 6 84
1 2
2 5
1 3
3 5
1 4
4 5
1 5 4 12 21
[Sample Output]
2
[Hint]
2 <= n <= 2000, 2 <= m <= 20000, 2 <= k <=
1 <= u, v <= n, u != v
1 <= pi <=
其实这道题很简单的：中国山东找蓝翔！
好吧，不水了。。。
这道题很明显的一点是,需要记录当前在i点时，当前得分为k时的方案数，才能继续向后递推。
那么现在问题来了：
k最大为
怎么办呢？
我们回过头来再看一看题意，我们就会惊奇滴发现：
所有合法的分数一定是K的因子。
理由：lcm(x,p[n])==k，x一定是k的因子。向前倒推，一定会有lcm(x',p[i])==x，故x'是x的因子，也就是k的因子。
我们再分析一下k的因子有多少个呢？
然后我们再一次惊奇滴发现：
当K为900000时，它的因子数目最多，为240个。
然后事情就好办了。
我们就可以将k的每一个因子分别标上号(如900000就从1-240分别对应一个因子)，就可以开到dp[2000+10][250+10]了。
开一个pos数组，pos[i]表示i这个数所对应的编号，其中i是当前k的一个因子。
开一个f数组，f[i]表示i这个编号所对应的数是多少。
我们每一次都先将k处理一下，得到一个k的因子与编号的映射，就可以得到：
用dp[i][j]表示当前在i号节点，已经得分的编号为j时的方案数。读入时反向加边，就可以得到转移方程：
dp[i][j]=sum{dp[k][l]}（(k,i)∈E&&lcm(l,p[i])==j&&j!=l）
然后dp就行了。
最开始想到dp的时候考虑了有环的情况，感觉不好处理。但后来又分析发现，环的存在并不影响答案。因为一个场景你不能在走第二次，直接忽略掉它就是了。
就这样，还是发一下代码：
预处理代码：
for(int i=1;i<=sqrt(k);i++)
{
if(k%i==0)
{
pos[i]=++cnt;
f[cnt]=i;
if(pos[k/i]==0){pos[k/i]=++cnt;f[cnt]=k/i;}
}
}
cnt初值为0。
记忆化搜索代码：
int dfs(int u,int pp)
{
int yy=pos[pp];
if(dp[u][yy]!=-1)return dp[u][yy];
if(u==1)return dp[u][yy]=0;//边界
int ans=0;
for(int i=head[u];i!=-1;i=e[i].next)
{
int v=e[i].v;
for(int j=1;j<=tt;j++)
{
int ret=lcm(f[j],pa[u]);
if(ret==pp&&ret!=f[j])
{
ans=(ans+dfs(v,f[j]))%1000000007;
}
}
}
return dp[u][yy]=ans;
}
边界为dp[1][pos[p[1]]]=1;
这道题就这样了。。。可怜少年老早以前看到这道题时惊为天人。。。