我去,517这他妈的都是什么鬼题目啊,烦死了

题意:

给你一副无向图n个点,标号为0到n-1, 每个点有一种颜色。。=
你想要走遍图中的每一个点恰好一次,可以从任意位置开始走,以任意位置结束
假设走的序列是c1,c2,c3…,cn,如果ci cj的颜色相同,那么[ci, cj]之间的点的颜色都要是相同的颜色
请问有多少种不同的走法,模10^9+7

输入格式:

  1. 第一行输入两个整数n,m (2≤n≤100,1≤m≤2500)表示点数与边数
  2. 第二行输入n个整数表示每个点颜色color[i], (0≤color[i]≤9),每种颜色最多出现10次
  3. 第三行输入m个数表示每条边的起点
  4. 第四行输入m个数表示每条边的终点

输出格式:

  1. 输出一个整数

分析:

然后这个题目除了无聊很烦以外就没有什么特点了,我们都可以一眼秒出怎么写,是吧,然后我发挥了我可以把代码打的特别翔的特点打了100行+,然后我因为数组开小了。整整多调了2h+。
我们可以对同一种颜色用状态压缩dp求出同一种颜色中从一个起点到另一个终点的方案数;然后我们之后利用状压颜色,表示一种颜色向另一种转移的方案。。。

代码:

#pragma GCC diagnostic error            "-std=c++11"
#pragma GCC target                           ("avx")
#pragma GCC optimize                             (3)
#pragma GCC optimize                       ("Ofast")
#pragma GCC optimize                      ("inline")
#pragma GCC optimize                      ("-fgcse")
#pragma GCC optimize                   ("-fgcse-lm")
#pragma GCC optimize                   ("-fipa-sra")
#pragma GCC optimize                  ("-ftree-pre")
#pragma GCC optimize                  ("-ftree-vrp")
#pragma GCC optimize                 ("-fpeephole2")
#pragma GCC optimize                 ("-ffast-math")
#pragma GCC optimize                ("-fsched-spec")
#pragma GCC optimize                ("unroll-loops")
#pragma GCC optimize               ("-falign-jumps")
#pragma GCC optimize               ("-falign-loops")
#pragma GCC optimize              ("-falign-labels")
#pragma GCC optimize              ("-fdevirtualize")
#pragma GCC optimize              ("-fcaller-saves")
#pragma GCC optimize              ("-fcrossjumping")
#pragma GCC optimize              ("-fthread-jumps")
#pragma GCC optimize              ("-funroll-loops")
#pragma GCC optimize             ("-fwhole-program")
#pragma GCC optimize            ("-freorder-blocks")
#pragma GCC optimize            ("-fschedule-insns")
#pragma GCC optimize            ("inline-functions")
#pragma GCC optimize           ("-ftree-tail-merge")
#pragma GCC optimize           ("-fschedule-insns2")
#pragma GCC optimize           ("-fstrict-aliasing")
#pragma GCC optimize           ("-fstrict-overflow")
#pragma GCC optimize           ("-falign-functions")
#pragma GCC optimize           ("-fcse-skip-blocks")
#pragma GCC optimize          ("-fcse-follow-jumps")
#pragma GCC optimize          ("-fsched-interblock")
#pragma GCC optimize          ("-fpartial-inlining")
#pragma GCC optimize          ("no-stack-protector")
#pragma GCC optimize         ("-freorder-functions")
#pragma GCC optimize         ("-findirect-inlining")
#pragma GCC optimize      ("-fhoist-adjacent-loads")
#pragma GCC optimize      ("-frerun-cse-after-loop")
#pragma GCC optimize      ("inline-small-functions")
#pragma GCC optimize    ("-finline-small-functions")
#pragma GCC optimize    ("-ftree-switch-conversion")
#pragma GCC optimize    ("-foptimize-sibling-calls")
#pragma GCC optimize   ("-fexpensive-optimizations")
#pragma GCC optimize ("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#include        <set>
#include        <map>
#include      <queue>
#include      <stack>
#include      <cmath>
#include     <cstdio>
#include     <time.h>
#include     <vector>
#include    <cstring>
#include   <stdlib.h>
#include   <iostream>
#include  <algorithm>
#include <bits/stdc++.h>
#define LL long long
#define int LL
using namespace std;
const LL N=2e5+10;
const LL inf=1e15+7;
const LL mod=1e9+7;
namespace FastIO
{
    template<typename tp> inline void read(tp &x)
    {
        x=0; char c=getchar(); bool f=0;
        for(;c<'0'||c>'9';f|=(c=='-'),c = getchar());
        for(;c>='0'&&c<='9';x=(x<<3)+(x<<1)+c-'0',c = getchar());
        if(f) x=-x;
    }
    template<typename tp> inline void write(tp x)
    {
        if (x==0) return (void) (putchar('0'));
        if (x<0) putchar('-'),x=-x;
        LL pr[20]; LL cnt=0;
        for (;x;x/=10) pr[++cnt]=x%10;
        while (cnt) putchar(pr[cnt--]+'0');
    }
    template<typename tp> inline void writeln(tp x)
    {
        write(x);
        putchar('\n');
    }
}
using namespace FastIO;
int n, m, cnt;
int hash_col[12], num_col;
int col[110], head[110];
int st[3000], en[3000];
int way[110][110], ans;
struct Edge
{
    int next, to;
} edge[6000];
int cnt_col;
int head_col[110], num[15];
int opt[11][11], back[110];
int dp_col[1 << 12][12];
int Map[110][110];
struct Edge_col
{
    int next, to;
} edge_col[6000];
void add(int u, int v)
{
    edge[++cnt].to = v;
    edge[cnt].next = head[u];
    head[u] = cnt;
}
void add_col(int u, int v)
{
    edge_col[++cnt_col].to = v;
    edge_col[cnt_col].next = head_col[u];
    head_col[u] = cnt_col;
}
int dp[1 << 12][101];
main()
{        memset(dp_col, 0, sizeof(dp_col));

    read(n), read(m);
    for (int i = 0; i < n; i++)
    {
        read(col[i]);
        if (hash_col[col[i]] == 0)
            num_col++, hash_col[col[i]] = num_col;
        col[i] = hash_col[col[i]];
        num[col[i]]++;
        opt[col[i]][num[col[i]]] = i;
        back[i] = num[col[i]];
    }
    for (int i = 1; i <= m; i++)
        read(st[i]);
    for (int i = 1; i <= m; i++)
    {
        read(en[i]);
        if(Map[st[i]][en[i]]) assert(0);
        add(st[i], en[i]), add(en[i], st[i]);
        if (col[st[i]] == col[en[i]])
            add_col(st[i], en[i]), add_col(en[i], st[i]);
    }
    for (int i = 0; i < n; i++)
    {
        memset(dp_col, 0, sizeof(dp_col));
        dp_col[1 << back[i] - 1][back[i]] = 1;
        for (int j = (1 << back[i] - 1); j < (1 << num[col[i]]) - 1; j++)
            for (int k = 1; k <= num[col[i]]; k++)
                if ((j & (1 << (k - 1))) && dp_col[j][k])
                {
                    for (int l = head_col[opt[col[i]][k]]; l != 0; l = edge_col[l].next)
                    {
                        int to = back[edge_col[l].to];
                        if (!(j & (1 << (to - 1))))
                            (dp_col[j | (1 << (to - 1))][to] += dp_col[j][k] % mod) %= mod;
                    }
                }
        for (int j = 1; j <= num[col[i]]; j++)
            way[i][opt[col[i]][j]] = dp_col[(1 << num[col[i]]) - 1][j];
    }
    for (int i = 0; i < n; i++)
        for (int j = 1; j <= num[col[i]]; j++)
        {
            dp[1 << col[i] - 1][opt[col[i]][j]] += way[i][opt[col[i]][j]];
            dp[1 << col[i] - 1][opt[col[i]][j]] %= mod;
        }
    for (int i = 1; i < (1 << num_col) - 1; i++)
    {
        for (int coll = 1; coll <= num_col; coll++)
            if (i & (1 << coll - 1))
            {
                for (int j = 1; j <= num[coll]; j++)
                {
                    int now = opt[coll][j];
                    if (!dp[i][now])
                        continue;
                    for (int k = head[now]; k != 0; k = edge[k].next)
                    {
                        int to = edge[k].to;
                        if (!(i & (1 << col[to] - 1)))
                        {
                            for (int l = 1; l <= num[col[to]]; l++)
                            {
                                dp[i | (1 << col[to] - 1)][opt[col[to]][l]] += (way[to][opt[col[to]][l]] % mod * dp[i][now]) % mod;
                                dp[i | (1 << col[to] - 1)][opt[col[to]][l]] %= mod;
                            }
                        }
                    }
                }
            }
    }
    for (int i = 0; i < n; i++)
        (ans += dp[(1 << num_col) - 1][i]) %= mod;
    writeln(ans);
    return 0;
}

Leave A Comment

发表评论

电子邮件地址不会被公开。 必填项已用*标注