{"problem":{"name":"BZOJ3328 PYXFIB","description":{"content":"给定整数 $n,k,p$，要求计算下列式子对 $p$ 取模的值： $$\\sum_{i=0}^{\\lfloor \\frac{n}{k} \\rfloor} C_n^{i\\times k}\\times F_{i\\times k}$$ 其中： - $p$ 为质数，且 $p$ 除以 $k$ 的余数为 $1$。 - $C$ 为组合数，即 $C_n^m=\\frac{n!}{m!(n-m)!}$。 - $F_","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":2000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P6"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP10664"},"statements":[{"statement_type":"Markdown","content":"给定整数 $n,k,p$，要求计算下列式子对 $p$ 取模的值：\n\n$$\\sum_{i=0}^{\\lfloor \\frac{n}{k} \\rfloor} C_n^{i\\times k}\\times F_{i\\times k}$$\n\n其中：\n- $p$ 为质数，且 $p$ 除以 $k$ 的余数为 $1$。\n- $C$ 为组合数，即 $C_n^m=\\frac{n!}{m!(n-m)!}$。\n- $F_n$ 为斐波那契数列，即 $F_0=1$，$F_1=1$，$F_n=F_{n-1}+F_{n-2}(n\\geq 2)$。\n\n## Input\n\n第一行输入一个正整数 $T$，表示数据组数。\n\n接下来 $T$ 行，每行三个正整数 $n,k,p$。\n\n## Output\n\n输出 $T$ 行，每行一个整数，表示结果。\n\n[samples]\n\n## Note\n\n对于 $100\\%$ 的数据，保证 $1\\leq n\\leq 10^{18}$，$1\\leq k \\leq 20000$，$1\\leq T\\leq 20$，$1\\leq p\\leq 10^9$，$p$ 为质数，且 $p$ 除以 $k$ 的余数为 $1$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10664","tags":["原根","数论","O2优化","矩阵乘法","单位根反演"],"sample_group":[["1\n1 2 3","1"]],"created_at":"2026-03-03 11:09:25"}}