[POI 2021/2022 R1] Układanie kart

Luogu
IDLGP9419
Time1000ms
Memory256MB
DifficultyP7
模拟递推POI(波兰)2021
我们用以下方法将一个排列递增排序: 一次操作:记第一个数字为 $k$,在排列中找到 $k-1$($k=1$ 则取 $n$),把 $k-1$ 拉到排列的第一个位置,中间的数字依次后移。 一次操作的价值:$k-1$(或 $n$)在原排列的位置(这个从 $0$ 开始标号)。 一个排列的价值:进行若干次操作直到排列有序,价值为每次操作的价值之和。 给你 $n,m$,求所有 $n!$ 个排列的价值之和,对 $m$ 取模。 ## Input 一行两个正整数,$n,m$。 ## Output 一行一个整数,答案对 $m$ 取模的结果。 [samples] ## Background 译自 [XXIX Olimpiada Informatyczna – I etap](https://sio2.mimuw.edu.pl/c/oi29-1/dashboard/) [Układanie kart](https://sio2.mimuw.edu.pl/c/oi29-1/p/ukl/)。 ## Note 对于所有数据,$2\leq n\leq 1000000$,$2\leq m\leq 10^9$。 | 子任务编号 | 附加限制 | 分数 | | :----------: | :----------: | :----------: | | 1 | $n\leq 10$ | 10 | | 2 | $n\leq 2000$ | 60 | | 3 | | 30 |
Samples
Input #1
2 100
Output #1
1
Input #2
3 100
Output #2
15
Input #3
10 1000
Output #3
100
Input #4
500 100000
Output #4
60000
Input #5
100000 1000
Output #5
0
API Response (JSON)
{
  "problem": {
    "name": "[POI 2021/2022 R1] Układanie kart",
    "description": {
      "content": "我们用以下方法将一个排列递增排序: 一次操作:记第一个数字为 $k$,在排列中找到 $k-1$($k=1$ 则取 $n$),把 $k-1$ 拉到排列的第一个位置,中间的数字依次后移。 一次操作的价值:$k-1$(或 $n$)在原排列的位置(这个从 $0$ 开始标号)。 一个排列的价值:进行若干次操作直到排列有序,价值为每次操作的价值之和。 给你 $n,m$,求所有 $n!$ 个排列的价值之",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": {
      "LuoguStyle": "P7"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP9419"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "我们用以下方法将一个排列递增排序:\n\n一次操作:记第一个数字为 $k$,在排列中找到 $k-1$($k=1$ 则取 $n$),把 $k-1$ 拉到排列的第一个位置,中间的数字依次后移。\n\n一次操作的价值:$k-1$(或 $n$)在原排列的位置(这个从 $0$ 开始标号)。\n\n一个排列的价值:进行若干次操作直到排列有序,价值为每次操作的价值之和。\n\n给你 $n,m$,求所有 $n!$ 个排列的价值之...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments