結果
問題 | No.2017 Mod7 Parade |
ユーザー |
|
提出日時 | 2022-07-22 22:11:26 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 68 ms / 2,000 ms |
コード長 | 1,033 bytes |
コンパイル時間 | 1,890 ms |
コンパイル使用メモリ | 195,744 KB |
最終ジャッジ日時 | 2025-01-30 12:28:25 |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 18 |
ソースコード
#include<bits/stdc++.h> using namespace std; const long long mod=1e9+7; long long mod7_10[6]={1, 3, 2, 6, 4, 5}; long long d(long long t,long long l){ return (mod7_10[l%6]-1)*4*t%7; } int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); long long N; cin>>N; vector<array<long long,2>>A(N); for(long long i=0;i<N;i++)cin>>A[i][0]>>A[i][1]; array<array<long long,6>,7>dp; for(long long i=0;i<7;i++)for(long long j=0;j<6;j++)dp[i][j]=0; dp[0][0]=1; for(long long i=N-1;i>=0;i--){ array<array<long long,6>,7>dp2; for(long long j=0;j<7;j++)for(long long k=0;k<6;k++)dp2[j][k]=0; for(long long j=0;j<7;j++){ for(long long k=0;k<6;k++){ dp2[j][k]=(dp2[j][k]+dp[j][k])%mod; dp2[(j+d(A[i][0],A[i][1])*mod7_10[k])%7][(k+A[i][1])%6]=(dp2[(j+d(A[i][0],A[i][1])*mod7_10[k])%7][(k+A[i][1])%6]+dp[j][k])%mod; } } dp=dp2; } long long ans=0; for(long long i=0;i<7;i++){ for(long long j=0;j<6;j++){ ans=(ans+(dp[i][j]*i))%mod; } } cout<<ans<<'\n'; }