当前位置:网站首页>[Niuke practice match 68] fans of Niuniu (matrix fast power cycle matrix optimization)
[Niuke practice match 68] fans of Niuniu (matrix fast power cycle matrix optimization)
2022-04-23 09:43:00 【Zimba_】
Topic link
Retention pit , Write tomorrow .
The question :
There is one n n n A ring of dots , Each point has an initial weight x i x_{i} xi.
The description that defines each round of adjustment is : For the weight of each point on the ring , Yes p 1 p_1 p1 The probability flows to the next point in a clockwise direction , Yes p 2 p_2 p2 The probability flows to the next point counterclockwise , Yes p 3 p_3 p3 The probability of stopping in place .( among p 1 + p 2 + p 3 = 1 p_{1}+p_{2}+p_{3}=1 p1+p2+p3=1)
ask k k k After wheel adjustment , The expected weight of each point , The answer is based on the model 998244353.
( 3 ≤ n ≤ 500 , 0 ≤ k ≤ 1 0 18 3\leq n\leq 500 ,0\leq k\leq 10^{18} 3≤n≤500,0≤k≤1018)
Ideas :
First, you can give the value of each point after a round of adjustment X i = p 1 x i − 1 + p 3 x i + p 2 x i + 1 X_{i}=p_{1}x_{i-1}+p_{3}x_{i}+p_{2}x_{i+1} Xi=p1xi−1+p3xi+p2xi+1.
You can easily get the equation of solving the vector transfer once :
[ p 3 p 2 0 0 p 1 p 1 p 3 p 2 0 0 0 p 1 p 3 p 2 0 0 0 p 1 p 3 p 2 p 2 0 0 p 1 p 3 ] [ x 1 x 2 x 3 x 4 x 5 ] = [ X 1 X 2 X 3 X 4 X 5 ] \left[ \begin{matrix} p_{3} & p_{2} & 0 & 0 & p_{1}\\ p_{1} & p_{3} & p_{2} & 0 & 0 \\ 0 & p_{1} & p_{3} & p_{2} & 0 \\ 0 & 0 & p_{1} & p_{3} & p_{2} \\ p_{2} & 0 & 0 & p_{1} & p_{3} \end{matrix} \right] \left[ \begin{matrix} x_{1} \\ x_{2} \\ x_{3} \\ x_{4} \\ x_{5} \end{matrix} \right] =\left[ \begin{matrix} X_{1} \\ X_{2} \\ X_{3} \\ X_{4} \\ X_{5} \end{matrix} \right] ⎣⎢⎢⎢⎢⎡p3p100p2p2p3p1000p2p3p1000p2p3p1p100p2p3⎦⎥⎥⎥⎥⎤⎣⎢⎢⎢⎢⎡x1x2x3x4x5⎦⎥⎥⎥⎥⎤=⎣⎢⎢⎢⎢⎡X1X2X3X4X5⎦⎥⎥⎥⎥⎤
So our answer is :
[ X 1 X 2 X 3 X 4 X 5 ] = [ p 3 p 2 0 0 p 1 p 1 p 3 p 2 0 0 0 p 1 p 3 p 2 0 0 0 p 1 p 3 p 2 p 2 0 0 p 1 p 3 ] k [ x 1 x 2 x 3 x 4 x 5 ] \left[ \begin{matrix} X_{1} \\ X_{2} \\ X_{3} \\ X_{4} \\ X_{5} \end{matrix} \right] =\left[ \begin{matrix} p_{3} & p_{2} & 0 & 0 & p_{1}\\ p_{1} & p_{3} & p_{2} & 0 & 0 \\ 0 & p_{1} & p_{3} & p_{2} & 0 \\ 0 & 0 & p_{1} & p_{3} & p_{2} \\ p_{2} & 0 & 0 & p_{1} & p_{3} \end{matrix} \right]^{k} \left[ \begin{matrix} x_{1} \\ x_{2} \\ x_{3} \\ x_{4} \\ x_{5} \end{matrix} \right] ⎣⎢⎢⎢⎢⎡X1X2X3X4X5⎦⎥⎥⎥⎥⎤=⎣⎢⎢⎢⎢⎡p3p100p2p2p3p1000p2p3p1000p2p3p1p100p2p3⎦⎥⎥⎥⎥⎤k⎣⎢⎢⎢⎢⎡x1x2x3x4x5⎦⎥⎥⎥⎥⎤
Now? , It becomes a matrix fast power board problem , however 500 ∗ 500 ∗ 500 ∗ l o g 1 0 18 ≈ 8 e 9 500*500*500*log10^{18}\approx 8e9 500∗500∗500∗log1018≈8e9, time limit 1 s s s I can't go through it .
Then we should consider optimization .
And then it's up , And something like a cyclic matrix . For the fast power of a cyclic matrix , It can be optimized to o ( n 2 l o g k ) o(n^{2}logk) o(n2logk) Of .
Cheese :
Circulant matrix :
When each row of a matrix is shifted to the right by one column from the previous row ( Move the last column to the first column ) obtain , We call such a matrix Circulant matrix .
nature :
Follow Ring Moment front + Follow Ring Moment front = Follow Ring Moment front Circulant matrix + Circulant matrix = Circulant matrix Follow Ring Moment front + Follow Ring Moment front = Follow Ring Moment front
Follow Ring Moment front × Follow Ring Moment front = Follow Ring Moment front Circulant matrix \times Circulant matrix = Circulant matrix Follow Ring Moment front × Follow Ring Moment front = Follow Ring Moment front
purpose :
One 、 According to the definition and properties of cyclic matrix , We're going to store a cyclic matrix , Just save the first line , The following line can be obtained from the first line .
Two 、 We To calculate a cyclic matrix , Just figure out the first line Just what it is , alike , The following lines can be obtained from the first line .
3、 ... and 、 The cyclic matrix is still a cyclic matrix through linear operation , So let's think The complexity of cyclic matrix multiplied by cyclic matrix , Because we just need to count the first line , therefore Matrix multiplication from the original o ( n 3 ) o(n^{3}) o(n3) Turned into o ( n 2 ) o(n^{2}) o(n2).
then , We find that the matrix of this problem is a cyclic matrix , So it can be optimized to o ( n 2 l o g k ) o(n^{2}logk) o(n2logk) 了 .
Code :
Retention pit , Knock again tomorrow
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
ll fpow(ll a,ll n)
{
ll sum=1,base=a;
while(n!=0)
{
if(n%2)sum=sum*base%mod;
base=base*base%mod;
n/=2;
}
return sum;
}
ll inv(ll a)
{
return fpow(a,mod-2);
}
struct Cmatrix
{
ll mat[505];
}A;
ll len;
Cmatrix mul(Cmatrix A,Cmatrix B)
{
Cmatrix tmp;
for(ll i=0;i<len;i++)
{
tmp.mat[i]=0;
for(int j=0;j<len;j++)
{
tmp.mat[i]=(tmp.mat[i]+A.mat[j]*B.mat[(len-j+i)%len])%mod;
}
}
return tmp;
}
Cmatrix ffpow(Cmatrix A,ll n)
{
Cmatrix sum;
for(ll i=0;i<len;i++)sum.mat[i]=0;
sum.mat[0]=1;
while(n!=0)
{
if(n%2)sum=mul(sum,A);
A=mul(A,A);
n/=2;
}
return sum;
}
ll x[505],X[505];
int main()
{
ll n,k;
scanf("%lld%lld",&n,&k);
len=n;
ll a,b,c;
scanf("%lld%lld%lld",&a,&b,&c);
ll p1=a*inv(a+b+c)%mod;
ll p2=b*inv(a+b+c)%mod;
ll p3=c*inv(a+b+c)%mod;
A.mat[0]=p3;A.mat[len-1]=p1;A.mat[1]=p2;
A=ffpow(A,k);
for(ll i=0;i<len;i++)scanf("%lld",&x[i]);
for(ll i=0;i<len;i++)
{
X[i]=0;
for(ll j=0;j<len;j++)
{
X[i]=(X[i]+x[j]*A.mat[(len-i+j)%len])%mod;
}
}
for(ll i=0;i<len;i++)printf("%lld ",X[i]);
putchar('\n');
return 0;
}
版权声明
本文为[Zimba_]所创,转载请带上原文链接,感谢
https://yzsam.com/2022/04/202204230621425035.html
边栏推荐
- kernel-pwn学习(4)--Double Fetch&&0CTF2018-baby
- JS DOM learn three ways to create elements
- Applet error: should have URL attribute when using navigateto, redirectto or switchtab
- Introduction to sap pi / PO login and basic functions
- Example of data object mask used by SAP translate
- MySQL of database -- Fundamentals
- Kettle实验
- Leetcode0587. 安装栅栏(difficult)
- Less than 100 secrets about prime numbers
- JS node operation, why learn node operation
猜你喜欢
How to use SQL statement union to get another column of another table when the content of a column in a table is empty
PHP笔记(一):开发环境配置
C语言:表达式求值(整型提升、算术转换 ...)
Leetcode0587. Install fence
Cloud computing competition -- basic part of 2020 competition [task 3]
ABAP CDs view with association example
3、 6 [Verilog HDL] gate level modeling of basic knowledge
亚马逊云科技入门资源中心,从0到1轻松上云
Kettle experiment (III)
PHP notes (I): development environment configuration
随机推荐
论文阅读《Integrity Monitoring Techniques for Vision Navigation Systems》
ES-aggregation聚合分析
112. Path sum
ABAP CDs view with association example
Chapter VIII project stakeholder management of information system project manager summary
Principle of synchronized implementation
Yyds dry goods inventory ubuntu18 0.4 install MySQL and solve error 1698: access denied for user ''root' '@' 'localhost' '
DVWA range practice
AQS & reentrantlock implementation principle
Base de la technologie électronique numérique 3.1 aperçu du circuit de porte, 3.2 circuit de porte à diode semi - conductrice
What is monitoring intelligent playback and how to use intelligent playback to query video recording
Leetcode题库78. 子集(递归 c实现)
SAP pi / PO function operation status monitoring and inspection
Integral function and Dirichlet convolution
Solving Lucas number and combination theorem
Two ways for flutter providers to share data
DMP engine work summary (2021, lightsaber)
Number theory blocking (integer division blocking)
Kettle experiment (III)
Applet error: should have URL attribute when using navigateto, redirectto or switchtab