P1450 [HAOI2008]硬币购物
多组问询。每次 (c_i) 相同，给定 (d_i,s)，求满足 (0le x_ile d_i) 且 (sum_{i=1}^{4} x_ic_i=S) 的 (x) 的方案数。
考虑容斥。我们假设 (f_i) 表示不受限制时，和为 (i) 的方案数。那么我们容斥哪些物品一定超额使用。
#include<bits/stdc++.h>
#define int long long
#define rep(i,a,b) for(register int i=(a);i<=(b);i++)
#define per(i,a,b) for(register int i=(a);i>=(b);i--)
using namespace std;
const int N=1e5+9;
inline int read() {
register int x=0, f=1; register char c=getchar();
while(c<'0'||c>'9') {if(c=='-') f=-1; c=getchar();}
while(c>='0'&&c<='9') {x=(x<<3)+(x<<1)+c-48,c=getchar();}
return x*f;
}
int Q,n=4,ss=15,c[5],d[5],S,f[N];
bool get(int s,int i) {return s&(1<<i-1);}
signed main() {
rep(i,1,n) c[i]=read();
Q=read();
f[0]=1;
rep(i,1,n) rep(j,c[i],100000) f[j]+=f[j-c[i]];
while(Q--) {
rep(i,1,n) d[i]=read();
S=read();
int ans=0;
rep(s,0,ss) {
int popc=0,w=0,res=0,tS=S;
rep(i,1,n) if(get(s,i)) {
popc++;
tS-=c[i]*(d[i]+1);
}
res=(tS<0?0:f[tS]), w=(popc%2?-1:1);
ans+=res*w;
}
printf("%lld
",ans);
}
return 0;
}
P3158 [CQOI2011]放棋子
(n imes m) 的棋盘，有 (c) 种不同颜色的棋子，每种颜色的棋子有 (a_i) 个。棋子不能叠放，且每行每列的所有棋子颜色必须相同。问方案数。
考虑 DP。(f(i,j,k)) 表示对于前 (i) 种颜色的棋子，放了 (j imes k) 大小的的棋盘格。转移觉得要枚举第 (i) 类棋子占了多少格子，设其占了 (x) 行 (y) 列。贡献很难算。所以我们要求 (g(i,j,k)) 表示 (i) 枚同色棋子占了 (j) 行 (k) 列（也可以理解成 (j imes k) 的棋盘格）。我们按行考虑。我们转移时枚举第 (j+1) 行放置了多少枚棋子，且有多少枚棋子原本就在 (j imes k) 的格子中。我们设前者为 (x)，后者为 (y)，则有
于是我们 (f) 就有转移
最后我们就可以计算答案
#include<bits/stdc++.h>
#define int long long
#define rep(i,a,b) for(register int i=(a);i<=(b);i++)
#define per(i,a,b) for(register int i=(a);i>=(b);i--)
using namespace std;
const int N=69,mod=1e9+9;
inline int read() {
register int x=0, f=1; register char c=getchar();
while(c<'0'||c>'9') {if(c=='-') f=-1; c=getchar();}
while(c>='0'&&c<='9') {x=(x<<3)+(x<<1)+c-48,c=getchar();}
return x*f;
}
int fac[N], inv[N], ifac[N];
void pre(int mn=30) {
inv[0]=inv[1]=fac[0]=ifac[0]=1;
for(int i=1;i<=mn;i++) fac[i]=fac[i-1]*i%mod;
for(int i=2;i<=mn;i++) inv[i]=inv[mod%i]*(mod-mod/i)%mod;
for(int i=1;i<=mn;i++) ifac[i]=ifac[i-1]*inv[i]%mod;
}
int C(int x,int y) {
if(x<0||y<0||x<y) return 0;
else return fac[x]*ifac[y]%mod*ifac[x-y]%mod;
}
void add(int &x,int y) {(x+=y)%=mod;}
int n,m,c,a[N],g[909][N][N],f[N][N][N];
signed main() {
n=read(), m=read(), c=read();
int mx=0;
rep(i,1,c) a[i]=read(), mx=max(mx,a[i]);
pre();
g[0][0][0]=1;
rep(i,0,mx) rep(j,0,n-1) rep(k,0,m) if(g[i][j][k]) {
rep(x,1,m) rep(y,0,min(x,k)) {
if(k+x-y>m) continue;
add(g[i+x][j+1][k+x-y],C(k,y)*C(k+x-y,k)%mod*g[i][j][k]%mod);
}
}
f[0][0][0]=1;
rep(i,0,c-1) rep(j,0,n) rep(k,0,m) if(f[i][j][k]) {
rep(x,1,n-j) rep(y,1,m-k) {
add(f[i+1][j+x][k+y],C(j+x,x)*C(k+y,y)%mod*f[i][j][k]%mod*g[a[i+1]][x][y]%mod);
}
}
int ans=0;
rep(j,1,n) rep(k,1,m) add(ans,C(n,j)*C(m,k)%mod*f[c][j][k]%mod);
printf("%lld
",ans);
return 0;
}
后记：你不要写错模数啊喂！你不要写错模数啊喂！你不要写错模数啊喂！你不要写错模数啊喂！你不要写错模数啊喂！你不要写错模数啊喂！你不要写错模数啊喂！你不要写错模数啊喂！你不要写错模数啊喂！你不要写错模数啊喂！你不要写错模数啊喂！你不要写错模数啊喂！你不要写错模数啊喂！你不要写错模数啊喂！你不要写错模数啊喂！
P3349 [ZJOI2016]小星星
暴力状压的话由于枚举子集所以 (O(3^nn^3))。DP 为 (f(u,i,S)) 表示 (u) 子树内，树点 (u) 对应图点 (i)，图点使用状态为 (S)。
考虑容斥。我们要求做到树点和图点一一对应，即最终所有的图点都被使用了。我们用容斥优化的时候考虑丢掉状压的 (S) 维度，容斥哪些点一定不使用，设其状态为 (S)。于是我们有
复杂度 (O(2^nn^3))
#include<bits/stdc++.h>
#define int long long
#define rep(i,a,b) for(register int i=(a);i<=(b);i++)
#define per(i,a,b) for(register int i=(a);i>=(b);i--)
using namespace std;
const int N=19;
inline int read() {
register int x=0, f=1; register char c=getchar();
while(c<'0'||c>'9') {if(c=='-') f=-1; c=getchar();}
while(c>='0'&&c<='9') {x=(x<<3)+(x<<1)+c-48,c=getchar();}
return x*f;
}
int n,m,f[N][N];
vector<int>G[N],T[N];
bool get(int s,int i) {return s&(1<<i-1);}
void dfs(int u,int fa,int s) {
for(auto v:T[u]) if(v!=fa) dfs(v,u,s);
rep(i,1,n) f[u][i]=!get(s,i);
rep(i,1,n) if(!get(s,i)) {
for(auto v:T[u]) if(v!=fa) {
int res=0;
for(auto j:G[i]) if(!get(s,j)) res+=f[v][j];
f[u][i]*=res;
}
}
}
signed main() {
n=read(), m=read();
rep(i,1,m) {
int u=read(), v=read();
G[u].push_back(v), G[v].push_back(u);
}
rep(i,2,n) {
int u=read(), v=read();
T[u].push_back(v), T[v].push_back(u);
}
int S=(1<<n)-1,ans=0;
rep(s,0,S) {
int w=1,res=0;
dfs(1,0,s);
rep(i,1,n) {
if(get(s,i)) w=-w;
else res+=f[1][i];
}
ans+=w*res;
}
printf("%lld
",ans);
return 0;
}
P3214 [HNOI2011]卡农
卡农好听！！这出题人怕不是不会乐理！！
有 (n) 个不同元素，一个片段是一个包含任意多个元素的不可重非空集合。问有多少种由 (m) 片段组成的的不可重集合，使得集合中每个元素出现次数为偶数。
神仙题。
Trick1：有序集合更加方便，于是我们将无序集转化为有序集，最终除以 (m!) 就行了。
Trick2：补集转换。
同样是 DP。(f(i)) 表示 (i) 个片段组成的合法集合数。首先考虑总数。我们发现如果任意确定了 (i-1) 个不可重片段，那么第 (i) 个片段也就随之确定了。这解决了偶数的问题。所以（满足偶数条件以及前 (i-1) 不可重的条件）总数为 (A_{2^n-1}^{i-1})。
由两个可能不满足的条件，片段不同以及片段非空。考虑存在片段相同的情况，由于前 (i-1) 不可重，那么一定是第 (i) 个和之前的有重复，由于减去两个相同的片段后总数还是偶数，并且我们重复的片段有 (2^n-1-(i-2)) 种，所以这部分答案为 ((i-1)(2^n-i+1)f(i-2))；考虑片段非空的情况，由于前 (i-1) 非空，那么一定是第 (i) 个是空片段，所以这部分答案为 (f(i-1))。
#include<bits/stdc++.h>
#define int long long
#define rep(i,a,b) for(register int i=(a);i<=(b);i++)
#define per(i,a,b) for(register int i=(a);i>=(b);i--)
using namespace std;
const int N=1e6+9,mod=1e8+7;
inline int read() {
register int x=0, f=1; register char c=getchar();
while(c<'0'||c>'9') {if(c=='-') f=-1; c=getchar();}
while(c>='0'&&c<='9') {x=(x<<3)+(x<<1)+c-48,c=getchar();}
return x*f;
}
int n,m,a[N],f[N];
int ksm(int x,int y) {
if(y==0) return 1;
else return ksm(x*x%mod,y/2)*(y%2?x:1)%mod;
}
signed main() {
n=read(), m=read();
int s=ksm(2,n);
a[0]=1, f[0]=1, f[1]=0;
rep(i,1,m) a[i]=a[i-1]*(s-i)%mod;
rep(i,1,m) f[i]=(a[i-1]-f[i-1]-(i-1)*(s-i+1)%mod*f[i-2]%mod)%mod;
f[m]=(f[m]+mod)%mod;
rep(i,1,m) f[m]=f[m]*ksm(i,mod-2)%mod;
printf("%lld
",f[m]);
return 0;
}
P6672 [清华集训2016] 你的生命已如风中残烛
有 (m) 张不同的牌，其中有 (n) 张牌上有正整数 (w)（满足 (sum w=m)），另有 (m-n) 上有 0。问有多少种排列方法，使得 (forall iin[1,m] sum w_{j=1}^{i}ge i)。
神仙题。
Trick1 如果每个 (w) 都减去 (1)，那么我们只需要保证前缀和非负。这样每个 (i) 的约束限制就一样了。
然后就是 Raney 定理。参考具体数学中的处理方法。因为不能保证每次1都在前面，于是我们数列取反然后再前面加上1，此时有 (m-n+1) 个 (1)。
于是 (ans=frac{m!}{m-n+1})。
https://www.luogu.com.cn/blog/forever-captain/solution-p6672
#include<bits/stdc++.h>
#define int long long
#define rep(i,a,b) for(register int i=(a);i<=(b);i++)
#define per(i,a,b) for(register int i=(a);i>=(b);i--)
using namespace std;
const int mod=998244353;
inline int read() {
register int x=0, f=1; register char c=getchar();
while(c<'0'||c>'9') {if(c=='-') f=-1; c=getchar();}
while(c>='0'&&c<='9') {x=(x<<3)+(x<<1)+c-48,c=getchar();}
return x*f;
}
signed main() {
int n=read(),m=0,ans=1;
rep(i,1,n) m+=read();
rep(i,2,m) ans=ans*(i==m-n+1?1:i)%mod;
printf("%lld
",ans);
return 0;
}
P2606 [ZJOI2010]排列计数
很水的一道题。可以转化为一棵完全二叉树的满足小根堆性质的标号排列数量。考虑树形 DP (f(u)) 表示 (u) 子树内的答案。转移时可以首先确定 (u) 一定是最小的 (1)，然后我们把剩下的几个随便分配给左右子树，然后让左右子树来安排这些标号的排列。
#include<bits/stdc++.h>
#define int long long
#define rep(i,a,b) for(register int i=(a);i<=(b);i++)
#define per(i,a,b) for(register int i=(a);i>=(b);i--)
using namespace std;
const int N=2e6+9;
inline int read() {
register int x=0, f=1; register char c=getchar();
while(c<'0'||c>'9') {if(c=='-') f=-1; c=getchar();}
while(c>='0'&&c<='9') {x=(x<<3)+(x<<1)+c-48,c=getchar();}
return x*f;
}
int n,mod,sz[N],f[N],fac[N],inv[N],ifac[N];
void pre() {
inv[0]=inv[1]=fac[0]=ifac[0]=1;
for(int i=1;i<=n;i++) fac[i]=fac[i-1]*i%mod;
for(int i=2;i<=n;i++) inv[i]=inv[mod%i]*(mod-mod/i)%mod;
for(int i=1;i<=n;i++) ifac[i]=ifac[i-1]*inv[i]%mod;
}
int C(int x,int y) {
if(x<0||y<0||x<y) return 0;
else return fac[x]*ifac[y]%mod*ifac[x-y]%mod;
}
void dfs(int u) {
if(u>n) return f[u]=1,void();
dfs(u*2),dfs(u*2+1);
sz[u]=sz[u*2]+sz[u*2+1]+1;
f[u]=C(sz[u*2]+sz[u*2+1],sz[u*2])*f[u*2]%mod*f[u*2+1]%mod;
}
signed main() {
n=read(), mod=read();
pre();
dfs(1);
printf("%lld
",f[1]);
return 0;
}
P3244 [HNOI2015]落忆枫音
给定一个 DAG，问添加了一条单向边 ((x,y)) 后，有多少叶向生成树。
考虑不管加入的边，答案危
每个点都选择一个父亲，乘起来。
然后我们加了一条边。现在我们连成的可能形成了环。于是我们不能要这种情况。我们考虑补集转换。对于一个环 (S)，满足选择了 (S) 的方案数为 (prod u otin S deg^{in}_u)，即环上的点指定父亲为环上的点，其他点随意选择。
所以答案是
设
则有答案为 (-dp_x+prod deg(i))，初始值有 (dp_y=frac{prod deg(i)}{deg_y})
转移有
#include<bits/stdc++.h>
#define int long long
#define rep(i,a,b) for(register int i=(a);i<=(b);i++)
#define per(i,a,b) for(register int i=(a);i>=(b);i--)
using namespace std;
const int N=200009,mod=1e9+7;
inline int read() {
register int x=0, f=1; register char c=getchar();
while(c<'0'||c>'9') {if(c=='-') f=-1; c=getchar();}
while(c>='0'&&c<='9') {x=(x<<3)+(x<<1)+c-48,c=getchar();}
return x*f;
}
int ksm(int x,int y) {
if(y==0) return 1;
else return ksm(x*x%mod,y/2)*(y%2?x:1)%mod;
}
int n,m,x,y,deg[N],f[N],prod=1,ans=1;
vector<int>fr[N];
bool vst[N];
void dfs(int u) {
if(vst[u]) return; vst[u]=1;
if(u==y) {f[u]=prod*ksm(deg[u],mod-2); return;}
for(auto v:fr[u]) dfs(v);
for(auto v:fr[u]) f[u]=(f[u]+f[v])%mod;
f[u]=f[u]*ksm(deg[u],mod-2)%mod;
}
signed main() {
n=read(), m=read(), x=read(), y=read();
rep(i,1,m) {
int u=read(), v=read();
fr[v].push_back(u), deg[v]++;
}
deg[1]++;
rep(i,1,n) {
prod=(prod*deg[i])%mod,
ans=(ans*(deg[i]+(i==y)))%mod;
}
dfs(x);
printf("%lld
",(ans-f[x]+mod)%mod);
return 0;
}
P3643 [APIO2016]划艇
求有多少个数列 (c_N) ，对于每个非零位置 (c_i) 满足
- (c_i=0)
- (a_ile c_ile b_i)
- (c_i>c_{上一个非零位置})
sub1：(a_i=b_i)，直接 check 是否满足 (a_i>a_{i-1})，如果是那么1个，否则0个
sub2：(sum_{b_i-a_i}le 10^6)，考虑 DP (f(i,j)) 表示前 (i) 个数且第 (i) 个数为 (a_i+j)。用vector存DP数组。应该不简单。
现在考虑优化这个DP。可以考虑离散化。我们把所有的 ([a_i,b_i]) 区间离散化成 (O(n)) 个端点，形成 (O(n)) 个区间。(f(i,j)) 表示前 (i) 个数，第 (i) 个数非零且在第 (j) 个区间内。我们 DP 的时候枚举上一个区间，以及出现在上一个区间的最后一个数是哪个。于是我们现在要计算在第 (j) 个区间内，有 (m) 个数且第 (i) 个数不为 0 的方案数。显然我们能得到，设有 (m) 数满足条件，则其贡献为 (inom{len+m-1}{m})。
所以有 DP 方程
由于这个 (k) 和组合数没有关系，考虑把 k 的求和以到组合数后面去，然后就可以前缀和优化
组合数不能直接贺板子，很不好，还需要吸收恒等式硬搞。
#include<bits/stdc++.h>
#define int long long
#define rep(i,a,b) for(register int i=(a);i<=(b);i++)
#define per(i,a,b) for(register int i=(a);i>=(b);i--)
using namespace std;
const int N=1009,mod=1e9+7;
inline int read() {
register int x=0, f=1; register char c=getchar();
while(c<'0'||c>'9') {if(c=='-') f=-1; c=getchar();}
while(c>='0'&&c<='9') {x=(x<<3)+(x<<1)+c-48,c=getchar();}
return x*f;
}
int n,inv[N],l[N],r[N],p[N],li[N],ri[N],len[N],cnt,c[N],f[N][N],s[N];
void pre() {
inv[0]=inv[1]=1;
rep(i,2,1000) inv[i]=inv[mod%i]*(mod-mod/i)%mod;
}
struct node {int id,val,lr;} b[N];
bool cmp(const node &x,const node &y) {return x.val<y.val;}
void discrete() {
rep(i,1,n)
b[i*2-1]=(node){i,l[i],0}, b[i*2]=(node){i,r[i],1};
sort(b+1,b+2*n+1,cmp);
rep(i,1,2*n) {
if(b[i].val!=b[i-1].val) cnt++;
if(b[i].lr) ri[b[i].id]=cnt;
else li[b[i].id]=cnt;
p[cnt]=b[i].val;
}
}
signed main() {
n=read();
pre();
rep(i,1,n) l[i]=read(), r[i]=read(), r[i]++;
discrete();
rep(i,1,cnt-1) len[i]=p[i+1]-p[i];
s[0]=1;
rep(j,1,cnt-1) {
c[0]=1;
rep(i,1,n) c[i]=c[i-1]*(len[j]+i-1)%mod*inv[i]%mod;
per(i,n,1) if(li[i]<=j&&j<ri[i]) {
int m=1,cur=len[j];
per(p,i-1,0) {
f[i][j]=(f[i][j]+cur*s[p]%mod)%mod;
if(li[p]<=j&&j+1<=ri[p]) cur=c[++m];
}
s[i]=(s[i]+f[i][j])%mod;
}
}
int ans=0;
rep(i,1,n) ans=(ans+s[i])%mod;
printf("%lld
",ans);
return 0;
}
P3228 [HNOI2013]数列
对于20%数据，可以DP (f(i,j)) 表示前 (i) 天且第 (i) 天为 (j) 的方案数。卡卡常应该能过去。
正解要一个trick考虑差分序列的情况。显然知道差分序列和 (a_1) 就可以唯一确定整个序列。一共有 (m^{k-1}) 种差分序列/假如确定了差分序列 (d)，则 (a_1) 有
种可能性
于是题目中求得即
令 (c_i) 为 (i) 在所有可能的差分序列中所出现的次数，有
由于每一个数分布概率均匀，所以 (c_i) 都是相等的。所以设出现次数为 (c)，有
#include<bits/stdc++.h>
#define int long long
#define rep(i,a,b) for(register int i=(a);i<=(b);i++)
#define per(i,a,b) for(register int i=(a);i>=(b);i--)
using namespace std;
inline int read() {
register int x=0, f=1; register char c=getchar();
while(c<'0'||c>'9') {if(c=='-') f=-1; c=getchar();}
while(c>='0'&&c<='9') {x=x*10+c-48,c=getchar();}
return x*f;
}
int n,k,m,p;
int ksm(int x,int y) {
if(y==0) return 1;
else return ksm(x*x%p,y/2)*(y%2?x:1)%p;
}
signed main() {
n=read(), k=read(), m=read(), p=read();
n%=p;
int c=ksm(m,k-2)*(k-1)%p;
int ans=ksm(m,k-1)*n%p;
ans-=c*((m+1)*m/2%p)%p;
printf("%lld
",(ans+p)%p);
return 0;
}
P4071 [SDOI2016]排列计数
连我都能一眼看出答案的sb题。设错排数 (f_n)，则有
#include<bits/stdc++.h>
#define int long long
#define rep(i,a,b) for(register int i=(a);i<=(b);i++)
#define per(i,a,b) for(register int i=(a);i>=(b);i--)
using namespace std;
const int N=1e6+9,mod=1e9+7;
inline int read() {
register int x=0, f=1; register char c=getchar();
while(c<'0'||c>'9') {if(c=='-') f=-1; c=getchar();}
while(c>='0'&&c<='9') {x=(x<<3)+(x<<1)+c-48,c=getchar();}
return x*f;
}
int f[N],fac[N], inv[N], ifac[N];
void pre(int n) {
inv[0]=inv[1]=fac[0]=ifac[0]=f[0]=f[2]=1;
for(int i=1;i<=n;i++) fac[i]=fac[i-1]*i%mod;
for(int i=2;i<=n;i++) inv[i]=inv[mod%i]*(mod-mod/i)%mod;
for(int i=1;i<=n;i++) ifac[i]=ifac[i-1]*inv[i]%mod;
for(int i=3;i<=n;i++) f[i]=(i-1)*(f[i-1]+f[i-2])%mod;
}
int C(int x,int y) {
if(x<0||y<0||x<y) return 0;
else return fac[x]*ifac[y]%mod*ifac[x-y]%mod;
}
signed main() {
int T=read();
pre(1000000);
while(T--) {
int n=read(), m=read();
printf("%lld
",C(n,m)*f[n-m]%mod);
}
return 0;
}
P1350 车的放置
还是连我都能做出来的sbt。
首先考虑 ((a+c) imes d) 的长方形，易得答案
然后考虑假如这个上方的长方形，我们枚举其中有几个车，易得答案
#include<bits/stdc++.h>
#define int long long
#define rep(i,a,b) for(register int i=(a);i<=(b);i++)
#define per(i,a,b) for(register int i=(a);i>=(b);i--)
using namespace std;
const int N=2009,mod=1e5+3;
inline int read() {
register int x=0, f=1; register char c=getchar();
while(c<'0'||c>'9') {if(c=='-') f=-1; c=getchar();}
while(c>='0'&&c<='9') {x=(x<<3)+(x<<1)+c-48,c=getchar();}
return x*f;
}
int a,b,c,d,k,fac[N],inv[N],ifac[N],ans;
void pre(int n) {
inv[0]=inv[1]=fac[0]=ifac[0]=1;
rep(i,1,n) fac[i]=fac[i-1]*i%mod;
rep(i,2,n) inv[i]=inv[mod%i]*(mod-mod/i)%mod;
rep(i,1,n) ifac[i]=ifac[i-1]*inv[i]%mod;
}
int C(int x,int y) {
if(x<0||y<0||x<y) return 0;
else return fac[x]*ifac[y]%mod*ifac[x-y]%mod;
}
signed main() {
a=read(), b=read(), c=read(), d=read(), k=read();
pre(2000);
rep(i,0,k) {
int res=C(a,i)*C(b,i)%mod*C(a+c-i,k-i)%mod*C(d,k-i)%mod*fac[i]%mod*fac[k-i]%mod;
ans=(ans+res)%mod;
}
printf("%lld
",ans);
return 0;
}
P3166 [CQOI2014]数三角形
还是小清新组合数题。
我们考虑补集转换。随便选3个点-横着共线-竖着共线-斜着共线，其中斜着要枚举向量 (vec{AC}=(x,y))。
我们为了方便让 (n:=n+1, m:=m+1)，即 (n,m) 分别代表格点数
随便选3个点：(inom{nm}{3}=frac{nm(nm-1)(nm-2)}{6})
横着共线：(ninom{m}{3}=frac{nm(m-1)(m-2)}{6})
竖着共线：(minom{n}{3}=frac{mn(n-1)(n-2)}{6})
斜着共线：考虑到以整点为端点的向量 ((x,y)) 所经过整点数（不包括两端）为 (gcd (x,y)-1)，所以我们计算点 A 的取法数量和点 B 的取法数量
OEIS 上好像有 (n=1) 和 (n=2) 的。
#include<bits/stdc++.h>
#define int long long
#define rep(i,a,b) for(register int i=(a);i<=(b);i++)
#define per(i,a,b) for(register int i=(a);i>=(b);i--)
using namespace std;
inline int read() {
register int x=0, f=1; register char c=getchar();
while(c<'0'||c>'9') {if(c=='-') f=-1; c=getchar();}
while(c>='0'&&c<='9') {x=(x<<3)+(x<<1)+c-48,c=getchar();}
return x*f;
}
int gcd(int a,int b) {
if(b==0) return a;
else return gcd(b,a%b);
}
signed main() {
int n=read()+1, m=read()+1;
int a=n*m*(n*m-1)/2*(n*m-2)/3, b=n*m*(m-1)/2*(m-2)/3, c=m*n*(n-1)/2*(n-2)/3, d=0;
rep(x,1,n) rep(y,1,m) d+=2*(n-x)*(m-y)*(gcd(x,y)-1);
printf("%lld
",a-b-c-d);
return 0;
}