BZOJ2445 最大团

Luogu
IDLGP10594
Time1000ms
Memory512MB
DifficultyP6
O2优化中国剩余定理 CRTLucas 定理
一个 $n$ 个点的无向图被叫做是一个 symmetric labeled cliquer,当且仅当该图的任意一个极大连通子图拥有相同的点数,并且任意一个极大连通子图都是完全图。 现有 $m$ 种颜色和所有含有 $n$ 个点且节点有标号的 symmetric labeled cliquer。我们需要将每个 symmetric labeled cliquer 都染上一种颜色,两个不同的 symmetric labeled cliquer 可以染相同颜色,求方案数对 $10^9-401$ 取模的结果。 ## Input 第一行读入一个正整数 $T$,表示数据组数。 接下来每行包含两个正整数 $n,m$,含义如题所述。 ## Output 输出包含 $T$ 行,每行输出答案。 [samples] ## Background 题目来自原 BZOJ,我们承认题面及原数据的版权均属于原 BZOJ 或将题目授权给 BZOJ 使用的出题人。如果您是版权所有者且认为我们侵犯了您的权益,可联系我们。 ## Note 数据保证,$1\leq T\leq 2$,$1\leq n,m\leq 2\times 10^9$。
Samples
Input #1
1
4 2
Output #1
32
API Response (JSON)
{
  "problem": {
    "name": "BZOJ2445 最大团",
    "description": {
      "content": "一个 $n$ 个点的无向图被叫做是一个 symmetric labeled cliquer,当且仅当该图的任意一个极大连通子图拥有相同的点数,并且任意一个极大连通子图都是完全图。 现有 $m$ 种颜色和所有含有 $n$ 个点且节点有标号的 symmetric labeled cliquer。我们需要将每个 symmetric labeled cliquer 都染上一种颜色,两个不同的 symme",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P6"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP10594"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "一个 $n$ 个点的无向图被叫做是一个 symmetric labeled cliquer,当且仅当该图的任意一个极大连通子图拥有相同的点数,并且任意一个极大连通子图都是完全图。\n\n现有 $m$ 种颜色和所有含有 $n$ 个点且节点有标号的 symmetric labeled cliquer。我们需要将每个 symmetric labeled cliquer 都染上一种颜色,两个不同的 symme...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments