LGTB新买了一张n*m的矩(桌)阵(子)，他想给某些1*1的小矩形染色，使得染色之后，原矩阵的每个n*n的子矩阵中都包含恰好k个被染色了的小矩形。他想知道有多少种染色方案能让他满足上述要求。因为答案肯呢个很大，请输出方案数膜1e9+7的值
输入
输入第一行包含三个整数n，m，k，意义如题面所示
对于15%的数据，1≤n*m≤20，n≤m
对于40%的数据，1≤n≤10，n≤m≤1000
对于100%的数据，1≤n≤100，n≤m≤1e18,0≤k≤n²
输出
输出包含1个整数，代表LGTB的方案数
样例
样例输入
5 6 1
样例输出
45
时间限制
3s
样例说明
样例如图所示，如果在灰色区域染一个格子，有20种方案。如果在两边的白色格子各染一个格子，有25种方案。共45种方案。
由于题目描述中m最大是1e18，所以肯定要用到快速幂。
首先我们可以发现，如果把一列捆在一起处理的话，那么为了满足题意，第i列一定与第i+n列的染色个数是相同的。
那么考虑DP[i][j]，代表每一个整个块(如1~n为一块，n+1~2*n为一块，因为他们每一列的染色个数相同)中处理了前i列，此时染了j个颜色的方案数。
那么如果考虑下一块的话，设下一块染色个数为kk，则增加的方案数就为C[n][k]^t[i](t[i]为i位置存在的总个数)
于是C[n][k]用杨辉三角求出，然后在快速幂求C[n][k]^t[i]。
这里会发现，有可能最后要多出一点，也就是部分块，那么他们的列数要+1。
处理完过后，就可以直接DP了。时间复杂度O(n^4)
1 #include<cstdio>
2 #include<iostream>
3 #include<cstring>
4 #include<cmath>
5 using namespace std; 6 const int maxn=105; 7 const long long mod=1e9+7; 8 int n,k;long long m; 9 long long c[maxn][maxn]; 10 long long dp[maxn][maxn*maxn]; 11 long long w[2][maxn];long long re; 12 long long qe(long long a,long long b) 13 { 14 long long qwe=1; 15 while(b) 16 { 17 if(b&1)qwe*=a; 18 if(qwe>mod)qwe%=mod; 19 b>>=1;a=a*a; 20 if(a>mod)a%=mod; 21 } 22 return qwe; 23 } 24 void init() 25 { 26 c[0][0]=1; 27 for(int i=1;i<=100;i++) 28 for(int j=0;j<=i;j++) 29 { 30 c[i][j]=c[i-1][j]+c[i-1][j-1]; 31 if(c[i][j]>mod)c[i][j]%=mod; 32 } 33 long long qwe=m/n; 34 re=m%n; 35 for(int i=0;i<=n;i++) 36 { 37 w[0][i]=qe(c[n][i],qwe); 38 w[1][i]=qe(c[n][i],qwe+1); 39 } 40 return ; 41 } 42 int main() 43 { 44 freopen("table.in","r",stdin); 45 freopen("table.out","w",stdout); 46 scanf("%d%I64d%d",&n,&m,&k); 47 init(); 48 dp[0][0]=1; 49 long long wer=0; 50 for(int i=0;i<n;i++)//列
51 for(int j=0;j<=n*i;j++) 52 for(int kk=0;kk<=min(n,k);kk++) 53 { 54 if(i<re)//多了一列
55 wer=w[1][kk]; 56 else wer=w[0][kk]; 57
58 dp[i+1][j+kk]+=wer*dp[i][j]%mod; 59 dp[i+1][j+kk]%=mod; 60 } 61 printf("%I64d",dp[n][k]); 62 return 0; 63 }