大一寒假集训最终考试（1月15日上午）（未完待续）

nefu 1665 四糸乃买花

#include <bits/stdc++.h>
using namespace std;
int n,w,t,cnt,ans,a[30];
int main()
{
    cin>>n;
    for(int i=0;i<n;i++)//i必须要从0开始，不能从1开始
        cin>>a[i];
    cin>>w;
    for(int i=1;i<(1<<n)-1;i++)//i=0代表一个都不选，i=2^n-1代表所有都选，除去这两个即可
    {
        t=w;cnt=0;//t为剩余的钱
        for(int j=0;j<n;j++)
        {
            if(i&(1<<j))
            {t=t-a[j];cnt++;}
        }
        if(t>=0&&cnt%4==0&&t%4==0)ans++;//注意t>0
    }
    printf("%d\n",ans);
    return 0;
}

nefu 1666 库特的数学题
当n>=3时，a[n]=18*3^(n-2)，用快速幂求解即可

#include <bits/stdc++.h>
using namespace std;
const long long mod=1e9+7;
long long f(long long a,long long b)
{
    long long s=18;
    while(b)
    {
        if(b%2==1){b--;s=s*a%mod;}
        a=a*a%mod;
        b=b/2;
    }
    return s;
}
int main()
{
    ios::sync_with_stdio(false);
    long long n;
    cin>>n;
    if(n==1)printf("6\n");
    else if(n==2) printf("18\n");
    else printf("%lld\n",f(3,n-2));
    return 0;
}