河北建设集团园林网站,python基础教程电子版,wordpress外国人留言,免费网站服务器租用正题
题目链接:https://www.luogu.com.cn/problem/P5371 题目大意
有nnn种牌#xff0c;每种牌最多CCC张#xff0c;XXX个限制形如kik_iki种牌至少aia_iai张。
求所有牌的序号能分成(i,i,i)(i,i,i)(i,i,i)或者(i,i1,i2)(i,i1,i2)(i,i1,i2)的若干组的方案数。 1≤n≤10…正题
题目链接:https://www.luogu.com.cn/problem/P5371 题目大意
有nnn种牌每种牌最多CCC张XXX个限制形如kik_iki种牌至少aia_iai张。
求所有牌的序号能分成(i,i,i)(i,i,i)(i,i,i)或者(i,i1,i2)(i,i1,i2)(i,i1,i2)的若干组的方案数。
1≤n≤1018,0≤X,C≤10001\leq n\leq 10^{18},0\leq X,C\leq 10001≤n≤1018,0≤X,C≤1000 解题思路
看到这个nnn的范围考虑矩阵乘法然后考虑上面那个叠的东西因为(i,i,i)(i,i,i)(i,i,i)能构成一叠所以三个(i,i1,i2)(i,i1,i2)(i,i1,i2)可以分成三个(i,i,i)(i,i,i)(i,i,i)所以这样的话不难发现一个牌最多有666张由前或后构成一叠再进一步的设fi,jf_{i,j}fi,j表示上个选了iii张这一个选了ijijij张此时有i,j≤3i,j\leq 3i,j≤3这样状态数就是999了然后暴力矩阵乘法局部暴力即可。 时间复杂度O(X93lognXC)O(X9^3\log nXC)O(X93lognXC) code
#includecstdio
#includecstring
#includealgorithm
#define ll long long
using namespace std;
const ll S9,P998244353;
struct Matrix{ll a[S][S];
}c,ans,f;
ll n,m,C;
Matrix operator*(const Matrix a,const Matrix b){memset(c.a,0,sizeof(c.a));for(ll i0;iS;i) for(ll j0;jS;j)for(ll k0;kS;k)(c.a[i][j]a.a[i][k]*b.a[k][j]%P)%P;return c;
}
Matrix Solve(ll k){memset(c.a,0,sizeof(c.a));for(ll i0;i9;i){for(ll jk;jC;j){ll xi/3,yxi%3,zj;if(zy)continue;y-x;z-x;ll sy*3(z-y)%3; c.a[i][s];}}return c;
}
void power(Matrix ans,Matrix f,ll b){while(b){if(b1)ansans*f;ff*f;b1;}return;
}
signed main()
{scanf(%lld%lld%lld,n,C,m);ll z0;ans.a[0][0]1;for(ll i1,k,w;im;i){scanf(%lld%lld,k,w);fSolve(0);power(ans,f,k-z-1);ansans*Solve(w);zk;}fSolve(0);power(ans,f,n-z);printf(%lld\n,ans.a[0][0]);return 0;
}
