2024牛客寒假算法基础集训营3题解（M题）

M.智乃的36倍数(normal version)

题意

���单来说就是问一个数组a中有多少种组合可以使得这个组合拼接而成的数是36的倍数

思路

36分解成4和9，能整除9代表各个位数之和是9的倍数，能整除4代表最后两位能整除4（因为100是4的倍数），由于样例过多，直接暴力是会超时的，所以想办法优化了一下：开了三个动态数组，分别为：除9的余数为i的下标，能除4的数且除9余数为i的下标，小于10且除9余数为i的下标。

那么接下来我只计算用除9余数之和能够整除9的且拼接在后面的个数（这个一定是满足整除36的条件的，主要要考虑会不会是自身拼接，可能要减去一种情况），再去特殊考虑能够满足除9余数之和能够整除9但是不一定能整除4的情况，也就是之前拼接在后面的不足10，我不能直接判断能不能整除4的情况，此时要统计向前者借一位判断能整除4的数量。最后得到的就是答案了。

代码

#include using namespace std;#define ll long longconst ll N=1e5+5;const ll mod=1e9+7;#define inf 0x7f7f7f7f7f7fll a[N];ll b[N];vectorp[10];//除9的余数为ivectorpp[10];//能除4的数且除9余数为ivectorppp[10];//小于10且除9余数为ill c[N];int main(){ios::sync_with_stdio(false);    //快读 cin.tie(0);cout.tie(0);ll n;    cin>>n;    ll ans=0;    for(ll i=0;i>a[i];        ll x=a[i];        ll y=0;        while(x)        {            y+=x%10;            x/=10;        }        b[i]=y;        p[y%9].push_back(i);        ll k=a[i]%4;        if((a[i]>=10&&k%4==0)) pp[y%9].push_back(i);        else if(a[i]