D. Dice(“矩阵快速幂”)

题意：有$n$个$k$面的骰子，$k$面编号分别为$1,2,3,,,k$，Diego对这些筛子进行了一些操作，使它们都不能摇到编号是$m$的倍数那一面，摇到其他面的概率相同。问：抛完这$n$个骰子，它们的结果相加后得到一个$m$的倍数的概率。

思路：我们能摇到的面数为$k?k/m$，我们可以只考虑它们的余数（0~m-1）出现的概率。
容易求出抛一次骰子，每个余数出现的次数，$P_1[1],P_1[2],P_1[3],,,P_1[m?1]$
抛两次骰子时，考虑两个数相加等于i的所有情况，$P_2[i]=\sum P_1[x]?P_1[y]((x+y)\%m=i)$
抛三次骰子时，$P_3[i]=\sum P_2[x]?P_1[y]((x+y)\%m=i)$
抛四次骰子时，$P_4[i]=\sum P_3[x]?P_1[y]=\sum P_2[x]?P_2[y]((x+y)\%m=i)$
……
这样递推n次，$P_n[0]$就是最终概率的分子，分母为$(k?k/m{)}^n$。

因为n比较大，所以可以借鉴一下快速幂的操作
~~
　　　∩∩
　　（??ω?）
　 ＿|　?／(＿＿_
　／ └-(＿＿＿_／
　￣￣￣￣￣￣￣

#include<bits/stdc++.h>typedef long long ll;
using namespace std;
const long long mod = 1000000007;ll n, m, k;struct mat {
    ll a[300];friend mat operator*(const mat &x, const mat &y) {
    mat ans;for (int k = 0; k < m; k++) {
    ans.a[k] = 0;int i = k + 1, j = m - 1;while (i < j) {
    //i+j=m+k(ans.a[k] += x.a[i] * y.a[j] + x.a[j] * y.a[i]) %= mod;i++, j--;}if(i == j)(ans.a[k] += x.a[i] * y.a[i]) %= mod;i = 0, j = k;while(i < j) {
    //i+j=k(ans.a[k] += x.a[i] * y.a[j] + x.a[j] * y.a[i]) %= mod;i++, j--;}if(i == j)(ans.a[k] += x.a[i] * y.a[i]) %= mod;}return ans;}
} base;mat q_pow(mat a, int b) {
    mat ans = a;while (b) {
    if (b & 1)ans = ans * a;a = a * a;b >>= 1;}return ans;
}
ll q_pow(ll a, int b) {
    ll ans = 1;while (b) {
    if (b & 1)ans = (ans * a) % mod;a = (a * a) % mod;b >>= 1;}return ans;
}
int main() {
    scanf("%lld%lld%lld", &n, &k, &m);for (int i = 1; i < m; i++)base.a[i] = k / m;if (k % m) {
    for (int i = 1; i <= k % m; i++)base.a[i]++;}mat ans = q_pow(base, n - 1);ll temp = q_pow(k - k / m, n);temp = q_pow(temp, mod - 2);printf("%lld\n", ans.a[0]*temp % mod);return 0;
}