T1
很顯然就是欽定一些質數的出現次數在一個範圍之間的所有情況
就是枚舉幾個不滿足上下界的條件
就得到每個質因子可以選擇的範圍
就可以随便算方案數了
實際上上下界不滿足都隻會讓系數 − 1 -1 −1
把上下界一個不滿足的情況分開讨論就可以做到 O ( 3 p n u m ) O(3^{p_{num}}) O(3pnum)次方了
#include<bits/stdc++.h>
using namespace std;
#define gc getchar
inline int read(){
char ch=gc();
int res=0,f=1;
while(!isdigit(ch))f^=ch=='-',ch=gc();
while(isdigit(ch))res=(res+(res<<2)<<1)+(ch^48),ch=gc();
return f?res:-res;
}
#define re register
#define pb push_back
#define cs const
#define pii pair<int,int>
#define fi first
#define se second
#define ll long long
#define poly vector<int>
#define bg begin
cs int mod=998244353;
inline int add(int a,int b){return (a+=b)>=mod?a-mod:a;}
inline void Add(int &a,int b){(a+=b)>=mod?(a-=mod):0;}
inline int dec(int a,int b){return (a-=b)<0?a+mod:a;}
inline void Dec(int &a,int b){(a-=b)<0?(a+=mod):0;}
inline int mul(int a,int b){return 1ll*a*b>=mod?1ll*a*b%mod:a*b;}
inline int mul(int a,int b,int Mod){return 1ll*a*b>=Mod?1ll*a*b%Mod:a*b;}
inline void Mul(int &a,int b){a=mul(a,b);}
inline int ksm(int a,int b){
int res=1;
for(;b;b>>=1,a=mul(a,a))(b&1)&&(res=mul(res,a));return res;
}
inline void chemx(ll &a,ll b){a<b?a=b:0;}
inline void chemn(ll &a,ll b){a>b?a=b:0;}
inline ll ksm(ll a,ll b,cs ll &mod){
ll res=1;
for(;b;b>>=1,a=mul(a,a,mod))if(b&1)res=mul(res,a,mod);
return res;
}
cs int N=1000005,M=N-5;
bool isp[N];
int pr[N],tot;
inline void init(){
for(int i=2;i<=M;i++){
if(!isp[i])pr[++tot]=i;
for(int j=1;j<=tot&&i*pr[j]<=M;j++){
isp[i*pr[j]]=1;
if(i%pr[j]==0)break;
}
}
}
inline bool Miller_Rabin(ll x){
ll mod=x;
if(x<=M)return !isp[x];
if(!(x&1))return false;
if((x%3==0)||(x%5==0)||(x%7==0))return false;
ll t=x-1,s=0;
while(!(t&1))t>>=1,s++;
for(int i=1;i<=20&&pr[i]<x;i++){
ll k=ksm(pr[i],t,mod),pre=k;
if(x%pr[i]==0)return false;
for(int j=0;j<s;j++){
k=mul(k,k,mod);
if(k==1&&pre!=1&&pre!=x-1)return false;
pre=k;
}
if(k!=1)return false;
}
return true;
}
int c[N],ans,cnt;
inline void calc(int coef,int coef2,int siz){
if(siz&1)Add(ans,mul(coef2,ksm(2,coef)-1));
else Dec(ans,mul(coef2,ksm(2,coef)-1));
}
void dfs(int pos,int coef,int coef2,int siz){
if(pos==cnt+1)return calc(coef,coef2,siz);
dfs(pos+1,mul(coef,c[pos]+1,mod-1),coef2,siz);
dfs(pos+1,mul(coef,c[pos],mod-1),mul(coef2,2),siz+1);
if(c[pos]>1)dfs(pos+1,mul(coef,c[pos]-1,mod-1),coef2,siz+2);
}
int main(){
init();
ll m;
scanf("%lld",&m);
for(int i=1;i<=tot;i++){
if(m%pr[i]==0){
int tt=0;
while(m%pr[i]==0)tt++,m/=pr[i];
c[++cnt]=tt;
}
}
if(m>1){
if(Miller_Rabin(m))c[++cnt]=1;
else{
int x=sqrt(m);
if(1ll*x*x==m){
c[++cnt]=2;
}
else{
c[++cnt]=1,c[++cnt]=1;
}
}
}
dfs(1,1,1,1);
cout<<ans;
}
T2
設 k i k_i ki第 i i i個選的個數， f [ i ] [ j ] [ k ] f[i][j][k] f[i][j][k]表示前 i i i個，填了 j j j個， ∑ a m a x ( 0 , c a − k a ) − m a x ( 0 , k a − c a ) / 4 = k \sum_amax(0,c_a-k_a)-max(0,k_a-c_a)/4=k ∑amax(0,ca−ka)−max(0,ka−ca)/4=k的方案數，步長乘方案數就是答案
最後由于去重是 ( ∑ k i ) ! ∏ k i ! \frac{(\sum k_i)!}{\prod k_i!} ∏ki!(∑ki)!
下面的系數中間邊乘維護
邊界情況有點奇怪，反正我是沒搞懂
#include<bits/stdc++.h>
using namespace std;
#define gc getchar
inline int read(){
char ch=gc();
int res=0,f=1;
while(!isdigit(ch))f^=ch=='-',ch=gc();
while(isdigit(ch))res=(res+(res<<2)<<1)+(ch^48),ch=gc();
return f?res:-res;
}
#define re register
#define pb push_back
#define cs const
#define pii pair<int,int>
#define fi first
#define se second
#define ll long long
#define poly vector<int>
#define bg begin
cs int mod=1e9+7;
inline int ksm(int a,int b,int res=1){
for(;b;b>>=1,a=1ll*a*a%mod)(b&1)&&(res=1ll*res*a%mod);return res;
}
inline void chemx(int &a,int b){a<b?a=b:0;}
inline void chemn(int &a,int b){a>b?a=b:0;}
cs int N=12,M=405,C=1605;
int f[N][M][C],q[N],c[N],p[C],fac[C],ifac[C],Q,tot,mx,n;
inline void init(){
fac[0]=ifac[0]=1;
for(int i=1;i<C;i++)fac[i]=1ll*fac[i-1]*i%mod;
ifac[C-1]=ksm(fac[C-1],mod-2);
for(int i=C-2;i;i--)ifac[i]=1ll*ifac[i+1]*(i+1)%mod;
}
int main(){
init();
n=read();
for(int i=1;i<=n;i++)q[i]=read(),Q+=q[i];
Q=ksm(Q,mod-2);
for(int i=1;i<=n;i++)q[i]=1ll*q[i]*Q%mod;
for(int i=1;i<=n;i++)c[i]=read(),tot+=c[i];
f[0][tot][0]=1,mx=tot*4;
for(int i=1;i<=n;i++){
for(int t=1,j=0;j<=mx;j++,(t=1ll*t*q[i]%mod))p[j]=1ll*ifac[j]*t%mod;
for(int j=0;j<=tot;j++)for(int k=0;k<=mx;k++)
if(f[i-1][j][k]){
int pt=f[i-1][j][k];
for(int l=0;l<=mx-k;l++){
int del=c[i];
if(l<c[i])del+=l-c[i];
else del+=(l-c[i])/4;
if(j>=del)(f[i][j-del][k+l]+=1ll*pt*p[l]%mod)%=mod;
}
}
}
int res=1;
for(int j=1;j<=mx;j++){
int now=0;
for(int i=1;i<=tot;i++)
(now+=f[n][i][j])%=mod;
(res+=1ll*fac[j]*now%mod)%=mod;
}
cout<<res;
}
T3
考場用随機化貪心騙了 45 p t s 45pts 45pts
實際上把式子拆開
可以發現我們隻需要把兩兩點比對使得點積和最大
這是一個二分圖最大權比對
結果卡了費用流做法。。。。
隻能寫 K M KM KM，還隻有非遞歸版能過
O r z Orz Orz了一波仲爺的闆子
#include<bits/stdc++.h>
using namespace std;
#define gc getchar
inline int read(){
char ch=gc();
int res=0,f=1;
while(!isdigit(ch))f^=ch=='-',ch=gc();
while(isdigit(ch))res=(res+(res<<2)<<1)+(ch^48),ch=gc();
return f?res:-res;
}
#define re register
#define pb push_back
#define cs const
#define pii pair<int,int>
#define fi first
#define se second
#define ll long long
#define poly vector<int>
#define bg begin
cs int mod=998244353;
inline int add(int a,int b){return (a+=b)>=mod?a-mod:a;}
inline void Add(int &a,int b){(a+=b)>=mod?(a-=mod):0;}
inline int dec(int a,int b){return (a-=b)<0?a+mod:a;}
inline void Dec(int &a,int b){(a-=b)<0?(a+=mod):0;}
inline int mul(int a,int b){return 1ll*a*b>=mod?1ll*a*b%mod:a*b;}
inline int mul(int a,int b,int Mod){return 1ll*a*b>=Mod?1ll*a*b%Mod:a*b;}
inline void Mul(int &a,int b){a=mul(a,b);}
inline int ksm(int a,int b,int res=1){
for(;b;b>>=1,a=mul(a,a))(b&1)&&(res=mul(res,a));return res;
}
inline void chemx(int &a,int b){a<b?a=b:0;}
inline void chemn(int &a,int b){a>b?a=b:0;}
cs int N=505;
int a[N][N],n;
namespace KM{
int wx[N],wy[N],px[N],py[N],vx[N],vy[N],path[N],id,mn[N];
#define calc(x,y) ((wx[(x)]+wy[(y)]-a[(x)][(y)]))
inline void solve(){
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)chemx(wx[i],a[i][j]);
for(int i=1;i<=n;i++){
vx[i]=++id,path[i]=0;
for(int j=1;j<=n;j++)mn[j]=i;
while(!px[i]){
int oy=0;
for(int j=1;j<=n;j++)
if(vy[j]!=id&&(!oy||(calc(mn[j],j)<calc(mn[oy],oy))))oy=j;
int ox=mn[oy],val=calc(ox,oy);
for(int j=1;j<=n;j++){
if(vx[j]==id)wx[j]-=val;
if(vy[j]==id)wy[j]+=val;
}
if(!py[oy]){
while(ox){
py[oy]=ox;
swap(oy,px[ox]);
ox=path[ox];
}
}
else{
int curx=py[oy];path[curx]=ox;
vx[curx]=vy[oy]=id;
for(int j=1;j<=n;j++)
if(vy[j]!=id&&(calc(mn[j],j))>calc(curx,j))mn[j]=curx;
}
}
}
cout<<"Yes\n";
for(int i=1;i<=n;i++)cout<<px[i]<<" ";
}
}
struct pt{
int x,y;
pt(int _x=0,int _y=0):x(_x),y(_y){}
friend inline int operator ^(cs pt &a,cs pt &b){
return a.x*b.x+a.y*b.y;
}
}p[N],v[N];
int main(){
n=read();
for(int i=1;i<=n;i++)p[i].x=read(),p[i].y=read();
for(int i=1;i<=n;i++)v[i].x=read(),v[i].y=read();
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)a[i][j]=p[i]^v[j];
KM::solve();
}