whuProblem 1613 - Count in Sama’s triangle

リンク:http://acm.whu.edu.cn/land/problem/detail?problem_id=1613
題意:f[i][0]=a,f[i][i]=b,f[i][j]=f[i-1][j-1]+f[i-1][j]の30行30列のクラス楊輝三角行列を構築し、すべての数対が(a,b)のうちどれだけの位置の値がmに等しいかを計算する.
解析:我々の構造方法は同じであるため,変動するのはaとbであり,各位置f[i][j]のaの係数Aとbの係数Bは前処理可能であり,各位置に対してA*a+B*bがあり,不定方程式A*x+B*y=mの正整数の解の個数を拡張ユークリッドで計算すればよい.
コード:

#include<map>
#include<set>
#include<cmath>
#include<queue>
#include<bitset>
#include<math.h>
#include<cstdio>
#include<vector>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
#pragma comment(linker, "/STACK:102400000,102400000")
using namespace std;
const int N=100010;
const int MAX=1000000100;
const int mod=100000000;
const int MOD1=1000000007;
const int MOD2=1000000009;
const double EPS=0.00000001;
typedef long long ll;
const ll MOD=998244353;
const int INF=1000000010;
typedef double db;
typedef unsigned long long ull;
int a[35][35],b[35][35];
void deal() {
    int i,j;
    for (i=0;i<=30;i++) a[i][0]=b[i][i]=1;
    for (i=2;i<=30;i++)
        for (j=1;j<i;j++) {
            a[i][j]=a[i-1][j-1]+a[i-1][j];
            b[i][j]=b[i-1][j-1]+b[i-1][j];
        }
}
int gcd(int a,int b) {
    return b ? gcd(b,a%b):a;
}
void ex_gcd(int a,int b,int &x,int &y) {
    if (!b) { x=1;y=0; }
    else { ex_gcd(b,a%b,y,x);y-=x*(a/b); }
}
int get(int a,int b,int m) {
    int g=gcd(a,b),x,y;
    if (m%g!=0) return 0;
    a/=g;b/=g;m/=g;
    ex_gcd(a,b,x,y);
    x*=m;y*=m;
    if (x<=0) { g=(1-x/b);x+=b*g;y-=a*g; }
    if (x>b) { g=(x-1)/b;x-=b*g;y+=a*g; }
    if (y>0) return (y+a-1)/a;
    return 0;
}
int main()
{
    int i,j,t,m;
    ll ans;
    deal();
    scanf("%d", &t);
    while (t--) {
        scanf("%d", &m);
        ans=0;
        for (i=2;i<=30;i++)
            for (j=1;j<i;j++)
            ans+=(ll)get(a[i][j],b[i][j],m);
        printf("%lld
", ans);
    }
    return 0;
}