方程

Description
给定正整数a,b,c,你需要求出有多少个系数为非负整数的多项式 f 满足 f(a)=b,f(b)=c 并给出一组解。有多组数据。

Input
第一行一个正整数 t 表示数据组数。
接下来 t 行每行三个正整数

a,b,c。
Output
对于每组数据， 第一行输出满足条件的多项式的个数对998244353取模的结果。若满足条件的多项式有无穷多个，输出-1。若个数>0且取模结果为 0，则输出 998244353。
若第一行输出的结果不为 0 或-1，那么另起一行，输出所有满足条件的多项式中次数最高的那个多项式，如果有多个多项式次数最高，那么输出将系数从高到低排列成数列后，字典序最大的那个。
输出多项式时，第一个数为一个非负整数 n ，表示该多项式的次数，接下来 n+1 个非负整数，为该多项式各个次数前的系数，按次数从高到低排列。

Sample Input

2
2 2 2
2 3 3

Sample Output

2
1 1 0
1
0 3

HINT
\(1\leq{t}\leq100,1\leq{a,b,c}\leq10^{18}\).

Solution

100分

如果 \(b=1\) , 如果 \(a=b=c=1\) , 有无穷解 ; 如果 \(b=c=1,a>1\) , 只有 \(f(x)=1\) 是满足条件的 ; 除此之外,无解.

\(b>1\) 时, 设常数项为 \(d'\) ,发现 \(bk+d'=c\) , 所以设 \(d\equiv{c}(mod\;b)\) .

若 \(d>0\) , 则常数项为\(d\) ; 否则,常数项为 \(0\) 或 \(b\) .

如果为 \(b\) 的话 , 则 \(f(a)\geq{b}\) 了 , \(f\) 是唯一确定的 .

确定常数项后 , 递归\(\frac{b-d}{a}\)和\(\frac{c-d}{b}\)即可 .

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define N 70
using namespace std;
typedef long long ll;
int t,mx,tot;
ll f[N],a,b,c;
inline int read(){
    int ret=0;char c=getchar();
    while(!isdigit(c))
        c=getchar();
    while(isdigit(c)){
        ret=(ret<<1)+(ret<<3)+c-'0';
        c=getchar();
    }
    return ret;
}
inline void func(ll x,ll y){
    if(!x||!y){
        if(!x&&!y) ++tot;
        return;
    }
    if(y%b){
        if(!((x-y%b)%a)){
            f[++mx]=y%b;
            func((x-y%b)/a,y/b);
        }
    }
    else{
        int p=mx;
        if(!(x%a)){
            f[++mx]=0;
            func(x/a,y/b);
        }
        if(x==y) 
            if((++tot)==1){
                mx=p;f[++mx]=x;
            }
    } 
}
inline void Aireen(){
    scanf("%d",&t);
    while(t--){
        scanf("%lld%lld%lld",&a,&b,&c);
        if(b==1)
            if(c==1)
                if(a==1) puts("-1");
                else printf("1\n0 1\n");
            else puts("0");
        else{
            tot=0;mx=-1;
            func(b,c);
            printf("%d\n",tot);
            if(tot){
                printf("%d",mx); 
                for(int i=mx;i>=0;--i)
                    printf(" %lld",f[i]);
                printf("\n");
            } 
        }
    }
}
int main(){
    freopen("equation.in","r",stdin);
    freopen("equation.out","w",stdout);
    Aireen();
    fclose(stdin);
    fclose(stdout);
    return 0;
}

取石子

Description
给定一棵大小为 n 的树，第 i 个结点上有 \(a_i\) 个石子。
方方方首先在一个结点上放上一个旗子，然后方方方和蛤布斯依次操作，每次从旗子所在结点上移除 1 至 k 个石子，然后将旗子移到一个相邻的结点上。
如果旗子所在结点没有石子，则当前操作的人输。
你需要求出方方方在哪些结点上放旗子可以获胜。
Input
第一行两个正整数 n,k。
第二行 n 个正整数 \(a_i\)。
接下来 n-1 行每行两个整数 u,v 表示一条边。
Output
第一行一个整数 m 表示可以获胜的结点数量。
第二行 m 个整数表示结点，从小到大排序后输出。
Sample Input

2 233
1 2
1 2

Sample Output

1
2

HINT
Solution

100分

显然,把石子移到石子数\(\geq\)当前结点的点上是没有用的,因为对方还可以将旗子移回来.
将所有点按石子数排序后,DP胜负态即可.

#include
#include
#include
#include
#include
#include
#include
#include
#define N 100005
#define min(a,b) (ab?a:b)
using namespace std;
typedef long long ll;
struct graph{
    int nxt,to;
}e[N<<1];
int a[N],g[N],f[N],p[N],ans[N],n,k,cnt,tot;
inline void addedge(int x,int y){
    e[++cnt].nxt=g[x];g[x]=cnt;e[cnt].to=y;
}
inline bool cmp(int x,int y){
    return a[x]