题解 P3896 【[湖南集训]Clever Rabbit】

· · 题解

这题好像没有什么难度

考虑高精度+矩阵乘法可以得出所有结果

但是我们发现复杂度是实现时限的10倍左右吧

那怎么办呢

所以我们可以直接打出一张表

就是所有结果的表

然后分情况依据位数不断累加

然后取模

给代码：

// luogu-judger-enable-o2
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const string ans[30] = {
"0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000",
"0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000",
"5205420000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000",
"6728118300000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000",
"0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000",
"1274525651070000000000000000000000000000000000000000000000000000000000000000000000000000000000000000",
"0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000",
"7310330478107153100000000000000000000000000000000000000000000000000000000000000000000000000000000000",
"9409915628571684501000000000000000000000000000000000000000000000000000000000000000000000000000000000",
"8356658699026214374320000000000000000000000000000000000000000000000000000000000000000000000000000000",
"4207478918227656840747000000000000000000000000000000000000000000000000000000000000000000000000000000",
"4658496829792060429255563000000000000000000000000000000000000000000000000000000000000000000000000000",
"4207037896872256856796074700000000000000000000000000000000000000000000000000000000000000000000000000",
"1837202944781138598433025203500000000000000000000000000000000000000000000000000000000000000000000000",
"9405629592787115276209767075501000000000000000000000000000000000000000000000000000000000000000000000",
"3871575438778206368306960563089270000000000000000000000000000000000000000000000000000000000000000000",
"5457901232352028026825349529235227100000000000000000000000000000000000000000000000000000000000000000",
"4513218532109379109259170998447632930100000000000000000000000000000000000000000000000000000000000000",
"6471730057670894088987559819623556002720000000000000000000000000000000000000000000000000000000000000",
"2797168835289124286487787462067213786930310000000000000000000000000000000000000000000000000000000000",
"2771731023505047486049501778805691950648204000000000000000000000000000000000000000000000000000000000",
"5732074351329883434271916845658127944983253061000000000000000000000000000000000000000000000000000000",
"3553290435639296282926099426642422443260257564600000000000000000000000000000000000000000000000000000",
"3044052405585945199366406088614915076346365343439100000000000000000000000000000000000000000000000000",
"1746302984497548302405625795120522934215199862039670000000000000000000000000000000000000000000000000",
"3455789784904911219785370351674968020401966054354869320000000000000000000000000000000000000000000000",
"2401446323835665869533642508189259066894773732002511970100000000000000000000000000000000000000000000",
"8412147772073441386461294986064076822499815831191636716982000000000000000000000000000000000000000000",
"0451347111866863143074007949705031757877526107129750881854310000000000000000000000000000000000000000",
"8716368647076347425212341128211018724039913458254613506379624300000000000000000000000000000000000000"};
int n, p, ansp = 0;
int main() {
    int i;
    scanf("%d%d", &n, &p);
    for (i = 99; ~i; --i) ansp = ((ll)ansp * 10 + ans[n - 1][i] - '0') % p;
    printf("%d\n", ansp);
    return 0;
}