NOI2016 循环之美
题意
题意
求能用 $\frac{x}{y}(1\leq x\leq n,1\leq y\leq m)$ 表示的 $k$ 进制下纯循环小数个数 $n,m\leq 10^9,k\leq 2000$
求能用 $\frac{x}{y}(1\leq x\leq n,1\leq y\leq m)$ 表示的 $k$ 进制下纯循环小数个数 $n,m\leq 10^9,k\leq 2000$
给定$p$.
$q$ 次询问,给定 $a,b$ ,定义 $f_0=a,f_1=b,f_i=f_{i-1}+f_{i-2}$ ,求 $f_i\mod p=0$ 的最小整数解 $i$
$p,q 10^5$ ($p$不一定是质数)
题意:有一群卷王坐成一排,第 $i$ 个人卷了 $a_i$ 题,每次所有人会往同一个方向看(往前或者往后),如果最近的人题数比自己多,就多卷一个题(如果这个人和你一样,但他卷了一题,那你也要卷一题),求 $m$ 次后 每个卷王的题数。
有$n$个数$a_1\dots a_n$,进行 $m$ 次操作,分两种:
for(int i=2;i<=n;++i)if(a[i-1]>a[i])++a[i];//1
for(int i=n-1;i;--i)if(a[i+1]>a[i])++a[i];//2
求操作结束后$a_1\dots a_n$的值。
$n,m\leq 3\times 10^5,6s$
已知 $x$ 满足 $l\leq x\leq r$ ,现在每次能询问一个 $y(0\leq y\leq s)$ ,第 $i$ 次会回答 $ix\geq y$是否成立。
求最少的次数,使得能确定 $x$ 在一个长度 $\leq t$ 的区间内。
$q\leq 100$。
定义$f(n)=\sum_{i=1}^k fib_i^n a_i$,其中$fib_1=1,fib_2=2,fib_n=fib_{n-1}+fib_{n-2}$
已知$f(1)\dots f(k)$,求$f(k+1)$。
所有运算对质数$M$取模,保证$fib_i$模$m$后两两不同,保证存在唯一解。
需要使用$O(k^2)$的做法。