?Okabe and El Psy Kongroo

題意：有n條平行x軸的線段，每條線段的起點為（ai，ci），終點為（bi，ci），且滿足ai=b(i-1)，從起點出發，每次可以往3個方向走，分別為?(x?+?1,?y?+?1),?(x?+?1,?y), or?(x?+?1,?y?-?1)，且走的過程必須滿足0>=y>=ci，求走到（k，0）有多少種走法

思路：dp+矩陣快速冪，

dp[i][0]=dp[i-1][0]+dp[i-1][1]

...........

dp[i][j]=dp[i-1][j]+dp[i-1][j+1]+dp[i-1][j-1]

...........

dp[i][c]=dp[i-1][c]+dp[i-1][c-1]

得到

dp[i][0] ? ? ? ?dp[i][1] ? ?... dp[i][j] ?... ? ? dp[i][c]

? s矩陣 [ ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ]

dp[i+1][0] ? dp[i+1][1] ... dp[i+1][j] ... dp[i+1][c]

每段線段用一次矩陣快速冪

AC代碼：

#include "iostream" #include "string.h" #include "stack" #include "queue" #include "string" #include "vector" #include "set" #include "map" #include "algorithm" #include "stdio.h" #include "math.h" #define ll long long #define bug(x) cout<<x<<" "<<"UUUUU"<<endl; #define mem(a) memset(a,0,sizeof(a)) using namespace std; const int N=20; ll M,Mod=1e9+7; struct Mat{ll m[N][N];Mat(){mem(m);}Mat friend operator* (Mat a, Mat b){Mat c;for(int i=0; i<M; i++)for(int j=0; j<M; j++)for(int k=0; k<M; k++)c.m[i][j]=(c.m[i][j]+a.m[i][k]*b.m[k][j])%Mod;return c;} }; Mat PowMod(Mat a, ll b){Mat c;for(int i=0; i<M; ++i) c.m[i][i]=1;while(b){if(b&1) c=c*a;a=a*a;b>>=1;}return c; } ll n,k,a[105],b[105],c[105]; int main(){cin>>n>>k;for(int i=0; i<n; ++i){cin>>a[i]>>b[i]>>c[i];}Mat t;for(int i=0;i<16;i++)for(int j=i-1;j<=i+1;j++)if(j>=0&&j<16)t.m[i][j] = 1;Mat ans;ans.m[0][0]=1;for(int i=0; i<n; ++i){k-=(b[i]-a[i]);M=c[i]+1;if(k>=0){ans=ans*PowMod(t,b[i]-a[i]);}else{k+=(b[i]-a[i]);ans=ans*PowMod(t,k);}}cout<<ans.m[0][0];return 0; } /* 1 3 0 3 3 2 6 0 3 0 3 10 2 */

?

轉載于:https://www.cnblogs.com/max88888888/p/7102892.html

總結

以上是生活随笔為你收集整理的Codeforces Round #420 E的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。