Quiz
https://atcoder.jp/contests/ddcc2019-qual/tasks/ddcc2018_qual_c
AC code
https://atcoder.jp/contests/ddcc2019-qual/submissions/13110019
考察
- O(N)で解ければいい
- N=10とする
- P側は1~2で構成するとすると、Q側は1~5まで使える
- P側は1~3で構成するとすると、Q側は1~3まで使える
- そうやって足していけばいいように思えるが、上記2行には重複がある
- P側=1,1,1,1,1,1,1,1,1,1 Q側=1,1,1,1,1,1,1,1,1,1 など
- 重複なく数える必要がある
- P側で1~3で構成するとして、310で考えると、3が含まれない数列も含まれる
- 1~3で構成して、3が1つは含まれる数列はいくつだろう
- 310 - 210 である
- そのようにP側を分離すると、Q側が取れる場合の数も決まり、求まる
- コードを書く前にN=3で答えが一致することを確認した (サンプル3)
code抜粋
// a^b mod p ll mod_pow(ll a, ll b){ if(b==0) return 1; // 肩が奇数 if(b%2==1){ return a * mod_pow(a, b-1) % mod; } else{ return mod_pow(a*a % mod, b/2) % mod; } } int main(){ cin.tie(0); ios::sync_with_stdio(false); // input ll N; cin>>N; mint sum = 0; FOR(i, 1, N+1){ // P側の個数 ll a = mod_pow(i, 10) - mod_pow(i-1, 10); if(a<0) a+=mod; // Q側の最大値 ll b = N/i; ll c = mod_pow(b, 10); sum += a*c; } p(sum.x); return 0; }