team2012-E1-mysol-0001

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

{{{
/* 解题报告 //

给出一个图，n 个点，m 条有向边，每个点有个权值 p[i]
要求从 1 到 n，路径上权值的最小公倍数为 k 方案数
另外，在路径上每走一步，最小公倍数的值都必须增加

做法就是动态规划，记 dp[u][i] 为当前最小公倍数的值为 v，
在第 i 个点上的方案数为多少，很明显，有 dp[v][j] = sum(dp[u][i])
其中 v > u，lcm(u, p[j]) = v 且从 i 到 j 有边

直观上看，u 在 10 ^ 6 范围内，i 在 2000 范围内，状态总数有 2 * 10 ^ 9 个
实际上，并没有这么多，因为有一个很重要的剪枝：
如果 u 不是 k 的因数，则 dp[u][i] 无法最终转移到 dp[k][n]
因此可以舍弃所有不是 k 的因子的 u，使得 u 最多只有 O(sqrt(k)) 的级别
考虑到这个条件后，复杂度就只有 O(sqrt(k) * m) 了

另外方便起见，我的程序里使用了 map 来存储 dp 值

// By 猛犸也钻地 @ 2012.07.18 */
}}}

{{{
#include <cstdio>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;

typedef pair<int,int> PII;
typedef long long LL;
const int MOD = 1000000007;

int main(){
    int n,m,k,p[2001];
    while(scanf("%d%d%d",&n,&m,&k)==3){
        map<PII,int> dp;
        vector<int> e[2001];
        for(int x,y,i=1;i<=m;i++){
            scanf("%d%d",&x,&y);
            e[x].push_back(y);
        }
        for(int i=1;i<=n;i++) scanf("%d",p+i);
        if(k%p[1]==0) dp[PII(p[1],1)]=1;
        for(map<PII,int>::iterator c=dp.begin();c!=dp.end();++c){
            int src=c->first.first,x=c->first.second;
            for(size_t i=0;i<e[x].size();i++){
                int y=e[x][i];
                LL dst=src*1ll/__gcd(src,p[y])*p[y];
                if(dst>src && k%dst==0)
                    dp[PII(dst,y)]=(dp[PII(dst,y)]+c->second)%MOD;
            }
        }
        printf("%d\n",dp[PII(k,n)]);
    }
}
}}}

/* 解题报告 //
给出一个图，n 个点，m 条有向边，每个点有个权值 p[i]
要求从 1 到 n，路径上权值的最小公倍数为 k 方案数
另外，在路径上每走一步，最小公倍数的值都必须增加
做法就是动态规划，记 dp[u][i] 为当前最小公倍数的值为 v，
在第 i 个点上的方案数为多少，很明显，有 dp[v][j] = sum(dp[u][i])
其中 v > u，lcm(u, p[j]) = v 且从 i 到 j 有边
直观上看，u 在 10 ^ 6 范围内，i 在 2000 范围内，状态总数有 2 * 10 ^ 9 个
实际上，并没有这么多，因为有一个很重要的剪枝：
如果 u 不是 k 的因数，则 dp[u][i] 无法最终转移到 dp[k][n]
因此可以舍弃所有不是 k 的因子的 u，使得 u 最多只有 O(sqrt(k)) 的级别
考虑到这个条件后，复杂度就只有 O(sqrt(k) * m) 了
另外方便起见，我的程序里使用了 map 来存储 dp 值
// By 猛犸也钻地 @ 2012.07.18 */

#include <cstdio>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
typedef pair<int,int> PII;
typedef long long LL;
const int MOD = 1000000007;
int main(){
    int n,m,k,p[2001];
    while(scanf("%d%d%d",&n,&m,&k)==3){
        map<PII,int> dp;
        vector<int> e[2001];
        for(int x,y,i=1;i<=m;i++){
            scanf("%d%d",&x,&y);
            e[x].push_back(y);
        }
        for(int i=1;i<=n;i++) scanf("%d",p+i);
        if(k%p[1]==0) dp[PII(p[1],1)]=1;
        for(map<PII,int>::iterator c=dp.begin();c!=dp.end();++c){
            int src=c->first.first,x=c->first.second;
            for(size_t i=0;i<e[x].size();i++){
                int y=e[x][i];
                LL dst=src*1ll/__gcd(src,p[y])*p[y];
                if(dst>src && k%dst==0)
                    dp[PII(dst,y)]=(dp[PII(dst,y)]+c->second)%MOD;
            }
        }
        printf("%d\n",dp[PII(k,n)]);
    }
}