如果你 wa #4

那么你应该是矩阵的时候对于乘的矩阵直接写的 ci,j=1，应该是 ci,j++

本人因为这个问题在模拟赛中痛失 100 分。

#include <bits/stdc++.h>
#define int long long
#define L(i,j,k) for(int i=(j);i<=(k);i++)
#define R(i,j,k) for(int i=(j);i>=(k);i--)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
const int maxn=3e5+10,mod=1e9+7;
int A[102],C[102][102],c[102],c2[102][102];
int n,d[maxn],f[102];
void mul1(int b[102][102]){
	memset(c,0,sizeof c);
	for(int i=0;i<102;i++){
		for(int j=0;j<102;j++){
			(c[i]+=1ll*A[j]*b[j][i]%mod)%=mod;
		}
	}	
	for(int i=0;i<102;i++)A[i]=c[i];
}
void mul2(int b[102][102]){
	memset(c2,0,sizeof c2);
	for(int i=0;i<102;i++){
		for(int j=0;j<102;j++){
			for(int k=0;k<102;k++){
				c2[i][k]+=1ll*C[i][j]*b[j][k]%mod;
				c2[i][k]%=mod; 
			}
		}
	}
	for(int i=0;i<102;i++){
		for(int j=0;j<102;j++){
			C[i][j]=c2[i][j];
		}
	}
}
int k;

signed main(){
	cin>>n>>k;
	for(int i=1;i<=n;i++)cin>>d[i];
	for(int i=0;i<=99;i++)C[i+1][i]=1;
	for(int i=1;i<=n;i++)C[100-d[i]+1][100]++,C[100-d[i]+1][101]++;
	C[101][101]=1;
	f[0]=1;
	int s=1;
	for(int i=1;i<=100;i++){
		for(int j=1;j<=n;j++){
			if(i-d[j]>=0)f[i]+=f[i-d[j]],f[i]%=mod;
		}
		s+=f[i],s%=mod; 
	}
	A[101]=s;
	for(int i=0;i<=100;i++)A[i]=f[i];
	if(k<=100){
		s=0;
		for(int i=0;i<=k;i++)s+=f[i],s%=mod;
		cout<<s<<'\n';
		return 0;
	}
	int mul=k-100;
	while(mul){
		if(mul&1)mul1(C);
		mul2(C),mul>>=1;
	} 
	cout<<A[101]<<'\n';
	return 0;
}

就是

for(int i=1;i<=n;i++)C[100-d[i]+1][100]++,C[100-d[i]+1][101]++;

的问题

不要写成

for(int i=1;i<=n;i++)C[100-d[i]+1][100]=1,C[100-d[i]+1][101]=1;

操了