team2012-F3-sol-0001

从 Trac 迁移的文章

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

原文章内容如下：

{{{
题意：给定一个有向图，每个节点一个权值。从起点出发，每到一个节点分数变为当前分数和节点权值的最小公倍数，且分数不能不变，问走到最后一个节点且分数是k的方案数。
解法：设F[i][s]为走到第i个节点，分数为s的方案数，则通过有向图上的边(i,j)可以转移到F[j][S]，且S>s。不过由于k太大，无法直接表示。
考虑每次都变为当前分数和节点权值的最小公倍数，即每次分数变为整数倍，且最后分数为k，所以中间所有可行状态的分数均为k的因子
只记录这些状态即可，状态数变为n*sqrt(k)。
}}}
{{{
#include <iostream>
#include <vector>
#include <map>
#include <cstring>

using namespace std;

typedef long long LL;

const int MOD = 1000000007;
int n, m, k, p[2002];
int f[2002][2002];
vector<int> conn[2002];
vector<int> fact;
map<int, LL> num_fact;

LL gcd(LL a, LL b)
{
    while(b)
    {
        LL c = a % b;
        a = b;
        b = c;
    }
    return a;
}

LL lcm(LL a, LL b)
{
    return a / gcd(a, b) * b;
}

int main()
{
    while(cin>>n>>m>>k)
    {
        for(int i=1;i<=n;i++)
            conn[i].clear();
        for(int i=1;i<=m;i++)
        {
            int a, b;
            cin>>a>>b;
            conn[a].push_back(b);
        }
        for(int i=1;i<=n;i++)
            cin>>p[i];
        fact.clear();
        num_fact.clear();
        for(int i=1;i<=k;i++)
            if(k%i==0)
            {
                num_fact[i] = fact.size();
                fact.push_back(i);
            }
        if(num_fact.count(p[1]) == 0)
        {
            cout<<0<<endl;
            continue;
        }
        int st = num_fact[p[1]];
        memset(f, 0, sizeof(f));
        f[1][st] = 1;
        for(int i=st;i<fact.size();i++)
        {
            int fact_now = fact[i];
            for(int j=1;j<=n;j++)
                if(f[j][i])
                {
                    for(int k=0;k<conn[j].size();k++)
                    {
                        int v = conn[j][k];
                        LL next_fact = lcm(p[v], fact_now);
                        if(num_fact.count(next_fact) && next_fact != fact_now)
                        {
                            f[v][num_fact[next_fact]] += f[j][i];
                            f[v][num_fact[next_fact]] %= MOD;
                        }
                    }
                }
        }
        cout<<f[n][num_fact[k]]<<endl;
    }
    return 0;
}
}}}

题意：给定一个有向图，每个节点一个权值。从起点出发，每到一个节点分数变为当前分数和节点权值的最小公倍数，且分数不能不变，问走到最后一个节点且分数是k的方案数。
解法：设F[i][s]为走到第i个节点，分数为s的方案数，则通过有向图上的边(i,j)可以转移到F[j][S]，且S>s。不过由于k太大，无法直接表示。
考虑每次都变为当前分数和节点权值的最小公倍数，即每次分数变为整数倍，且最后分数为k，所以中间所有可行状态的分数均为k的因子
只记录这些状态即可，状态数变为n*sqrt(k)。

#include <iostream>
#include <vector>
#include <map>
#include <cstring>
using namespace std;
typedef long long LL;
const int MOD = 1000000007;
int n, m, k, p[2002];
int f[2002][2002];
vector<int> conn[2002];
vector<int> fact;
map<int, LL> num_fact;
LL gcd(LL a, LL b)
{
    while(b)
    {
        LL c = a % b;
        a = b;
        b = c;
    }
    return a;
}
LL lcm(LL a, LL b)
{
    return a / gcd(a, b) * b;
}
int main()
{
    while(cin>>n>>m>>k)
    {
        for(int i=1;i<=n;i++)
            conn[i].clear();
        for(int i=1;i<=m;i++)
        {
            int a, b;
            cin>>a>>b;
            conn[a].push_back(b);
        }
        for(int i=1;i<=n;i++)
            cin>>p[i];
        fact.clear();
        num_fact.clear();
        for(int i=1;i<=k;i++)
            if(k%i==0)
            {
                num_fact[i] = fact.size();
                fact.push_back(i);
            }
        if(num_fact.count(p[1]) == 0)
        {
            cout<<0<<endl;
            continue;
        }
        int st = num_fact[p[1]];
        memset(f, 0, sizeof(f));
        f[1][st] = 1;
        for(int i=st;i<fact.size();i++)
        {
            int fact_now = fact[i];
            for(int j=1;j<=n;j++)
                if(f[j][i])
                {
                    for(int k=0;k<conn[j].size();k++)
                    {
                        int v = conn[j][k];
                        LL next_fact = lcm(p[v], fact_now);
                        if(num_fact.count(next_fact) && next_fact != fact_now)
                        {
                            f[v][num_fact[next_fact]] += f[j][i];
                            f[v][num_fact[next_fact]] %= MOD;
                        }
                    }
                }
        }
        cout<<f[n][num_fact[k]]<<endl;
    }
    return 0;
}