电子商务网站流程图,微商做网站,soho网站建设教程,网站编写语言1.洛谷 P1962 斐波那契数列
题意
大家都知道#xff0c;斐波那契数列是满足如下性质的一个数列#xff1a; F n { 1 ( n ≤ 2 ) F n − 1 F n − 2 ( n ≥ 3 ) F_n \left\{\begin{aligned} 1 \space (n \le 2) \\ F_{n-1}F_{n-2} \space (n\ge 3) \end{aligned}\right. …1.洛谷 P1962 斐波那契数列
题意
大家都知道斐波那契数列是满足如下性质的一个数列 F n { 1 ( n ≤ 2 ) F n − 1 F n − 2 ( n ≥ 3 ) F_n \left\{\begin{aligned} 1 \space (n \le 2) \\ F_{n-1}F_{n-2} \space (n\ge 3) \end{aligned}\right. Fn{1 (n≤2)Fn−1Fn−2 (n≥3)
请你求出 F n m o d 1 0 9 7 F_n \bmod 10^9 7 Fnmod1097 的值。 1 ≤ n 2 63 1\le n 2^{63} 1≤n263。
思路 [ F i − 1 F i ] [ F i − 2 F i − 1 ] ⋅ [ 0 1 1 1 ] \begin{bmatrix} F_{i-1} F_{i} \end{bmatrix} \begin{bmatrix} F_{i-2} F_{i-1} \end{bmatrix}\cdot \begin{bmatrix} 0 1\\ 1 1 \end{bmatrix} [Fi−1Fi][Fi−2Fi−1]⋅[0111]
2.SMOJ 数列1
题意
有一个数列 f n { 0 ( n ≤ 2 ) 7 f n − 1 6 f n − 2 4 × 3 n ( n ≥ 3 ) f_n \left\{\begin{aligned} 0 \ (n \le 2) \\ 7f_{n-1}6f_{n-2}4\times 3^n \ (n\ge 3) \end{aligned}\right. fn{0 (n≤2)7fn−16fn−24×3n (n≥3)
请你求出 f n m o d 1 0 9 7 f_n \bmod 10^9 7 fnmod1097 的值。 3 ≤ n ≤ 1 0 9 3\le n \le 10^9 3≤n≤109。
思路 [ f i − 1 f i 4 × 3 i 1 ] [ f i − 2 f i − 1 4 × 3 i ] ⋅ [ 0 6 0 1 7 0 0 1 3 ] \begin{bmatrix} f_{i-1} f_i 4\times3^{i1}\end{bmatrix}\begin{bmatrix} f_{i-2} f_{i-1} 4\times 3^i\end{bmatrix}\cdot \begin{bmatrix} 0 6 0\\ 1 7 0\\ 0 1 3 \end{bmatrix} [fi−1fi4×3i1][fi−2fi−14×3i]⋅ 010671003
3.SMOJ 数列2
题意
有一个数列 f n { 0 ( n ≤ 2 ) 7 f n − 1 6 f n − 2 4 × 3 n 5 n ( n ≥ 3 ) f_n \left\{\begin{aligned} 0 \ (n \le 2) \\ 7f_{n-1}6f_{n-2}4\times 3^n5n \ (n\ge 3) \end{aligned}\right. fn{0 (n≤2)7fn−16fn−24×3n5n (n≥3)
请你求出 f n m o d 1 0 9 7 f_n \bmod 10^9 7 fnmod1097 的值。
思路 [ f i − 1 f i 4 × 3 i 1 5 ( i 1 ) 5 ] [ f i − 2 f i − 1 4 × 3 i 5 i 5 ] ⋅ [ 0 6 0 1 0 1 7 0 1 0 0 1 3 1 0 0 1 0 1 0 0 0 0 1 1 ] \begin{bmatrix} f_{i-1} f_i 4\times 3^{i1} 5(i1) 5 \end{bmatrix} \begin{bmatrix} f_{i-2} f_{i-1} 4\times 3^i 5i 5 \end{bmatrix}\cdot\begin{bmatrix} 0 6 0 1 0\\ 1 7 0 1 0\\ 0 1 3 1 0\\ 0 1 0 1 0\\ 0 0 0 1 1 \end{bmatrix} [fi−1fi4×3i15(i1)5][fi−2fi−14×3i5i5]⋅ 0100067110003001111100001
4.SMOJ 幸运数
题意
小明认为只有数字 4 4 4 和 7 7 7 是幸运数字其他数字都不是。如果一个整数的每个数字都是幸运数字那么该整数就是幸运整数。
给出一个数组 n u m b e r s 1... n numbers_{1...n} numbers1...n。
一个长度为 L L L 的幸运数列 A 0... L − 1 A_{0...L-1} A0...L−1 必须同时满足 ∀ i ∈ [ 0 , L ) \forall i\in[0,L) ∀i∈[0,L) A i A_i Ai 必须是幸运整数。 ∀ i ∈ [ 0 , L ) \forall i\in[0,L) ∀i∈[0,L) A i A_i Ai 的最后一个数字必须等于 A [ i 1 ] A[i1] A[i1] 的第一个数字。 ∀ i ∈ [ 0 , L ) \forall i\in[0,L) ∀i∈[0,L)至少存在一个下标 j j j 满足 A i n u m b e r s j A_inumbers_j Ainumbersj。
输出有多少个不同的长度为L的幸运序列答案模 1234567891 1234567891 1234567891。
对于两个长度都是L的幸运序列 A 0... L − 1 A_{0...L- 1} A0...L−1 和 B 0... L − 1 B_{0...L - 1} B0...L−1他们被认为是不同序列的条件是 ∃ i , A i ≠ B i \exist i,A_i\neq B_i ∃i,AiBi。 1 ≤ n ≤ 50 , 1 ≤ n u m b e r s i ≤ 1 0 9 , 1 ≤ L ≤ 1 0 9 1\le n\le 50,1\le numbers_i\le 10^9,1\le L\le 10^9 1≤n≤50,1≤numbersi≤109,1≤L≤109
思路
对所有幸运数分类 4 4 4 头 4 4 4 尾 4 4 4 头 7 7 7 尾 7 7 7 头 4 4 4 尾 7 7 7 头 7 7 7 尾
用一个桶 c n t cnt cnt 记个数。
令 f i , t y p e f_{i,type} fi,type 表示前 i i i 个幸运数组成的序列中序列最后一个数种类为 t y p e ∈ [ 1 , 4 ] type\in [1,4] type∈[1,4] 的方案数。
那么容易写出转移式子 f i , 1 f i − 1 , 1 ⋅ c n t 1 f i − 1 , 3 ⋅ c n t 1 f_{i,1}f_{i-1,1}\cdot cnt_1f_{i-1,3}\cdot cnt_1 fi,1fi−1,1⋅cnt1fi−1,3⋅cnt1 f i , 2 f i − 1 , 1 ⋅ c n t 2 f i − 1 , 3 ⋅ c n t 2 f_{i,2}f_{i-1,1}\cdot cnt_2f_{i-1,3}\cdot cnt_2 fi,2fi−1,1⋅cnt2fi−1,3⋅cnt2 f i , 3 f i − 1 , 2 ⋅ c n t 3 f i − 1 , 4 ⋅ c n t 3 f_{i,3}f_{i-1,2}\cdot cnt_3f_{i-1,4}\cdot cnt_3 fi,3fi−1,2⋅cnt3fi−1,4⋅cnt3 f i , 4 f i − 1 , 2 ⋅ c n t 4 f i − 1 , 4 ⋅ c n t 4 f_{i,4}f_{i-1,2}\cdot cnt_4f_{i-1,4}\cdot cnt_4 fi,4fi−1,2⋅cnt4fi−1,4⋅cnt4
只需做 L L L 次 dp 即可但是 L L L 最大去到 1 0 9 10^9 109显然会炸。由于操作单调因此考虑矩阵快速幂优化 [ f i , 1 f i , 2 f i , 3 f i , 4 ] [ f i − 1 , 1 f i − 1 , 2 f i − 1 , 3 f i − 1 , 4 ] ⋅ [ c n t 1 c n t 2 0 0 0 0 c n t 3 c n t 4 c n t 1 c n t 2 0 0 0 0 c n t 3 c n t 3 ] \begin{bmatrix} f_{i,1} f_{i,2} f_{i,3} f_{i,4} \end{bmatrix}\begin{bmatrix} f_{i-1,1} f_{i-1,2} f_{i-1,3} f_{i-1,4} \end{bmatrix}\cdot\begin{bmatrix} cnt_1 cnt_2 0 0\\ 0 0 cnt_3 cnt_4\\ cnt_1 cnt_2 0 0\\ 0 0 cnt_3 cnt_3 \end{bmatrix} [fi,1fi,2fi,3fi,4][fi−1,1fi−1,2fi−1,3fi−1,4]⋅ cnt10cnt10cnt20cnt200cnt30cnt30cnt40cnt3
代码
#includebits/stdc.h
using namespace std;
#define ll long long
const ll N102,mod1234567891;
struct matrix
{ll row,col;ll data[N][N];matrix(ll r,ll c,ll isI){rowr;colc;memset(data,0,sizeof(data));if(isI){for(int i1;irow;i)data[i][i]1;}}
};
matrix operator * (const matrix a,const matrix b)
{matrix c(a.row,b.col,0);for(int i1;ia.row;i)for(int j1;jb.col;j)for(int k1;ka.col;k)c.data[i][j](c.data[i][j]a.data[i][k]*b.data[k][j]%modmod)%mod;return c;
}
matrix qpow_matrix(matrix a,ll k)
{matrix ret(a.row,a.col,1);while(k){if(k1)retret*a;aa*a;k1;}return ret;
}
ll n,m,a[N];
ll f[N][5],cnt[5];
ll type(string x)
{ll sxx.size();x*x;for(int i1;isx;i)if(x[i]!4x[i]!7)return 0;if(x[1]4x[sx]4)return 1;else if(x[1]4x[sx]7)return 2;else if(x[1]7x[sx]4)return 3;else return 4;
}
vectorstringluk[N];
int main()
{scanf(%lld%lld,n,m);for(int i1;in;i){string a;cina;ll ttype(a);if(!t)continue;bool flag1;for(auto x:luk[t]){if(xa){flag0;break;}}if(flag)luk[t].push_back(a),cnt[t];}matrix A(1,4,0);matrix B(4,4,0);for(int i1;in;i)A.data[1][i]cnt[i];B.data[1][1]B.data[3][1]cnt[1];B.data[1][2]B.data[3][2]cnt[2];B.data[2][3]B.data[4][3]cnt[3];B.data[2][4]B.data[4][4]cnt[4];AA*qpow_matrix(B,m-1);ll ans0;for(int i1;i4;i)ans(ansA.data[1][i])%mod;printf(%lld,ans);return 0;
}5.SMOJ 序列/CF691E Xor-sequences
题意
给定一个数集 A A A现在你需要构造一个长度为 m m m 的序列 B B B序列 B B B 的元素从数集 A A A 中任意挑选要求 B B B 中任意相邻的两个数字的异或值二进制表示中 1 1 1 的个数是 3 3 3 的倍数请问 B B B 的有多少种合法的构造方案两种方案不同当且仅当存在 b i b_i bi 在 A A A 中的位置不同。 1 ≤ n ≤ 100 , 1 ≤ m ≤ 1 0 18 , 0 ≤ a i ≤ 1 0 18 1\le n\le 100,1\le m\le 10^{18},0\le a_i\le 10^{18} 1≤n≤100,1≤m≤1018,0≤ai≤1018
思路
设 f i , j f_{i,j} fi,j 表示选择了 i i i 个数最后一个数是 a j a_j aj 的方案数注意数列可以乱序那么有 f i , j ∑ k 1 n f i − 1 , k ⋅ A i , j f_{i,j}\sum_{k1}^{n}f_{i-1,k}\cdot\ A_{i,j} fi,jk1∑nfi−1,k⋅ Ai,j
其中 A i , j A_{i,j} Ai,j 表示 A i , j [ a j ⨁ a k m o d 3 0 ] A_{i,j}\left [a_j\bigoplus a_k \bmod30\right ] Ai,j[aj⨁akmod30]
中括号为艾弗森括号不难发现 A A A 以对角线对称。
对于每个 ( i , j ) (i,j) (i,j)都要遍历 k ∈ [ 1 , n ] k\in[1,n] k∈[1,n] 来逐一比对一遍是否有 a j ⨁ a k m o d 3 0 a_j\bigoplus a_k \bmod30 aj⨁akmod30。如此过程实则与矩阵乘法的运算过程比较相似这还是比较注意力惊人了除非你对矩阵无比的熟悉那么不妨使用矩阵快速幂优化了。最终答案就是 a n s ∑ d a t a ( A n − 1 ) ans\sum data(A^{n-1}) ans∑data(An−1) d a t a ( M ) data(M) data(M) 表示一个矩阵 M M M 内所有元素。
#includebits/stdc.h
using namespace std;
#define ll long long
const ll N102,mod1e97;
struct matrix
{ll row,col;ll data[N][N];matrix(ll r,ll c,ll isI){rowr;colc;memset(data,0,sizeof(data));if(isI){for(int i1;irow;i)data[i][i]1;}}
};
matrix operator * (const matrix a,const matrix b)
{matrix c(a.row,b.col,0);for(int i1;ia.row;i)for(int j1;jb.col;j)for(int k1;ka.col;k)c.data[i][j](c.data[i][j]a.data[i][k]*b.data[k][j]%modmod)%mod;return c;
}
matrix qpow_matrix(matrix a,ll k)
{matrix ret(a.row,a.col,1);while(k){if(k1)retret*a;aa*a;k1;}return ret;
}
ll n,m,a[N];
ll popcnt(ll x)
{ll ret0;while(x){if(x1)ret;x1;}return ret;
}
int main()
{scanf(%lld%lld,n,m);for(int i1;in;i)scanf(%lld,a[i]);matrix A(n,n,0);for(int i1;in;i)for(int j1;jn;j)A.data[i][j](popcnt(a[i]^a[j])%30);Aqpow_matrix(A,m-1);ll ans0;for(int i1;in;i)for(int j1;jn;j)ans(ansA.data[i][j])%mod;printf(%lld,ans);return 0;
}6.SMOJ 黑板与数字/CF621E Wet Shark and Blocks
本篇较口胡见谅
题意
有 b b b 个黑板从左往右排成一行。
第 1 1 1 个黑板从左往右写有 n n n 个数字每个数字是 1 1 1 至 9 9 9 范围内的数字。
把第 1 1 1 个黑板的所有数字复制一份写到第 2 2 2 个黑板。
把第 1 1 1 个黑板的所有数字复制一份写到第 3 3 3 个黑板。
把第 1 1 1 个黑板的所有数字复制一份写到第 b b b 个黑板。
从这 b b b 个黑板中各取一个数字构成一个 b b b 位数要使得这个 b b b 位数模 x x x 的结果是 k k k求方案数同一个黑板内取相同的数字算不同方案因为位置不同答案模 1 0 9 7 10^97 1097。
思路
令 f i , j f_{i,j} fi,j 表示选了 i i i 个格子模 x x x 余数为 j j j那么有转移式子 f i , 10 j k m o d x f i − 1 , j n u m ( k ) f_{i,10jk \bmod x}f_{i-1,j}num(k) fi,10jkmodxfi−1,jnum(k)
其中 n u m ( k ) num(k) num(k) 表示 n u m ( k ) ∑ i 1 n [ a i m o d x k ] num(k)\sum_{i1}^n [a_i\bmod xk] num(k)i1∑n[aimodxk]
再枚举每一位去到了 Θ ( b x ) \Theta(bx) Θ(bx)但是如此操作像上几篇题解一样与矩阵乘法相类似因此可以考虑矩阵快速幂优化到 Θ ( log 2 b ) \Theta(\log_2b) Θ(log2b)
代码
#includebits/stdc.h
using namespace std;
#define ll long long
const ll N111,mod1e97;
ll n,b,k,x,a,yx[N];
struct matrix
{ll row,col;//行和列ll data[N][N];matrix(ll r,ll c,ll isI){rowr;colc;memset(data,0,sizeof(data));if(isI){for(int i0;irow;i)data[i][i]1;}}
};
matrix operator * (const matrix a,const matrix b)
{matrix c(a.row,b.col,0);for(int i0;ia.row;i)for(int j0;jb.col;j)for(int k0;ka.col;k)c.data[i][j](c.data[i][j]a.data[i][k]*b.data[k][j]%modmod)%mod;return c;
}
matrix qpow_matrix(matrix a,ll k)
{matrix res(a.row,a.col,1);while(k){if(k1)resres*a;aa*a;k1;}return res;
}
int main()
{scanf(%lld%lld%lld%lld,n,b,k,x);for(int i1;in;i){scanf(%lld,a);yx[a%x];}matrix A(1,x,0);for(int i0;ix;i)A.data[0][i]yx[i];matrix B(x,x,0);for(int i0;ix;i){for(int j0;jx;j){ll r(i*10j)%x;B.data[i][r]yx[j];}}AA*qpow_matrix(B,b-1);printf(%lld,A.data[0][k]);return 0;
}
