做网站虚拟主机和云服务器,做网站应该画什么图,企业网站建设前期规划,wordpress 如何制作模板下载传送门 文章目录题意#xff1a;思路题意#xff1a;
有nnn个细胞#xff0c;你初始在第nnn细胞上#xff0c;假设你当前在xxx处#xff0c;你每次可以进行如下两个操作#xff1a; (1)(1)(1)选择[1,x−1][1,x-1][1,x−1]内一个数yyy#xff0c;跳到第x−yx-yx−y个细胞…传送门 文章目录题意思路题意
有nnn个细胞你初始在第nnn细胞上假设你当前在xxx处你每次可以进行如下两个操作
(1)(1)(1)选择[1,x−1][1,x-1][1,x−1]内一个数yyy跳到第x−yx-yx−y个细胞上。
(2)(2)(2)选择[2,x][2,x][2,x]之间的一个数zzz跳到⌊xz⌋\left \lfloor \frac{x}{z} \right \rfloor⌊zx⌋。
问你有多少种不同的方式到达111号细胞。
2≤n≤4e62\le n\le 4e62≤n≤4e6
思路
如果直接按照题意来设计状态f[i]f[i]f[i]表示从nnn到iii的方案数那么第一个操作显然可以用一个变量打一个标记第二个可以整除分块将iii这个点的贡献分配给⌊xz⌋\left \lfloor \frac{x}{z} \right \rfloor⌊zx⌋。
复杂度O(nn)O(n\sqrt n)O(nn)
这个只能通过简单版本要通过这个题的话显然需要优化其实不难发现他与倍数有关。
我们考虑倒着来设计状态f[i]f[i]f[i]表示从iii到111的方案数那么f[1]1f[1]1f[1]1。
假设当前枚举的点是kkk考虑⌊xz⌋k\left \lfloor \frac{x}{z} \right \rfloork⌊zx⌋k这个式子代表从xxx点能到当前点kkk由于我们是倒着来的那么也就是kkk这个点可以转移到xxx考虑枚举zzz那么能转移到的区间就是[k∗z,k∗zz−1][k*z,k*zz-1][k∗z,k∗zz−1]通过枚举倍数让后打一个标记即可。
复杂度O(nlogn)O(nlogn)O(nlogn)
// Problem: D1. Up the Strip (simplified version)
// Contest: Codeforces - Codeforces Round #740 (Div. 2, based on VK Cup 2021 - Final (Engine))
// URL: https://codeforces.com/contest/1561/problem/D1
// Memory Limit: 128 MB
// Time Limit: 6000 ms
//
// Powered by CP Editor (https://cpeditor.org)//#pragma GCC optimize(Ofast,no-stack-protector,unroll-loops,fast-math)
//#pragma GCC target(sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tunenative)
//#pragma GCC optimize(2)
#includecstdio
#includeiostream
#includestring
#includecstring
#includemap
#includecmath
#includecctype
#includevector
#includeset
#includequeue
#includealgorithm
#includesstream
#includectime
#includecstdlib
#includerandom
#includecassert
#define X first
#define Y second
#define L (u1)
#define R (u1|1)
#define pb push_back
#define mk make_pair
#define Mid ((tr[u].ltr[u].r)1)
#define Len(u) (tr[u].r-tr[u].l1)
#define random(a,b) ((a)rand()%((b)-(a)1))
#define db puts(---)
#define lowbit(x) (x(-x))
using namespace std;//void rd_cre() { freopen(d://dp//data.txt,w,stdout); srand(time(NULL)); }
//void rd_ac() { freopen(d://dp//data.txt,r,stdin); freopen(d://dp//AC.txt,w,stdout); }
//void rd_wa() { freopen(d://dp//data.txt,r,stdin); freopen(d://dp//WA.txt,w,stdout); }typedef long long LL;
typedef unsigned long long ULL;
typedef pairint,int PII;const int N5000010,INF0x3f3f3f3f;
const double eps1e-6;int n,mod;
LL a[N],f[N];int main()
{
// ios::sync_with_stdio(false);
// cin.tie(0);scanf(%d%d,n,mod);f[1]1; LL add0;for(int i1;in;i) {a[i]a[i-1]; a[i]%mod;f[i]addf[i]a[i]; f[i]%mod;addf[i]; add%mod;for(int j2;1ll*j*in;j) {int lj*i,rj*ij-1; rmin(r,n1);a[l]f[i]; a[r1]-f[i];a[l]%mod; a[r1]%mod; a[r1]mod; a[r1]%mod;}}coutf[n]%modendl;return 0;
}
/*1 2 3 4 5 6 7 8
1- 2 3 4 5 6 7 8
2- [4,5] */
