当前位置:网站首页>AtCoder Grand Contest 013 E - Placing Squares
AtCoder Grand Contest 013 E - Placing Squares
2022-07-05 05:31:00 【solemntee】
Portal :E - Placing Squares
The question : Now there is one with a length of n The stick
On the stick m m m A sign , The first i The distance between the marks and the left endpoint is x i x_i xi
You need to put some squares on this stick , Satisfy :
The side length of each square is a positive integer
Each square must have a side close to the stick
The stick must be completely covered , The boundary of the square cannot exceed the stick
The junction of two adjacent squares cannot be marked
Define the beauty degree of each scheme as the product of all square areas
Seek the sum of the beauty of all legal schemes , The answer is right 1 0 9 + 7 10^9+7 109+7 modulus
First of all, let's enjoy the official explanation
First of all, the contribution and can be transformed into the number of schemes through a clever transformation . Modify the model of the original problem slightly : Now there is n n n Consecutive spaces , Partition plates must be placed on the left and right boundaries , You can place partitions in two adjacent spaces , You can put red and blue balls in the space . Contribution and the number of solutions equivalent to the converted problem , This becomes a count d p dp dp.
consider d p [ i ] [ j ] dp[i][j] dp[i][j] Before considering i i i position , After the last partition j j j The number of ball schemes .
Consider the transfer of violence enumerated in section i i i There's a place for ( 0 , 1 , 2 ) (0,1,2) (0,1,2) Ball and whether it is in the i i i Place the baffle in two places , The specific derivation process will not be repeated
d p [ i ] [ 0 ] = d p [ i − 1 ] [ 0 ] ∗ 2 + d p [ i − 1 ] [ 1 ] ∗ 2 + d p [ i − 1 ] [ 2 ] ∗ 1 d p [ i ] [ 1 ] = d p [ i − 1 ] [ 0 ] ∗ 1 + d p [ i − 1 ] [ 1 ] ∗ 1 + d p [ i − 1 ] [ 2 ] ∗ 0 d p [ i ] [ 0 ] = d p [ i − 1 ] [ 0 ] ∗ 1 + d p [ i − 1 ] [ 1 ] ∗ 2 + d p [ i − 1 ] [ 2 ] ∗ 1... dp[i][0]=dp[i-1][0]*2+dp[i-1][1]*2+dp[i-1][2]*1\\ dp[i][1]=dp[i-1][0]*1+dp[i-1][1]*1+dp[i-1][2]*0\\ dp[i][0]=dp[i-1][0]*1+dp[i-1][1]*2+dp[i-1][2]*1 ... dp[i][0]=dp[i−1][0]∗2+dp[i−1][1]∗2+dp[i−1][2]∗1dp[i][1]=dp[i−1][0]∗1+dp[i−1][1]∗1+dp[i−1][2]∗0dp[i][0]=dp[i−1][0]∗1+dp[i−1][1]∗2+dp[i−1][2]∗1...
amount to
A N S [ i ] = { 2 2 1 1 1 0 1 2 1 } ∗ A N S [ i − 1 ] ANS[i]= \left\{ \begin{matrix} 2 & 2 &1 \\ 1 & 1 & 0 \\ 1 & 2 & 1 \end{matrix} \right\} *ANS[i-1] ANS[i]=⎩⎨⎧211212101⎭⎬⎫∗ANS[i−1]
Obviously, the matrix can be used for fast power optimization .
Of course, the transfer at the diaphragm is slightly different , No more details here .
#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
const int N=3;
struct Matrix{
int a[N][N];
Matrix(){
memset(a,0,sizeof(a));}
Matrix operator *(const Matrix &B)
{
Matrix c;
for(int k=0;k<N;k++)
for(int i=0;i<N;i++)
for(int j=0;j<N;j++)
c.a[i][j]=(c.a[i][j]+1LL*a[i][k]*B.a[k][j]%mod+mod)%mod;
return c;
}
}A,B,C,D;
Matrix fpow(Matrix A,long long b)///A^b
{
Matrix ret,B=A;
for(int i=0;i<N;i++)ret.a[i][i]=1;
while(b)
{
if(b&1)ret=ret*B;
B=B*B;
b>>=1;
}
return ret;
}
void init()
{
A.a[0][0]=2,A.a[0][1]=2,A.a[0][2]=1;
A.a[1][0]=1,A.a[1][1]=1,A.a[1][2]=0;
A.a[2][0]=1,A.a[2][1]=2,A.a[2][2]=1;
B.a[0][0]=1,B.a[0][1]=0,B.a[0][2]=0;
B.a[1][0]=1,B.a[1][1]=1,B.a[1][2]=0;
B.a[2][0]=1,B.a[2][1]=2,B.a[2][2]=1;
C.a[0][0]=1,C.a[0][1]=2,C.a[0][2]=1;
C.a[1][0]=0,C.a[1][1]=0,C.a[1][2]=0;
C.a[2][0]=0,C.a[2][1]=0,C.a[2][2]=0;
}
int a[1000005];
int main()
{
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)scanf("%d",&a[i]);
init();
Matrix ans;
ans.a[0][0]=1;
for(int i=1;i<=m;i++)
{
ans=fpow(A,a[i]-a[i-1]-1)*ans;
ans=B*ans;
}
ans=fpow(A,n-a[m]-1)*ans;
ans=C*ans;
// for(int i=0;i<N;i++)
// {
// for(int j=0;j<N;j++)
// {
// printf("%d%c",ans.a[i][j],(j==N-1)?'\n':' ');
// }
// }
printf("%d\n",(ans.a[0][0]%mod+mod)%mod);
return 0;
}
边栏推荐
- [merge array] 88 merge two ordered arrays
- 卷积神经网络简介
- PC寄存器
- 注解与反射
- Configuration and startup of kubedm series-02-kubelet
- 对象的序列化
- Improvement of pointnet++
- lxml.etree.XMLSyntaxError: Opening and ending tag mismatch: meta line 6 and head, line 8, column 8
- Developing desktop applications with electron
- Codeforces round 712 (Div. 2) d. 3-coloring (construction)
猜你喜欢
On-off and on-off of quality system construction
lxml. etree. XMLSyntaxError: Opening and ending tag mismatch: meta line 6 and head, line 8, column 8
Sword finger offer 58 - ii Rotate string left
Romance of programmers on Valentine's Day
利用HashMap实现简单缓存
object serialization
YOLOv5-Shufflenetv2
Sword finger offer 53 - I. find the number I in the sorted array
Codeforces round 712 (Div. 2) d. 3-coloring (construction)
Sword finger offer 04 Search in two-dimensional array
随机推荐
一个新的微型ORM开源框架
Graduation project of game mall
sync.Mutex源码解读
kubeadm系列-02-kubelet的配置和启动
Zzulioj 1673: b: clever characters???
Daily question - Search two-dimensional matrix PS two-dimensional array search
Palindrome (csp-s-2021-palin) solution
Solon 框架如何方便获取每个请求的响应时间?
ssh免密登录设置及使用脚本进行ssh登录并执行指令
卷积神经网络——卷积层
TF-A中的工具介绍
常见的最优化方法
sync. Interpretation of mutex source code
Solon Logging 插件的添加器级别控制和日志器的级别控制
Configuration and startup of kubedm series-02-kubelet
剑指 Offer 53 - II. 0~n-1中缺失的数字
剑指 Offer 53 - I. 在排序数组中查找数字 I
[to be continued] I believe that everyone has the right to choose their own way of life - written in front of the art column
[to be continued] [UE4 notes] L1 create and configure items
Acwing 4301. Truncated sequence