{"problem":{"name":"BZOJ4665 小 w 的喜糖","description":{"content":"小 w 一共买了 $n$ 块喜糖，发给了 $n$ 个人，每个喜糖有一个种类。这时，小 w 突发奇想，如果这 $n$ 个人相互交换手中的糖，那会有多少种方案使得每个人手中的糖的种类都与原来不同。 两个方案不同当且仅当，存在一个人，他手中的糖的种类在两个方案中不一样。","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P5"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP10597"},"statements":[{"statement_type":"Markdown","content":"小 w 一共买了 $n$ 块喜糖，发给了 $n$ 个人，每个喜糖有一个种类。这时，小 w 突发奇想，如果这 $n$ 个人相互交换手中的糖，那会有多少种方案使得每个人手中的糖的种类都与原来不同。\n\n两个方案不同当且仅当，存在一个人，他手中的糖的种类在两个方案中不一样。\n\n## Input\n\n第一行，一个正整数 $n$。\n\n接下来 $n$ 行，每行一个正整数，第 $i$ 个整数 $A_i$ 表示开始时第 $i$ 个人手中的糖的种类。\n\n## Output\n\n一行一个整数，表示方案数。答案对 $10^9+9$ 取模。\n\n[samples]\n\n## Background\n\n题目来自原 BZOJ，我们承认题面及原数据的版权均属于原 BZOJ 或将题目授权给 BZOJ 使用的出题人。如果您是版权所有者且认为我们侵犯了您的权益，可联系我们。\n\n---\n\n废话不多说，反正小 w 要发喜糖啦！！\n\n## Note\n\n对于所有数据，$1\\leq A_i \\leq n \\leq 2000$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10597","tags":["动态规划 DP","O2优化","容斥原理"],"sample_group":[["6\n1\n1\n2\n2\n3\n3","10"]],"created_at":"2026-03-03 11:09:25"}}