ABC137F
题意：
给定一个素数\(p\)和\(a_0\sim a_{p-1}\in\{0,1\}\)
找到至多\(p-1\)次的多项式\(f(x)=\sum_{i=0}^{p-1}b_ix^i(b_i\in[0,p-1])\)
满足\(f(i)\equiv a_i\ (mod\ p)\)
\(2\leq p<3000\)
题解：
神仙构造题，这个其实很像中国剩余定理，而且\(p\)是素数满足费马小定理，\(a_i\)满足只有\(0\)和\(1\)，考虑构造：
如果\(a_i=1\)，那么\(f(x)+=(g(x)=1-(x-i)^{p-1})\)
这个\(g(x)\)当且仅当\(x=i\)时，\(g(x)=1\)，其他情况下因为费马小定理，后面那一项等于\(1\)，总体等于零，不会对其他项造成影响。
这个式子用二项式定理直接展开。
#include<bits/stdc++.h>
using namespace std;
namespace red{
#define int long long
#define double long double
#define ls(p) (p<<1)
#define rs(p) (p<<1|1)
#define lowbit(i) ((i)&(-i))
#define mid ((l+r)>>1)
#define eps (1e-15)
const int N=1e6+10,mod=998244353,inf=2e15;
void __init(int n=2000) {}
inline void main()
{
auto fast=[&](int x,int k,int mod) -> int
{
int ret=1;
while(k)
{
if(k&1) ret=ret*x%mod;
x=x*x%mod;
k>>=1;
}
return ret;
};
int n;
cin>>n;
vector<int> a(n);
for(int i=0;i<n;++i)
{
int x;
cin>>x;
if(!x) continue;
//1-(x-i)^{n-1}
++a[0];
int pw=1,com=1;
for(int j=n-1;~j;--j)
{
a[j]-=pw*com%n;
a[j]%=n;
pw=pw*(-i)%n;
com=com*j%n*fast(n-j,n-2,n)%n;
}
}
for(int i=0;i<n;++i)
{
cout<<(a[i]+n)%n<<' ';
}
}
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
red::__init();
int qwq=1; //cin>>qwq;
while(qwq--) red::main();
return 0;
}
/*
1 7 5 6 8 2 6 5
0 8 5 6 8 0 8 5
3
5 6 5
3 8 5
2
3
8
*/
ABC138F
题意：
给定\(L,R\)，求有多少对数字\(L\leq x\leq y\leq R\)，满足\(x\mod y=x\oplus y\)
\(0\leq L\leq R\leq 10^{18}\)
模\(1e9+7\)
题解：
转化一下取模
如果\(2x\leq y\)，那么\(y-x>y\%x\)
如果\(2x>y\)，那么\(y-x=y\%x\)
\(x\oplus y\geq y-x\)
所以如果\(2x\leq y\)，不可能满足要求。
\(2x>y\)时，
\(x\)和\(y\)二进制下的最高位相同，如果要满足\(y-x=y\oplus x\)，那么\(y\&x=x\)
总结一下就是\(x,y\)的二进制位数相同，而且\(y\&x=x\)
考虑数位\(dp\)，但是很难容斥，用另一种状态设置，\(dp[pos][x1][x2]\)表示第\(pos\)位，是否到达下界，是否到达上界。
#include<bits/stdc++.h>
using namespace std;
namespace red{
#define int long long
#define double long double
#define ls(p) (p<<1)
#define rs(p) (p<<1|1)
#define lowbit(i) ((i)&(-i))
#define mid ((l+r)>>1)
#define eps (1e-15)
const int N=1e6+10,mod=1e9+7,inf=2e15;
void __init(int n=2000) {}
inline void main()
{
int l,r;
cin>>l>>r;
vector<int> d,u;
vector dp(100,vector(2,vector<int>(2,-1)));
function<int(int,int,int)> dfs=[&](int pos,int x1,int x2) -> int
{
if(pos<0) return 1;
if(~dp[pos][x1][x2]) return dp[pos][x1][x2];
int &ret=dp[pos][x1][x2];ret=0;
int t1=x1?d[pos]:0,t2=x2?u[pos]:1;
for(int y=t1;y<=t2;++y)
for(int x=t1;x<=y;++x)
ret=(ret+dfs(pos-1,x1&(x==t1),x2&(y==t2)))%mod;
return ret;
};
auto solve=[&](int l,int r) -> int
{
while(l) d.emplace_back(l&1),l>>=1;
while(r) u.emplace_back(r&1),r>>=1;
// reverse(d.begin(),d.end());
// reverse(u.begin(),u.end());
int ans=0,tl=d.size(),tr=u.size();
for(int i=tl;i<=tr;++i) ans=(ans+dfs(i-2,i==tl,i==tr))%mod;
return ans;
};
cout<<solve(l,r)<<'\n';
}
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
red::__init();
int qwq=1; //cin>>qwq;
while(qwq--) red::main();
return 0;
}
/*
1 7 5 6 8 2 6 5
0 8 5 6 8 0 8 5
3
5 6 5
3 8 5
2
3
8
*/
CF1717E
题意：
求
\[\sum_{a+b+c=n}lcm(c,gcd(a,b)) \]\(n\leq 10^5\)
题解：
额
枚举\(gcd(a,b)=d\)
然后枚举\(a+b=t*d\)的\(t\)，这里是调和级数。
那么\(c=n-t*d\)
然后就想知道有多少对\((a,b)\)，满足\(a+b=t\)且\(gcd(a,b)=1\)
如果\(a\)和\(b\)互质，那么\(a\)和\(a+b\)互质。
且\(a+b=t\)，所以\(a\)和\(t\)互质。
所以这个数量等于\(\varphi(t)\)
#include<bits/stdc++.h>
using namespace std;
namespace red{
#define int long long
#define double long double
#define ls(p) (p<<1)
#define rs(p) (p<<1|1)
#define lowbit(i) ((i)&(-i))
#define mid ((l+r)>>1)
#define eps (1e-15)
const int N=1e6+10,mod=1e9+7,inf=2e15;
void __init(int n=2000) {}
inline void main()
{
auto lcm=[&](int x,int y) -> int
{
return x*y/__gcd(x,y);
};
int n;
cin>>n;
vector<int> phi(n+1);
iota(phi.begin(),phi.end(),0);
for(int i=1;i<=n;++i)
{
for(int j=2*i;j<=n;j+=i) phi[j]-=phi[i];
}
int ans=0;
for(int d=1;d<=n-2;++d)
{
for(int g=2*d;g<=n;g+=d)
{
int c=n-g;
ans=(ans+lcm(c,d)*phi[g/d])%mod;
}
}
cout<<ans<<'\n';
}
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
red::__init();
int qwq=1; //cin>>qwq;
while(qwq--) red::main();
return 0;
}
/*
1 7 5 6 8 2 6 5
0 8 5 6 8 0 8 5
3
5 6 5
3 8 5
2
3
8
*/