本题算是签到题, 但由于赛中花费了过多的时间去滴吧格, 造成了不必要的浪费以及智商掉线, 所以有必要记录一下
题意: 方格从 1 到 n, 每一格 mjl 可以选择吃鱼 / 巧克力 / 鸡腿, 求走到 n 格时满足
1. 每三格不可重复同一种食物
2. 每三格均不同食物时中间格子不可吃巧克力
3. 每三格前后两格不可同时吃巧克力
以上三个条件的方案数, n<1e10
太长不看版: 打表 + 快速幂 AC
长篇吐槽版
很显然的, 设 \(dp[n][i][j][k]\), 走到第 \(n\) 格时第 \(n-2\) 格的食物是 \(i\), 第 \(n-1\) 的食物是 \(j\), 第 \(n\) 的食物是 \(k\) 的方案数
然后一波转移套上矩阵快速幂, 应该没问题?
那么首先应该搞出所有转移, emmm 好像方程很多, 手写花了一定时间发现写歪了 (傻逼做法 1
于是写了个程序暴力转移
- rep(i,1,3)rep(j,1,3)rep(k,1,3){
- printf("dp[i][%d][%d][%d]=",i,j,k);
- bool flag=0;
- if(i==j&&j==k&&i==k) flag=1;
- if(j==2&&i!=2&&k!=2&&i!=k) flag=1;
- if(i==2&&k==2) flag=1;
- if(flag){
- cout<<0<<endl;
- continue;
- }
- flag=0;
- int jj=i,kk=j;
- rep(ii,1,3){
- if(ii==jj&&jj==kk&&ii==kk)continue;
- if(jj==2&&ii!=2&&kk!=2&&ii!=kk)continue;
- if(ii==2&&kk==2)continue;
- printf("dp[i-1][%d][%d][%d]+",ii,jj,kk);
- flag=1;
- }
- cout<<endl;
- }
于是得到
- dp[i][1][1][1]=0
- dp[i][1][1][2]=dp[i-1][2][1][1]+dp[i-1][3][1][1];
- dp[i][1][1][3]=dp[i-1][2][1][1]+dp[i-1][3][1][1];
- dp[i][1][2][1]=dp[i-1][1][1][2]+dp[i-1][3][1][2];
- dp[i][1][2][2]=dp[i-1][1][1][2]+dp[i-1][3][1][2];
- dp[i][1][2][3]=0;
- dp[i][1][3][1]=dp[i-1][1][1][3]+dp[i-1][2][1][3]+dp[i-1][3][1][3];
- dp[i][1][3][2]=dp[i-1][1][1][3]+dp[i-1][2][1][3]+dp[i-1][3][1][3];
- dp[i][1][3][3]=dp[i-1][1][1][3]+dp[i-1][2][1][3]+dp[i-1][3][1][3];
- dp[i][2][1][1]=dp[i-1][1][2][1]+dp[i-1][2][2][1];
- dp[i][2][1][2]=0;
- dp[i][2][1][3]=dp[i-1][1][2][1]+dp[i-1][2][2][1];
- dp[i][2][2][1]=dp[i-1][1][2][2]+dp[i-1][3][2][2];
- dp[i][2][2][2]=0;
- dp[i][2][2][3]=dp[i-1][1][2][2]+dp[i-1][3][2][2];
- dp[i][2][3][1]=dp[i-1][2][2][3]+dp[i-1][3][2][3];
- dp[i][2][3][2]=0;
- dp[i][2][3][3]=dp[i-1][2][2][3]+dp[i-1][3][2][3];
- dp[i][3][1][1]=dp[i-1][1][3][1]+dp[i-1][2][3][1]+dp[i-1][3][3][1];
- dp[i][3][1][2]=dp[i-1][1][3][1]+dp[i-1][2][3][1]+dp[i-1][3][3][1];
- dp[i][3][1][3]=dp[i-1][1][3][1]+dp[i-1][2][3][1]+dp[i-1][3][3][1];
- dp[i][3][2][1]=0;
- dp[i][3][2][2]=dp[i-1][1][3][2]+dp[i-1][3][3][2];
- dp[i][3][2][3]=dp[i-1][1][3][2]+dp[i-1][3][3][2];
- dp[i][3][3][1]=dp[i-1][1][3][3]+dp[i-1][2][3][3];
- dp[i][3][3][2]=dp[i-1][1][3][3]+dp[i-1][2][3][3];
- dp[i][3][3][3]=0;
先试试样例, 卧槽怎么全是 0 的
发现忘了前 3 项特判初始化 (傻逼做法 2
赶紧加上去
- rep(i,1,3)dp[1][0][0][i]=dp[0][0][0][0];
- rep(i,1,3)rep(j,1,3)dp[2][0][i][j]+=dp[1][0][0][i];
- rep(i,1,3)rep(j,1,3)rep(k,1,3){
- if(i==j&&j==k&&i==k)continue;
- if(j==2&&i!=2&&k!=2&&i!=k)continue;
- if(i==2&&k==2)continue;
- dp[3][i][j][k]+=dp[2][0][i][j];
- }
搞完后怒上 27*27 的矩阵, 然而 TLE(傻逼做法 3
再套了个费马小定理, TLE(hhh
dalao 指点了不如试试 BM? 没办法只好上了
得到 f[n]=2f[n-1]-f[n-2]+3f[n-3]+2f[n-4]
再怒上一波快速幂, 发现答案歪了.. 挂机 10min
最后偶然发现必须后几项开始推才是正确的 (傻逼做法 4
推完后改代码发现又递推不上去了, 两个人同时写都歪了
再次发现递推矩阵的上三角写歪了一位...(傻逼做法 5
对了, 挪板子的时候发现 MOD 写成了 1e9+9, 幸好被队友发现了 hhh(傻逼做法 6
最后奉上代码
- #include<bits/stdc++.h>
- #define rep(i,j,k) for(int i=j;i<=k;i++)
- #define rrep(i,j,k) for(int i=j;i>=k;i--)
- #define println(a) printf("%lld\n",(ll)(a))
- #define printbk(a) printf("%lld",(ll)(a))
- using namespace std;
- typedef long long ll;
- const int maxn = 100;
- const int MAXN = maxn;
- const ll MOD = 1e9+7;
- inline ll mod(ll a){return a%MOD;}
- ll read(){
- ll x=0,f=1;register char ch=getchar();
- while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
- while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
- return x*f;
- }
- ll b[5][5]={
- {0,0,0,0,0},
- {0,2,-1,3,2},
- {0,1,0,0,0},
- {0,0,1,0,0},
- {0,0,0,1,0},
- };
- ll c[]={0,2956,1286,560,244};
- struct Mat{
- ll m[5][5],r,c;
- void node(int rr,int cc,bool unit=0){
- r=rr;c=cc;
- memset(m,0,sizeof m);
- if(unit) rep(i,1,4) m[i][i]=1;
- }
- void print(){
- rep(i,1,4){
- rep(j,1,4){
- cout<<m[i][j]<<" ";
- }
- cout<<endl;
- }
- }
- };
- Mat operator * (Mat a,Mat b){
- Mat ans;ans.node(a.r,b.c);
- rep(i,1,4){
- rep(j,1,4){
- int t=4;
- rep(k,1,t){
- ans.m[i][j]+=mod(a.m[i][k]*b.m[k][j]);
- ans.m[i][j]=mod(ans.m[i][j]);
- }
- }
- }
- return ans;
- }
- Mat qmod(Mat a,ll n){
- Mat ans;ans.node(4,4,1);
- while(n){
- if(n&1) ans=ans*a;
- n>>=1;
- a=a*a;
- }
- return ans;
- }
- ll ans[]={0,3,9,20,46,106,244,560,1286,2956};
- int main(){
- int T=read();
- while(T--){
- Mat base,base2;
- base.node(4,4); base2.node(4,4);
- rep(i,1,4) rep(j,1,4) base.m[i][j]=b[i][j];
- rep(i,1,4) base2.m[i][1]=c[i];
- ll n=read();
- if(n<=9){
- println(ans[n]);
- continue;
- }
- base=qmod(base,n-9);
- Mat res=base*base2;
- println((res.m[1][1]+MOD)%MOD);
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2769598.html