整数对
题目描述
求满足 (0leq xleq n,0leq yleqsqrt{frac{p}{q}}cdot x) 的 ((x,y)) 的整数对个数。
(1leq Tleq 10^5,1leq p,qleq 1000,1leq nleq 10^9)
解法
太棒啦，一道题掌握两个高科技。
这个 (sqrt{frac{p}{q}}) 有点烦，我们用 Stern-Brocot树 来把这个东西拟合成有理数 (frac{a}{b})，我的方式是如果拟合出来的有理数要爆出 (1e17) 了那么我们退出拟合，我们再限定一个拟合次数 (5000)，如果超过这个次数我们就认为精度够了。
剩下的问题变成了求 (sum_{x=0}^nlfloorfrac{ax}{b} floor)，直接搞个类欧几里得就行了。
#include <cstdio>
#include <cmath>
#define int __int128
int read()
{
int x=0,f=1;char c;
while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
return x*f;
}
void write(int x)
{
if(x<0) x=-x,putchar('-');
if(x>9) write(x/10);
putchar(x%10+'0');
}
int T,p,q,n,t;
int work(int n,int a,int b,int c)
{
int ac=a/c,bc=b/c,n1=n+1,m=(a*n+b)/c,f=0;
if(!a) return bc*n1;
if(a>=c || b>=c)
{
f=n*n1/2*ac+n1*bc+work(n,a%c,b%c,c);
return f;
}
f=n*m-work(m-1,c,c-b-1,a);
return f;
}
void find(int a,int b,int c,int d)
{
t++;
if(c>=1e17 || d>=1e17 || t>=5000)
{
write(work(n,a,0,b)+n+1);
puts("");
return ;
}
int m=a+c,n=b+d;
if(n*n*p<m*m*q) find(a,b,m,n);
else find(m,n,c,d);
}
signed main()
{
T=read();
while(T--)
{
t=0;
p=read();q=read();n=read();
find(0,1,1,0);
}
}
序列变换
题目描述
对于一个长度为 (n)，下标为 ([0,n)) 的非负整数序列 (a)，定义变换 (b=f(a,k))，其中 (b) 也是长度为 (n) 的序列，且 (b_i=oplus_{j=0}^{k-1}a_{(i+j)mod n})，问变换 (T) 次之后得到的序列。
(1leq kleq nleq5cdot 10^5,1leq Tleq 10^{18})
解法
这道题变换其实有点复杂，算贡献这个方法是行不通的。
不妨从卷积的角度来理解这个变换，定义乘法为异或起来的卷积，设初始序列的生成函数是 (F(x))，则有：
后面的部分可以暴力卷起来，相当于是在模 (2) 意义下的卷积，但是 (O(nlog klog n)) 直接 ( t T) 飞了。
有一个神奇结论：((1+x...+x^{k-1})^{2^t}=1+x^{2^t}...+x^{(k-1)2^t})，这个可以归纳证明，不是自己乘自己的项的系数都是 (2) 的倍数，所以都被模掉了，然后一直归纳上来即可。
(F(x) imes(1+x...+x^{k-1})^Tmod(x^n-1)) 是可以 (O(n)) 算的，就把每一类的东西取出来，然后做一个类似前缀和的东西就行了，讨论一下 (k) 大于整类的情况，所以直接二进制拆分 (O(nlog T))
#include <cstdio>
#include <vector>
using namespace std;
#define int long long
const int M = 500005;
int read()
{
int x=0,f=1;char c;
while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
return x*f;
}
int n,k,t,a[M],b[M],vis[M];vector<int> v;
void work(int x)
{
for(int i=0;i<n;i++)
{
v.clear();
if(!vis[i])
{
//取出这一类所有的元素
int ans=0;
for(int j=i;!vis[j];j=(j+x)%n)
vis[j]=1,v.push_back(j),ans^=a[j];
if((k/v.size())%2==0) ans=0;//否则可以取遍整类
int u=k%v.size();
for(int j=0;j<u;j++)
ans^=a[v[j]];
for(int j=0;j<v.size();j++)
{
b[v[j]]=ans;
ans^=a[v[j]];
ans^=a[v[(j+u)%v.size()]];
}
}
}
for(int i=0;i<n;i++) a[i]=b[i],b[i]=vis[i]=0;
}
signed main()
{
n=read();k=read();t=read();
for(int i=0;i<n;i++)
a[i]=read();
for(int p=1;t;p<<=1)
if(t&p)
{
t^=p;
work(p%n);
}
for(int i=0;i<n;i++) printf("%d ",a[i]);
}