服务之家做网站简单吗,网站服务器系统盘满了怎么清理,长沙百度百科,网站建设带主机正题
题目链接:https://www.luogu.com.cn/problem/AT5661 题目大意
一个包含A,B,CA,B,CA,B,C的序列#xff0c;每次可以选择相邻的两个除了ABABAB和BABABA的删去。
求有多少个长度为NNN的序列可以删完。 1≤N≤1071\leq N\leq 10^71≤N≤107 解题思路
因为每次是删除一个奇…正题
题目链接:https://www.luogu.com.cn/problem/AT5661 题目大意
一个包含A,B,CA,B,CA,B,C的序列每次可以选择相邻的两个除了ABABAB和BABABA的删去。
求有多少个长度为NNN的序列可以删完。
1≤N≤1071\leq N\leq 10^71≤N≤107 解题思路
因为每次是删除一个奇数位置和一个偶数位置如果我们把所有偶数位置的取反那么就变成了不能删除AAAAAA和BBBBBB。
然后如果在边上AAA一定可以删除非到边界也就是AAA的数量不能超过n2\frac{n}{2}2n同理BBB也是。
然后减去AAA大于的或者BBB大于的就好了因为只能有一个大于
时间复杂度O(n)O(n)O(n) code
#includecstdio
#includecstring
#includealgorithm
#define ll long long
using namespace std;
const ll N1e710,P998244353;
ll n,pw[N],inv[N],fac[N],ans;
ll C(ll n,ll m)
{return fac[n]*inv[m]%P*inv[n-m]%P;}
signed main()
{scanf(%lld,n);pw[0]ansinv[1]1;for(ll i2;in;i)inv[i]P-(P/i)*inv[P%i]%P;inv[0]fac[0]1;for(ll i1;in;i)fac[i]fac[i-1]*i%P,inv[i]inv[i-1]*inv[i]%P;for(ll i1;in;i)ansans*3%P,pw[i]pw[i-1]*2%P;for(ll in/21;in;i)ans(ans-pw[n-i]*C(n,i)%P*2%PP)%P;printf(%lld\n,ans);return 0;
}
