cf 621E. Wet Shark and Blocks

神奇，矩阵乘法23333333333333333

递推式是很简单的（连我这种不会DP的人都写出来了。）

需要求出的是转移矩阵（还是叫系数矩阵的），也是最这个东西用快速幂。

这个东西的i，j大概就表示从i到j的方案数，那么原始的状态肯定是f[0]=1;对应的矩阵也就是[1,0,0,0,0,0,0,,,,,,]

貌似为了方便？？！！这个矩阵貌似可以转化成f[i][i]=1的矩阵。。。所以。。（太BT了，，，还是我太垃圾）

还有最后的答案输出，想了想data[?][kk],？是什么也不好，一开始是0位，答案求的也是从0到b位的，所以就data[0][kk]吧。。（简直乱搞）

 #include<bits/stdc++.h>

 #define inf 0x7fffffff

 #define LL long long

 #define N 100005

 using namespace std;

 inline int ra()

 {

     int x=,f=; char ch=getchar();

     while (ch<'' || ch>'') {if (ch=='-') f=-; ch=getchar();}

     while (ch>='' && ch<='') {x=x*+ch-''; ch=getchar();}

     return x*f;

 }

 const int mod=1e9+;

 int a[];

 struct maxtri{

     int n;

     LL data[][];

     maxtri(int tn=)

     {

         n=tn;

         for (int i=; i<n; i++)

             for (int j=; j<n; j++)

                 data[i][j]=;

     }

     void init()

     {

         for (int i=; i<n; i++) data[i][i]=;

     }

 };

 maxtri operator *(maxtri a, maxtri b)

 {

     maxtri c(a.n);

     int n=a.n;

     for (int i=; i<n; i++)

         for (int j=; j<n; j++)

             for (int k=; k<n; k++)

                 c.data[i][j]=(c.data[i][j]+a.data[i][k]*b.data[k][j]%mod)%mod;

     return c;

 }

 maxtri ksm(maxtri a, int b)

 {

     maxtri t(a.n),ans(a.n);

     ans.init(); t=a;

     while (b)

     {

         if (b&) ans=ans*t;

         t=t*t;

         b>>=;

     }

     return ans;

 }

 int main()

 {

     int n=ra(),b=ra(),kk=ra(),x=ra();

     for (int i=; i<=n; i++)

         a[ra()]++;

     maxtri tmp(x);

     for (int i=; i<x; i++)

         for (int j=; j<x; j++)

             for (int k=; k<; k++)

                 if ((i*+k)%x==j) tmp.data[i][j]+=a[k];

     maxtri ans(x);

     ans=ksm(tmp,b);

     cout<<ans.data[][kk];

     return ;

 }

巴特西

cf 621E. Wet Shark and Blocks

最新文章

热门文章