蒟蒻的小窝

蒟蒻的小窝

题解 P3123 【[USACO15OPEN]Bessie Goes Moo S】

posted on 2020-08-21 20:48:51 | under 题解 |

它是要求能被 $7$ 整除的数量呗,但能被7整除也就意味着它 $mod7==0$ ,关键的地方来了,那我们就以判断在这道题中, $3$ 和 $10$, $7$ 和 $14$, $53$ 和 $60$ 是等价的!所以只需要在读数据的时候把这个数 $mod7$ ,(对于负数的 $mod$ 是 $(x%7+7)%7)$ 然后枚举 $7$ 个字符分别为 $0-6$ 的情况,查看套进公式后 $mod7$ 是否为 $0$,如果为 $0$,那么答案就加上每个字符当中这个数字所出现的次数的乘积,乘法法则嘛,这就ok了。温馨提示:十年OI一场空,不开 $long long$ 见祖宗。特别在连乘的时候也要强制类型转换成 $long long$。

Code:

#include<cstdio>
#define LL long long
using namespace std;
int N,x;
char ch;
LL ans,hsh[95][7];
inline int read(){
    int ret=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9'){if (ch=='-')f=-f;ch=getchar();}
    while (ch>='0'&&ch<='9') ret=ret*10+ch-'0',ch=getchar();
    return ret*f;
}
int main(){
    N=read();
    for (int i=0;i<N;i++){
        ch=getchar(),x=read();
        hsh[ch][(x%7+7)%7]++;
    }
    for(int B=0;B<7;B++)
    for(int E=0;E<7;E++)
    for(int S=0;S<7;S++)
    for(int I=0;I<7;I++)
    for(int G=0;G<7;G++)
    for(int O=0;O<7;O++)
    for(int M=0;M<7;M++) 
      if (((B+E+S+S+I+E)*(G+O+E+S)*(M+O+O))%7==0) ans+=hsh['B'][B]*hsh['E'][E]*hsh['S'][S]*hsh['I'][I]*hsh['G'][G]*hsh['O'][O]*hsh['M'][M];
    printf("%lld\n",ans);
    return 0;
}