Full_of_Boys训练7总结
题目来源:2016沈阳区域赛
C.Recursive sequence
矩阵快速幂,思路来自oldz
#include <bits/stdc++.h> typedef unsigned long long ll; const ll mod=2147493647; using namespace std; ll A[7][7]={ {1,0,0,0,0,0,0}, {1,1,0,0,0,0,0}, {1,2,1,0,0,0,0}, {1,3,3,1,0,0,0}, {1,4,6,4,1,0,0}, {0,0,0,0,0,0,1}, {0,0,0,0,1,2,1}}; ll tmp[7][7],c[7][7],d[7][7],ans[7][7],B[7][7]; inline void mul(ll a[][7], ll b[][7], int n){ for(int i=0;i<n;++i) for(int j=0;j<n;++j)tmp[i][j]=0,c[i][j]=a[i][j],d[i][j]=b[i][j]; for(int i=0;i<n;++i) for(int k=0;k<n;++k)if(c[i][k]) for(int j=0;j<n;++j)if(d[k][j]){ tmp[i][j] = (tmp[i][j]+(c[i][k]*d[k][j])%mod)%mod; } for(int i=0;i<n;++i) for(int j=0;j<n;++j)a[i][j]=tmp[i][j]; } void mx_pow(ll ans[][7], ll A[][7], ll b){ while(b){ if(b&1)mul(ans,A,7); mul(A,A,7); b>>=1; } } ll n,a,b; int main() { int T; scanf("%d",&T); while(T--){ scanf("%lld%lld%lld",&n,&a,&b); for(int i=0;i<7;++i) for(int j=0;j<7;++j) if(i!=j)ans[i][j]=0; else ans[i][j]=1; for(int i=0;i<7;++i) for(int j=0;j<7;++j) B[i][j]=A[i][j]; mx_pow(ans,B,n-2); a%=mod;b%=mod; ll res = (ans[6][0]%mod+(3*ans[6][1])%mod+(9*ans[6][2])%mod+(27*ans[6][3])%mod+(81*ans[6][4])%mod+(a*ans[6][5])%mod+(b*ans[6][6])%mod)%mod; printf("%lld\n",res); } return 0; }
E.Counting Cliques
搜索,建图时有个比较重要的优化,写完代码会发现用到的边,只有由编号小到大的单向边。。。根本没想到搜。。。总结一下吧
#include <cstdio> #include <cstring> #include <algorithm> #include <vector> typedef long long ll; using namespace std; int n,m,s,x,y,tmp[111],cc,ans,mp[111][111],vis[111]; vector<int> G[111]; inline int ck(int x){ for(int i=1;i<=cc;++i) if(mp[tmp[i]][x]==0) return 0; return 1; } inline void dfs(int u){ if(cc==s){ ++ans; return; } for(int i=0;i<G[u].size();++i){ int v=G[u][i]; if(!vis[v]&&v>u&&ck(v)){ tmp[++cc]=v; vis[v]=1; dfs(v); --cc; vis[v]=0; } } } vector<int> tt; inline void del(int x){ for(int i=0;i<G[x].size();++i){ int v=G[x][i];tt.clear(); mp[x][v]=mp[v][x]=0; for(int j=0;j<G[v].size();++j){ if(G[v][j]!=x)tt.push_back(G[v][j]); } G[v]=tt; } G[x].clear(); } int T; int main() { scanf("%d",&T); while(T--){ ans=0; scanf("%d%d%d",&n,&m,&s); for(int i=1;i<=n;++i){ G[i].clear(); for(int j=1;j<=i;++j)mp[i][j]=mp[j][i]=0; } for(int i=1;i<=m;++i){ scanf("%d%d",&x,&y); if(x>y)swap(x,y); G[x].push_back(y);//!!!!important!!!! mp[x][y]=mp[y][x]=1; } for(int i=1;i<=n;++i){ cc=0; vis[i]=1; tmp[++cc]=i; dfs(i); vis[i]=0; del(i); } printf("%d\n",ans); } return 0; }
G.Do not pour out
二分+微积分,膜一发wst