题意
给定(n)个点((nle 40))，(m)条((mle 1000))长为(1)的边（无重边有自环）。
(q)个询问((qle 40))，每次询问两个点之间长度在(l,r(l,rle 10^9,(r-1)le 200))之间的路径数。
分析
一开始打了个爆搜结果一分都没有。
正解是弗洛伊德。
30pts
(f[i][j][k])表示从(i)到(j)路径长度为(k)的方案数。
很明显(k=1)的时候(f[i][j][k]=g[i][j])，(g[i][j])为邻接矩阵，表示(i,j)之间有一条边。
我们可以从(2)到(l-1)递推一遍，然后再从(l)到(r)递推一遍，这次统计方案数。
注意(l=1)时的特判，这样子30分到手。
时间复杂度(O(n^3qr))
70pts
然后我们可以注意到，上面的运算和矩阵的运算有点相似。
我们发现，邻接矩阵就是系数矩阵，代表(k-1)长度的路径能否转移到(k)长度的路径。
我们递推一次就相当于乘以一个邻接矩阵，我们可以用矩阵快速幂快速递推出(k=l)时的f矩阵。
时间复杂度(O(n^3q((r − l) + log n)))
100pts
我们要拿满分还必须优化掉((r-l))前面的系数。
我们预处理一遍前缀和，用一个(sum)矩阵保存(1~200)的系数前缀和。
算出(A^l)之后我们只要乘上这个前缀和矩阵就可以直接算出答案了，这样我们就能把((r-l))前的系数优化到(1)了。
代码
30pts
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#define ll long long
using namespace std;
const int M=1009,N=50;
const int Maxn=10000009;
const int mod=2333;
int read(){
char c;int num,f=1;
while(c=getchar(),!isdigit(c))if(c=='-')f=-1;num=c-'0';
while(c=getchar(), isdigit(c))num=num*10+c-'0';
return f*num;
}
int n,m,s,t,l,r,g[50][50];
int f[50][50][5],Case;
void work(){
s=read();t=read();l=read();r=read();
int ans=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++){
f[i][j][1]=g[i][j];
if(l==1&&i==s&&j==t)
ans+=f[i][j][1];
}
for(int k=2;k<l;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++){
f[i][j][k%2]=0;
for(int mid=1;mid<=n;mid++)
f[i][j][k%2]=(f[i][j][k%2]+f[i][mid][(k-1)%2]*g[mid][j])%mod;
}
for(int k=max(l,2);k<=r;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++){
f[i][j][k%2]=0;
for(int mid=1;mid<=n;mid++)
f[i][j][k%2]=(f[i][j][k%2]+f[i][mid][(k-1)%2]*g[mid][j])%mod;
if(i==s&&j==t)
ans=(ans+f[i][j][k%2])%mod;
}
printf("%d
",ans);
}
int main()
{
freopen("l.in","r",stdin);
freopen("l.out","w",stdout);
n=read();m=read();
int u,v;
for(int i=1;i<=m;i++){
u=read();v=read();
g[u][v]=g[v][u]=1;
}
Case=read();
while(Case--)work();
return 0;
}
70pts
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#define ll long long
using namespace std;
const int M=1009,N=50;
const int Maxn=10000009;
const int mod=2333;
struct mat{
int a[50][50];
mat(){
memset(a,0,sizeof(a));
}
}f[209],g,now;
int read(){
char c;int num,f=1;
while(c=getchar(),!isdigit(c))if(c=='-')f=-1;num=c-'0';
while(c=getchar(), isdigit(c))num=num*10+c-'0';
return f*num;
}
int n,m,s,t,l,r,Case;
mat operator *(mat A,mat B){
mat C;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
C.a[i][j]=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
for(int k=1;k<=n;k++)
C.a[i][j]=(C.a[i][j]+A.a[i][k]*B.a[k][j]%mod)%mod;
return C;
}
mat operator ^(mat A,int p){
mat C=A;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++)
C.a[i][j]=0;
C.a[i][i]=1;
}
for(;p;p>>=1,A=A*A)
if(p&1)C=C*A;
return C;
}
mat operator +(mat A,mat B){
mat ans;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
ans.a[i][j]=A.a[i][j]+B.a[i][j];
if(ans.a[i][j]>=mod)ans.a[i][j]-=mod;
}
}
return ans;
}
void work(){
s=read();t=read();l=read();r=read();
int ans=0;
if(l>r){printf("0
");return ;}
now=g^l;
for(int k=1;k<=(r-l+1);k++){
ans=(ans+now.a[s][t])%mod;
now=now*g;
}
printf("%d
",ans);
return ;
}
int main()
{
freopen("l.in","r",stdin);
freopen("l.out","w",stdout);
n=read();m=read();
int u,v;
for(int i=1;i<=m;i++){
u=read();v=read();
g.a[u][v]=g.a[v][u]=1;
}
Case=read();
while(Case--)work();
return 0;
}
100pts
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#define ll long long
using namespace std;
const int M=1009,N=50;
const int Maxn=10000009;
const int mod=2333;
struct mat{
int a[50][50];
mat(){
memset(a,0,sizeof(a));
}
}sum[209],g,now;
int read(){
char c;int num,f=1;
while(c=getchar(),!isdigit(c))if(c=='-')f=-1;num=c-'0';
while(c=getchar(), isdigit(c))num=num*10+c-'0';
return f*num;
}
int n,m,s,t,l,r,Case;
mat operator *(mat A,mat B){
mat C;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
C.a[i][j]=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
for(int k=1;k<=n;k++)
C.a[i][j]=(C.a[i][j]+A.a[i][k]*B.a[k][j]%mod)%mod;
return C;
}
mat operator ^(mat A,int p){
mat C=A;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++)
C.a[i][j]=0;
C.a[i][i]=1;
}
for(;p;p>>=1,A=A*A)
if(p&1)C=C*A;
return C;
}
mat operator +(mat A,mat B){
mat ans;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
ans.a[i][j]=A.a[i][j]+B.a[i][j];
if(ans.a[i][j]>=mod)ans.a[i][j]-=mod;
}
}
return ans;
}
void work(){
s=read();t=read();l=read();r=read();
int ans=0;
if(l>r){printf("0
");return ;}
now=g^l;
now=now*sum[r-l];
printf("%d
",now.a[s][t]);
return ;
}
int main()
{
freopen("l.in","r",stdin);
freopen("l.out","w",stdout);
n=read();m=read();
int u,v;
for(int i=1;i<=m;i++){
u=read();v=read();
g.a[u][v]=g.a[v][u]=1;
}
for(int i=1;i<=n;i++)now.a[i][i]=1;
sum[0]=now;
for(int i=1;i<=201;i++){
now=now*g;
sum[i]=sum[i-1]+now;
}
Case=read();
while(Case--)work();
return 0;
}