正題

題目鏈接:http://noip.ybtoj.com.cn/contest/596/problem/1

---

題目大意

$T$組詢問給出$n$求有多少個$n$的排列滿足第一個是$1$并且相鄰的差不超過$2$。

$1\le T\le 10^6,1\le n\le 10^9$

---

解題思路

考慮一下如果我們要不斷向前填滿前面的一段的話，那么填的方案就只有兩種，$(x,x+1)$和$(x,x+2,x+1,x+3)$，這樣一下會跳$1$或者$3$。

然后還有一種方法是一直往前跳兩格然后再跳回來，但是這樣就直接結束了。

設$f_i$表示按照最前面那兩種方法鋪$i$個的方案，那么答案就是$({\sum }_{i=1}^n{f}_i)?f_{n?1}$，減去$n?1$是因為會被$f_n$算重。

然后矩陣乘法+分塊預處理光速冪做就好了。

時間復雜度$O(4^3(\sqrt{10^9}+T))$

---

code

#include<cstdio> #include<cstring> #include<algorithm> #include<vector> #define ll long long #define file(x) freopen("data"#x".in","r",stdin);freopen("data"#x".out","w",stdout); using namespace std; const ll N=5e5+10; struct node{ll to,next; }a[N<<1]; ll n,m,tot=1,ls[N],fa[N],dep[N],s[N],f[N],ans,num; vector<ll> T[N]; void addl(ll x,ll y){a[++tot].to=y;a[tot].next=ls[x];ls[x]=tot;return; } void dfs(ll x,ll from){dep[x]=dep[fa[x]]+1;for(ll i=ls[x];i;i=a[i].next){ll y=a[i].to;if(i==from)continue;else if(dep[y]){if(dep[y]<=dep[x])s[x]++,s[fa[y]]--;continue;}T[x].push_back(y);fa[y]=x;dfs(y,i^1);s[x]+=s[y];}num+=(s[x]==0);return; } void calc(ll x){f[x]=(s[x]==0);dep[x]=1;for(ll i=0;i<T[x].size();i++){ll y=T[x][i];calc(y);ans+=f[x]*dep[y]+f[y]*dep[x];dep[x]+=dep[y];f[x]+=(s[x]==0)*dep[y]+f[y];}return; } signed main() {file(2);scanf("%lld%lld",&n,&m);for(ll i=1;i<=m;i++){ll x,y;scanf("%lld%lld",&x,&y);addl(x,y);addl(y,x);}dfs(1,0);calc(1);printf("%lld\n",n*(n-1)/2ll*num-ans);return 0; }

總結

以上是生活随笔為你收集整理的Ybtoj-排列计数【矩阵乘法,分块幂】的全部內容，希望文章能夠幫你解決所遇到的問題。

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