标签：tmp return matrix long 循环 n1 105
- 抽丝剥茧到最后一步，你离成功解出这道题只剩下“矩阵等比数列求和”这个问题了。把式子写出来：\(M+M^2+M^3+...+M^k\)，虽然没办法套用求和公式，但一定有办法的，看着它，用心感受，或者不妨先转移注意力——
- 分治！分解原问题为结构相同的子问题，再将子问题的解合并成原问题的解！
- 分治的过程中，如果调用power函数，总的时间复杂度大概会多出一个log，这是不能接受的；不妨新开一个全局变量，在递归的过程中顺便计算快速幂的值
点击查看代码
#include <bits/stdc++.h>
using namespace std;
const int mod=1000000007;
long long L,R;
vector<long long>a[105],c[105];
long long f[105],ans;
long long n;
class matrix
{
public:
matrix()
{
memset(a,0,sizeof(a));
}
long long a[105][105];
void clear()
{
memset(a,0,sizeof(a));
}
};
matrix pr;
matrix danwei()
{
matrix res;
for(long long i=1;i<=n;i++)
{
res.a[i][i]=1;
}
return res;
}
matrix operator+(matrix a,matrix b)
{
matrix c;
for(long long i=1;i<=n;i++)
{
for(long long j=1;j<=n;j++)
{
c.a[i][j]+=(a.a[i][j]+b.a[i][j]);
c.a[i][j]%=mod;
}
}
return c;
}
matrix operator*(matrix a,matrix b)
{
matrix c;
for(long long i=1;i<=n;i++)
{
for(long long j=1;j<=n;j++)
{
for(long long k=1;k<=n;k++)
{
c.a[i][j]+=(a.a[i][k]*b.a[k][j]%mod);
}
c.a[i][j]%=mod;
}
}
return c;
}
matrix power(matrix n1,long long p)
{
matrix res=danwei();
for(p;p;p>>=1)
{
if((p&1)==1)
{
res=res*n1;
}
n1=n1*n1;
}
return res;
}
matrix P;
matrix fenzhi(matrix n1,long long p)
{
if(p==1)
{
P=n1;
return n1;
}
matrix tmp=fenzhi(n1,p/2),q=P;
if(p%2==0)
{
P=P*P;
return tmp+tmp*q;
}
else
{
P=P*P*n1;
return tmp+tmp*q+q*q*n1;
}
}
void calc(long long l,long long r)
{
if(l>r)
{
return;
}
else if(l==r)
{
matrix val=power(pr,l-1);
for(long long i=1;i<=n;i++)
{
long long n1=(l-1)*n+i;
if(n1>=L&&n1<=R)
{
for(long long j=1;j<=n;j++)
{
ans=ans+f[j]*val.a[i][j]%mod;
ans%=mod;
}
}
}
}
else
{
matrix val=power(pr,l-2)*fenzhi(pr,r-l+1);
for(long long i=1;i<=n;i++)
{
for(long long j=1;j<=n;j++)
{
ans=ans+f[j]*val.a[i][j]%mod;
ans%=mod;
}
}
}
}
int main()
{
int size(512<<20);
__asm__ ( "movq %0, %%rsp\n"::"r"((char*)malloc(size)+size));
ios::sync_with_stdio(false);
cin.tie(0);
long long T;
cin>>T;
while(T--)
{
long long m;
cin>>n>>m>>L>>R;
pr.clear();
for(long long i=1;i<=n;i++)
{
f[i]=0;
a[i].clear();
c[i].clear();
}
for(long long i=1;i<=m;i++)
{
long long u,v,w;
cin>>u>>v>>w;
if(v<=n)
{
a[v].push_back(u);
c[v].push_back(w);
}
else
{
pr.a[v-n][u]=w;
}
}
f[1]=1;
for(long long i=1;i<=n;i++)
{
for(long long j=0;j<a[i].size();j++)
{
(f[i]+=(c[i][j]*f[a[i][j]]%mod))%=mod;
for(long long k=1;k<=n;k++)
{
pr.a[i][k]+=(pr.a[a[i][j]][k]*c[i][j]%mod);
pr.a[i][k]%=mod;
}
}
}
long long l=(L-1)/n+1;
long long r=(R-1)/n+1;
ans=0;
if(l==r)
{
calc(l,l);
}
else
{
calc(l,l);
calc(r,r);
calc(l+1,r-1);
}
cout<<ans<<endl;
}
exit(0);
}
/*
2
3 4 1 100
1 2 1
1 3 1
3 4 1
2 5 1
5 8 998244353 1000000007
1 2 114514
1 4 1919810
2 3 999999999
3 5 111111111
4 5 1000000000
1 10 123456789
5 6 987654321
3 9 888888888
*/
标签：tmp,
return,
matrix,
long,
循环,
n1,
105
From： https://www.cnblogs.com/watersail/p/18398706