当前位置:网站首页>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;
}
边栏推荐
- Haut OJ 1243: simple mathematical problems
- The present is a gift from heaven -- a film review of the journey of the soul
- YOLOv5-Shufflenetv2
- [turn to] MySQL operation practice (I): Keywords & functions
- lxml.etree.XMLSyntaxError: Opening and ending tag mismatch: meta line 6 and head, line 8, column 8
- [interval problem] 435 Non overlapping interval
- Introduction to memory layout of FVP and Juno platforms
- Detailed explanation of expression (csp-j 2021 expr) topic
- 卷积神经网络——卷积层
- 浅谈JVM(面试常考)
猜你喜欢
随机推荐
每日一题-无重复字符的最长子串
Introduction to memory layout of FVP and Juno platforms
剑指 Offer 05. 替换空格
Palindrome (csp-s-2021-palin) solution
Warning using room database: schema export directory is not provided to the annotation processor so we cannot export
26、 File system API (device sharing between applications; directory and file API)
Double pointer Foundation
剑指 Offer 53 - II. 0~n-1中缺失的数字
Codeforces Round #715 (Div. 2) D. Binary Literature
YOLOv5-Shufflenetv2
Control Unit 控制部件
Haut OJ 2021 freshmen week II reflection summary
游戏商城毕业设计
Software test -- 0 sequence
Little known skills of Task Manager
[turn to] MySQL operation practice (III): table connection
Haut OJ 1221: a tired day
Daily question - longest substring without repeated characters
使用Electron开发桌面应用
Chapter 6 data flow modeling - after class exercises