6-28
T1二分哥
Um_nik 是一个很强的 Codeforces 选手。
Petr 也是一个很强的 Codeforces 选手。
对于某个排列，我们定义一次“交换”为选择两个不同的位置将他们交换。他们两个人各自拿到一个长度为 n 的初始升序的排列，随后 Um_nik 会将这个排
列“交换”7n + 1 次，而 Petr 会将这个排列“交换”3n 次。
给你一个进行若干次交换后的排列，你需要判断这个排列是由谁进行操作得到的。
O(n)构造出一个能使序列还原的方案，将操作数的奇偶性与3x和7x+1比较即可。
std:
#include<bits/stdc++.h>
using namespace std;
int t,n,op,a[2500005],p[2500005],cnt;
#include <vector>
struct Generator{
std::vector<int> num;
bool vis[2500005];
int cnt[2500005];
typedef unsigned int ui;
ui a,b,x;ui getnum()
{
return x=a*x+b;
}
std::vector<int> get_permutation(int n,ui a_,ui b_)
{
a=a_;
b=b_;
x=0;
std::vector<int> per;
for(int i=1;i<=n;i++)
{
per.emplace_back(getnum()%n+1);
cnt[per.back()]++;
}
for(int i=1;i<=n;i++)
{
cnt[i]+=cnt[i-1];
}
for(int i=0;i<n;i++) per[i]=cnt[per[i]]--;
for(int i=1;i<=n;i++) cnt[i]=0;
return per;
}
}gen;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>t;
while(t--)
{
cnt=0;
cin>>n>>op;
if(op==0)
{
for(int i=1;i<=n;i++)
{
cin>>a[i];
p[a[i]]=i;
}
}
if(op==1)
{
unsigned sda,sdb;
cin>>sda>>sdb;
auto t=gen.get_permutation(n,sda,sdb);
for(int i=1;i<=n;i++)
{
a[i]=t[i-1];
p[a[i]]=i;
}
}
for(int i=1;i<=n;i++)
{
if(a[i]!=i)
{
int t=a[i];
swap(a[i],a[p[i]]);
swap(p[i],p[t]);
cnt++;
}
}
if((cnt&1)==((n*3)&1)) cout<<"Petr\n";
else cout<<"Um_nik\n";
}
}
T2匹配
哈娜有一棵树。哈娜喜欢一些稳定的匹配，因此哈娜希望这棵树的最大匹配唯一。显然有些情况下原来的树可能不满足这个性质，因此哈娜想在树上断开几条边，使得断边之后的树（其实应该叫森林了）最大匹配唯一。你需要帮助哈娜求出有多少种删边方案使得最大匹配唯一。称两种删边方案不同，当且仅当存在某条边，他在两种方案中一个被保留，一个被删除。答案对 998244353 取模
优化⼀下状态设计，记分别表⽰以 为⼦树的答案且 是孤⽴点/与某个⼉⼦匹配/与⽗亲匹配的⽅案数。分别求出转移(转移详见代码)，最后答案就是froot,0+froot,1。
std：
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod=998244353;
int n,nxt[600005],head[300005],go[600005],k,f[300005][3];
void add(int u,int v)
{
nxt[++k]=head[u];
head[u]=k;
go[k]=v;
}
int qpow(int a,int b)
{
if(b==0) return 1;
int g=qpow(a,b/2);
g=g*g%mod;
if(b&1) g=g*a%mod;
return g;
}
int inv(int x)
{
return qpow(x,mod-2);
}
void dfs(int x,int fa)
{
f[x][0]=f[x][2]=1;
for(int i=head[x];i;i=nxt[i])
{
int g=go[i];
if(g==fa) continue ;
dfs(g,x);
f[x][0]*=f[g][0]+f[g][1];
f[x][1]+=f[g][2]*inv(f[g][0]+2*f[g][1]);
f[x][2]*=f[g][0]+2*f[g][1];
f[x][0]%=mod;
f[x][1]%=mod;
f[x][2]%=mod;
}
f[x][1]*=f[x][2];
f[x][1]%=mod;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n;
for(int i=1;i<n;i++)
{
int u,v;
cin>>u>>v;
add(u,v);
add(v,u);
}
dfs(1,0);
cout<<(f[1][0]+f[1][1])%mod;
}
T3质数
给你一个正整数 n，你需要找出一个区间 [l, r]，满足 [l, r] 内所有质数的和等于 n，
若无解，请输出 NIE。
本题采用了 Special Judge，你的答案正确当且仅当：
• 若输入无解，你的程序只输出了 NIE。
• 若输入有解，你的程序输出了一个区间 [l, r]，且区间内所有质数的和等于 n。
考试的时候用了20分钟左右打了个暴力拿了30分，正解是先考虑筛法求出L以内的质数，但当L过大时，筛法到这⾥已经⾛到死路了，过⼤的 不⽀持我们这样⼲。观察到⼀个性质，假如我们筛法的上限是 ，那么如果在 以内没有找到⼀个合法的⽅案的话，最终答案的右端点⼀定⼤于 。继续推⼀下你可以发现，如果答案右端点⼤于 ，那么答案中质数的数量最多只有个！我们之前在算法⼀中的优化就可以上场了， 先枚举答案中的质数个数 ，在 附近暴⼒双指针。由于 以内的质数个数是级别的，于是我们粗略估计我们暴⼒的范围⼤约在t ln n左右,当然你也不需要真的⼀个⼀个判素数，利⽤我们提前筛好的⼩质数，去把每次暴⼒的区间内的质数筛出来，这样可以有更快的效率
(这道题没调出来，也没有别人的代码)
标签：std,哈娜,int,质数,ui,2023,集训,6.28,mod From： https://www.cnblogs.com/determination/p/17521378.html