游戏
可以发现，如果有数字可以填，那么最后一个填的一定获胜。然后特判一下不能填的情况。
#include <bits/stdc++.h>
using namespace std;
#define up(i,j,n) for(int i=j;i<=n;i++)
#define down(i,j,n) for(int i=j;i>=n;i--)
const int MAXN=1e5+5;
char s[30];
int a[MAXN],top=0,num[MAXN],cnt=0;
namespace BIT{
int c[MAXN];
int lowbit(int i){return i&(-i);}
int calc(int x){
int res=0;
for(int i=x;i<=cnt;i+=lowbit(i))res+=c[i];
return res;
}
void upd(int x){
for(int i=x;i>=1;i-=lowbit(i))c[i]++;
}
}using namespace BIT;
int main(){
// freopen("input.in","r",stdin);
int N;
scanf("%d",&N);
int ans=0;
up(o,1,N){
scanf("%s",s);
if(s[0]=='X')ans++;
else{
int len=strlen(s),x=0,f=1;
if(s[0]=='-')f=-1;
up(i,0,len-1)if(s[i]!='-')
x=x*10+s[i]-'0';
a[++top]=x*f;
num[++cnt]=a[top];
}
}
if(N==1&&ans==1){
puts("L");
return 0;
}
if(ans==0){
sort(num+1,num+cnt+1);
cnt=unique(num+1,num+cnt+1)-(num+1);
up(i,1,top)a[i]=lower_bound(num+1,num+cnt+1,a[i])-num;
up(i,1,top){
ans+=calc(a[i]);
upd(a[i]);
}
}
puts(ans%2?"W":"L");
return 0;
}
多项式
根据广义欧拉定理，对于任意的$n\geq \phi(k)$有$x^n\equiv x^{n\ mod\ \phi(k) + \phi(k) }\pmod k$。
所以我们构造$n=2\phi(k)+1$，则多项式为$x^n+(k-1)x^{n-\phi(k)}$。
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define up(i,j,n) for(int i=j;i<=n;i++)
#define down(i,j,n) for(int i=j;i>=n;i--)
#define cmax(a,b) a=max(a,b)
#define cmin(a,b) a=min(a,b)
const int MAXN=3e4+5;
const int oo=0x3f3f3f3f;
int k,phi=1;
namespace solution{
void Solve(){
scanf("%d",&k);
if(k==1){
puts("-1");
return;
}
int num=k;
for(int i=2;i*i<=k;i++)if(num%i==0){
int tmp=1;
while(num%i==0){
num/=i;
tmp*=i;
}
phi*=(tmp-tmp/i);
}
if(num>1)phi*=(num-1);
int n=2*phi+1;
printf("%d\n",n);
up(i,0,n){
if(i==n-phi)printf("%d ",k-1);
else if(i==n)printf("1 ");
else printf("0 ");
}
puts("");
}
}
int main(){
// freopen("input.in","r",stdin);
using namespace solution;
Solve();
return 0;
}
子集
把数字按奇偶分成$S,T$，然后连边，求最大独立集即可。
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define up(i,j,n) for(int i=j;i<=n;i++)
#define down(i,j,n) for(int i=j;i>=n;i--)
#define cmax(a,b) a=max(a,b)
#define cmin(a,b) a=min(a,b)
#define SZ(x) (int)x.size()
const int MAXN=505;
const int oo=0x3f3f3f3f;
ll gcd(ll a,ll b){return !b?a:gcd(b,a%b);}
ll N,a[MAXN],ans=0,nxt[MAXN];
vector<int>G[MAXN];
bool vis[MAXN];
bool DFS(ll node){
up(i,0,SZ(G[node])-1)if(!vis[G[node][i]]){
vis[G[node][i]]=1;
if(!nxt[G[node][i]]||DFS(nxt[G[node][i]])){
nxt[G[node][i]]=node;
return 1;
}
}
return 0;
}
int main(){
// freopen("input.in","r",stdin);
scanf("%lld",&N);
up(i,1,N)scanf("%lld",&a[i]);
up(i,1,N)if((a[i]&1)==0)
up(j,1,N)if((a[j]&1)==1){
if(gcd(a[i],a[j])!=1||gcd(a[i]+1,a[j]+1)!=1)continue;
G[i].push_back(j);
}
up(i,1,N)if((a[i]&1)==0){
memset(vis,0,sizeof(vis));
ans+=DFS(i);
}
printf("%d\n",N-ans);
return 0;
}