2012-A3-0001
从 Trac 迁移的文章
这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。
原文章内容如下：
题意是在问有向图上的始于1至于n路径，路径上到某个点的得分是其所有前缀节点点权的LCM，且每个节点的得分不同，求出终点得分为k的路径数量。
由于每个节点的得分不同，所以不会经过同一个节点2次，否则不能保证LCM不同，故以LCM和节点作为状态是没有后效性的。
在计算数量是要保证在某个状态的数量已计算完全时再用它去更新别的状态，否则会使数量不对。
由于LCM随着路径必然单调严格递增，所以可以按照得分从小到大的顺序进行计算。
而且，后一个LCM得分是前一个倍数，所以路径不可能很长，否则会轻松突破k的限制，
所以加上某个LCM最终不能到达k的话就不必更新它，这个优化应该可以大大减少状态的数量，
这样 最大的状态数是n * (k的因子)，但是每个点的点权是固定的，所以这个几乎是不可能达到的。
{{{
#include<cstdio>
#include<map>
#include<cstring>
using namespace std;
typedef unsigned num;
const num mo = 1000000007;
num v[20480],nx[20480],ptr[2048],p[2048];
num gcd(num a,num b){
for(num t;b;b = t)
{t = a% b;a = b;}
return a;
}
map<num,num> sat;
int main(){
for(num n,m,k;3==scanf("%u%u%u",&n,&m,&k);){
memset(ptr,0,n+1<<2);
for(num i=1,u;i<=m;++i){
scanf("%u%u",&u,v+i);
nx[i]=ptr[u];ptr[u]=i;
}
for(num i=1;i<=n;++i)
scanf("%u",p+i);
sat.clear();
sat[p[1]<<11|1]=1;
for(__typeof(sat.end()) it = sat.begin();it!=sat.end();++it){
num z = it ->first>>11, u = it->first&2047u;
for(num x = ptr[u],t;x;x = nx[x]){
t = p[v[x]] / gcd(p[v[x]],z);
if(t==1 || k%t%z)continue;
t = t*z<<11|v[x];
sat[t] =(sat[t]+it->second)%mo;
}
}
printf("%u\n",sat[k<<11|n]);
}
return 0;
}
}}}题意是在问有向图上的始于1至于n路径，路径上到某个点的得分是其所有前缀节点点权的LCM，且每个节点的得分不同，求出终点得分为k的路径数量。
由于每个节点的得分不同，所以不会经过同一个节点2次，否则不能保证LCM不同，故以LCM和节点作为状态是没有后效性的。
在计算数量是要保证在某个状态的数量已计算完全时再用它去更新别的状态，否则会使数量不对。
由于LCM随着路径必然单调严格递增，所以可以按照得分从小到大的顺序进行计算。
而且，后一个LCM得分是前一个倍数，所以路径不可能很长，否则会轻松突破k的限制，
所以加上某个LCM最终不能到达k的话就不必更新它，这个优化应该可以大大减少状态的数量，
这样 最大的状态数是n * (k的因子)，但是每个点的点权是固定的，所以这个几乎是不可能达到的。
#include<cstdio>
#include<map>
#include<cstring>
using namespace std;
typedef unsigned num;
const num mo = 1000000007;
num v[20480],nx[20480],ptr[2048],p[2048];
num gcd(num a,num b){
for(num t;b;b = t)
{t = a% b;a = b;}
return a;
}
map<num,num> sat;
int main(){
for(num n,m,k;3==scanf("%u%u%u",&n,&m,&k);){
memset(ptr,0,n+1<<2);
for(num i=1,u;i<=m;++i){
scanf("%u%u",&u,v+i);
nx[i]=ptr[u];ptr[u]=i;
}
for(num i=1;i<=n;++i)
scanf("%u",p+i);
sat.clear();
sat[p[1]<<11|1]=1;
for(__typeof(sat.end()) it = sat.begin();it!=sat.end();++it){
num z = it ->first>>11, u = it->first&2047u;
for(num x = ptr[u],t;x;x = nx[x]){
t = p[v[x]] / gcd(p[v[x]],z);
if(t==1 || k%t%z)continue;
t = t*z<<11|v[x];
sat[t] =(sat[t]+it->second)%mo;
}
}
printf("%u\n",sat[k<<11|n]);
}
return 0;
}