T1
第一眼看上去好像矩阵快速幂..然而矩阵快速幂根本无法处理二维问题。
于是打了个暴力，骗了60...
正解是\(f_{n,m}=\sum_{i,j}f_{i,j}*C_{n+m-i|j-1}^{i-1|j-1}*a^{m-j}*b^{n-i}\)
Code
#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>
namespace EMT{
#define pf printf
#define F(i,a,b) for(register int i=a;i<=b;i++)
#define D(i,a,b) for(register int i=a;i>=b;i--)
typedef long long ll;
inline ll read(){ll x=0,f=1;char ch=getchar();while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}while(ch>=‘0‘&&ch<=‘9‘)x=x*10+ch-‘0‘,ch=getchar();return x*f;}
inline int min(int a,int b){return a<b?a:b;}inline int max(int a,int b){return a>b?a:b;}
inline void pi(ll x){pf("%lld ",x);}inline void pn(){pf("\n");}
inline void file(){freopen("in.in","r",stdin);freopen("my.out","w",stdout);}
const int N=6e5+100,p=998244353;
ll n,m,jca[N],jcb[N],invn[N],inv[N],ans,jc[N],a,b;
inline ll C(int n,int m){return ((jc[n]*inv[m])%p*inv[n-m])%p;}
inline short main(){
// file();
n=read();m=read();a=read()%p;b=read()%p;
jca[0]=jcb[0]=inv[1]=jc[0]=inv[0]=1;
F(i,1,N-10)jc [i]=jc [i-1]*i%p;
F(i,1,N-10)jca[i]=jca[i-1]*a%p;
F(i,1,N-10)jcb[i]=jcb[i-1]*b%p;
F(i,2,N-10)inv[i]=(p-p/i)*inv[p%i]%p;
F(i,1,N-10)inv[i]= inv[i-1]*inv[i]%p;
F(i,1,n){ll x=read()%p;(ans+=x*jcb[n-i]%p*jca[m]%p*C(n+m-i-1,m-1)%p)%=p;}
F(i,1,m){ll x=read()%p;(ans+=x*jcb[n]%p*jca[m-i]%p*C(n+m-i-1,n-1)%p)%=p;}
pi(ans);
return 0;
}
}
signed main(){return EMT::main();}
T2
dfs骗60是我没想到的...
考虑把左边的点看成边，吧右边的点看成点，断开一条边成为树形dp，
从两边都点亮中挑一个最小值即可
Code
#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>
namespace EMT{
#define pf printf
#define F(i,a,b) for(register int i=a;i<=b;i++)
#define D(i,a,b) for(register int i=a;i>=b;i--)
typedef long long ll;
inline int read(){int x=0,f=1;char ch=getchar();while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}while(ch>=‘0‘&&ch<=‘9‘)x=x*10+ch-‘0‘,ch=getchar();return x*f;}
inline int min(int a,int b){return a<b?a:b;}inline int max(int a,int b){return a>b?a:b;}
inline void pi(int x){pf("%d ",x);}inline void pn(){pf("\n");}
inline void file(){freopen("in.in","r",stdin);freopen("my.out","w",stdout);}
const int N=1e6+100,maxn=0x3f3f3f3f;int a,b,dp[N][2],val[N],n,head[N],co,huan[3],ans,v[N];
struct node{int next,to;}e[N<<1];inline void add(int next,int to){e[++co].next=head[next],e[co].to=to,head[next]=co;}
inline void dfs1(int k,int fa){
for(register int i=head[k],j;i;i=e[i].next){
j=e[i].to;if(j==fa)continue;
if(v[j]){huan[1]=j;huan[2]=k;return;}
v[j]=1;dfs1(j,k);
}
}
inline void clean(){F(i,1,n)dp[i][0]=0,dp[i][1]=val[i];}
inline void dfs(int k,int fa){
for(register int i=head[k],j;i;i=e[i].next){
j=e[i].to;if(j==fa)continue;
dfs(j,k);
dp[k][0]+=dp[j][1];
dp[k][1]+=min(dp[j][0],dp[j][1]);
}
}
inline short main(){
//file();
n=read();a=read();b=read();
F(i,1,n){int x=read(),y=read();val[x]+=a;val[y]+=b;add(x,y);add(y,x);}
v[1]=1;dfs1(1,0);
if(e[head[huan[1]]].to==huan[2])head[huan[1]]=e[head[huan[1]]].next;
else
for(register int i=head[huan[1]];i;i=e[i].next){
if(e[e[i].next].to==huan[2]){
e[i].next=e[e[i].next].next;
break;
}
}
if(e[head[huan[2]]].to==huan[1])head[huan[2]]=e[head[huan[2]]].next;
else
for(register int i=head[huan[2]];i;i=e[i].next){
if(e[e[i].next].to==huan[1]){
e[i].next=e[e[i].next].next;
break;
}
}
clean();
dfs(huan[1],0);
ans=dp[huan[1]][1];
clean();
dfs(huan[2],0);
ans=min(ans,dp[huan[2]][1]);
pi(ans);
return 0;
}
}
signed main(){return EMT::main();}
T3
算完全平方数....
把数拆成\(p*q\)，q为全部完全平方数的乘积，
则m内有贡献的有\(sqrt(m/p)\)个，判断奇偶性即可。
Code
#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>
namespace EMT{
#define pf printf
#define F(i,a,b) for(register int i=a;i<=b;i++)
#define D(i,a,b) for(register int i=a;i>=b;i--)
typedef long long ll;
inline int read(){int x=0,f=1;char ch=getchar();while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}while(ch>=‘0‘&&ch<=‘9‘)x=x*10+ch-‘0‘,ch=getchar();return x*f;}
inline int min(int a,int b){return a<b?a:b;}inline int max(int a,int b){return a>b?a:b;}
inline void pi(int x){pf("%d ",x);}inline void pn(){pf("\n");}
inline void file(){freopen("in.in","r",stdin);freopen("my.out","w",stdout);}
const int N=1e7+100;
int n,p[N],q[N],cnt;ll m;
inline bool f(int a,int b){return a==(a/b)*b;}
inline short main(){
n=read();scanf("%lld",&m);
for(register int i=1;i*i<=n;i++)q[++cnt]=i*i;
F(i,1,n)p[i]=i;
D(i,cnt,1)
for(register int j=1;j*q[i]<=n;j++){
int x=j*q[i];
if(f(p[x],q[i]))p[x]/=q[i];
}
int ans=0;
F(i,1,n){int x=sqrt(m/p[i]);if(x&1)--ans;else ++ans;}
pi(ans);
return 0;
}
}
signed main(){return EMT::main();}